EXCELSIOR

1. Introduction 본문

Graph Theory

1. Introduction

Excelsior-JH 2020. 2. 24. 20:19

이번 포스팅은 Graph Theory에 관하여 참고할만한 자료를 검색하던 중 맨체스터 대학교의 Discrete Math의 Lecture Note 자료를 얻게 되어 이를 바탕으로 공부하면서 정리한 것입니다.



1. Introduction

1.1 Graph Theory

  • 그래프 이론(Graph Theory)은 1736년에 그 유명한 오일러(Euler)에 의해 시작 되었다.

  • 오일러는 Königsberg Bridge Problem을 풀기 위해 아래의 그림과 같이 육지(land)를 하나의 점(point)으로 나타내고, 다리(bridge)를 선(line)으로 추상화하여 나타냈다. 이 때 사용한 방식이 바로 그래프 이론의 시초가 된다.


  • Königsberg Bridge Problem는 다음과 같다. 이 문제의 답을 미리 말하자면, "불가능 하다" 이다.

    • 예를 들어, East Island 에서 출발한다고 했을 때, 각 지역을 다 돌고 다시 East Island로 돌아와야 한다.

    • 이 때, 모든 다리 를 정확히 한번씩 그리고 한번만 건너야 한다.

  • 오일러는 이 문제에 대한 풀이와 함께 전반적인 그래프 이론을 제시하게 된다.



1.2 Definitions: Graph, Vertex, Edge

Graph, Vertex, Edge

  • 그래프 이론에 대해 공부하기 위해 가장 기본이 되는 정의(definition)부터 살펴보자.

  • 그래프(graph)와 정점(vertex or node), 그리고 에지(edge)에 대한 정의는 다음과 같다.


Definition 1.1.

A graph is a finite, nonempty set , the vertex set, along with a set , the edge set, whose elements are pairs with .


  • 위의 정의를 바탕으로 그래프를 다음과 같이 적을 수 있다.

    • : vertex 집합(set) edge set 로 이루어진 graph .

    • vertex (복수형은 vertices)라 부르고, edge라 한다.


Undirected / directed graph

  • 이 때, edge set을 어떻게 정해 주느냐에 따라 unirected graphdirected graph로 나뉘게 된다.

  • 먼저 undirected graph의 정의에 대해 살펴보자.

    Definition 1.2

    An undirected graph is a graph in which the edge set consists of unordered pairs.

    • unordered pairs란 vertex 의 edge를 나타내는 pair 로 나타내거나, 로 나타내도 상관 없는 경우를 말한다.

    • 이 의미는 결국 edge 에 화살표 즉, 방향이 없는 그래프를 의미 한다.


  • 다음의 정의는 directed graph에 해당한다.

    Definition 1.3

    A directed graph is a graph in which the edge set consists of ordered pairs. The term "directed graph" is often abbreviated as digraph.

    • undirected graph와는 반대로 edge 인 경우의 그래프를 directed graph라고 한다.

    • 이 때, vertex 사이의 edge를 화살표(→)를 사용하여 연결한다.

    • directed graph를 줄여서, digraph라고도 많이 부른다.


  • 아래의 그림은 vertex edge 인 그래프 에 대해 undirected graph(왼쪽)와 digraph(오른쪽)를 각각 나타낸 것이다.


Self loop and parallel edge

  • 때에 따라 graph는 두 vertex 에 대해 하나 이상의 edge로 연결되어 있는 경우가 있는데, 이를 multiple edge 또는 parallel edge라고 한다. 위에서 살펴본 Königsberg Bridge graph가 이에 해당한다.

  • 또한, vertex 즉, 자기 자신을 연결하는 edge 가 있을 수 있는데, 이를 loop 또는 self loop라고 한다.


Tip

  • VertexNode라고 부르기도 하는데 이 두 단어의 차이는 없다고 한다.[링크]

  • digraph에서의 edge를 arc라고 부르기도 하는데, 어떤 곳에서는 edgearc를 같은 의미로 사용하기도 한다.

Remark

  • 이번에 포스팅할 Graph Theroy에서 다루는 일반적인 "graph"는 self loop 와 parallel edges가 없는 undirected graph를 의미한다.

  • 이러한 undirected graph인 "graph"를 다른 교재에서는 simple graph라 말하기도 한다.

  • 이와 반대로 parallel edge를 포함하고 있는 graph를 multigraph라 부르기로 한다.




Adjacent, Predecessor

  • 이번에는 graph의 두 node 관계를 나타내는 adjacentpredecessor에 대해 알아보자.

Definition 1.4

Two vertices in an undirected graph are said to be adjacent or to be neighbours if . In this case we also say that the edge is incident on the vertices and .


  • undirected graph 의 두 vertex 가 edge 로 연결 되어 있으면, 이를 adjacent하다 라고 한다.

Definition 1.5

If the directed edge is present in a directed graph we will say that is a predecessor of and that is a successor of . We will also say taht is the tail or tail vertex of the edge , while is the tip or tip vertex.


  • directed graph 의 두 vertex 이면, 를 의미한다. 이때, 노드를 predecessor 또는 tail vertex라 하고, 화살표를 받는 노드 successor 또는 tip vertex라고 한다.


1.3 Standard examples

  • 이번에는 몇가지 graph에 대한 종류를 살펴보도록 하자.


The complete graphs

  • complete graph 은 undirected graph이며 개의 vertex가 서로 연결되어 있는 graph를 의미한다. 즉, 서로 다른 두 개의 vertex 에 대해 반드시 하나의 edge 로 연결된 undirected graph를 말한다.

  • 이를 수식으로 나타내면 다음과 같다.

  • 이 때, 집합 의 크기는 다음과 같다.

  • 아래의 그림은 에 해당하는 complete graph를 나타낸 예시다.


The path graphs

  • path graph 개의 vertex가 하나의 path로 연결되어 있는 graph 이다.

  • 이를 수식으로 나타내면 다음과 같다.

  • 아래의 예시를 통해 쉽게 이해할 수 있다.



The cycle graphs

  • cycle graph circuit graph라고도 하며, vertex의 개수 인 graph에서 표현할 수 있다.

  • 위의 식 에서도 확인할 수 있듯이, cycle graph이기 때문에 이므로, 이 되는것을 확인할 수 있다.


The complete bipartite graphs

  • 먼저, bipartite graph(이분 그래프)를 먼저 살펴보면, graph 내의 모든 vertex를 두 개의 vertex set인 로 나눌 수 있고, 같은 집합 내에서는 edge가 없는 graph를 말한다.


Definition 1.6

A graph is said to be a bipartite graph if

  • it has a nonempty edge set : and

  • its vertex set can be decomposed into two nonempty, disjoint subsets

in such a way that all the edges contain a member of and a member of .


  • 이 때, 인 vertex와 인 vertex 에 대해 모두 edge로 연결되어 있는 graph를 complete bipartite graph 이라고 한다.

  • 이를 수식으로 나타내면 다음과 같다.

  • graph는 아래의 그림에서 확인할 수 있듯이, 인 edge를 가지는 graph를 의미한다.


The cube graphs

  • cube graph 에서 -dimensional cube graph를 의미하며, 각 vertex는 차원으로 구성되며 0 또는 1의 이진수를 label로 하는 graph를 의미한다.

  • 이 때, edge들은 서로 다른 label을 가지는 노드 쌍을 연결한다.

  • 예를 들어 는 다음과 같은 vertex 와 edge 를 가진다.

  • cube graph 를 수식으로 나타내면 다음과 같다.

  • 의 Vertex 개수는 를 가지지만, edge의 개수는 를 가진다.

  • 아래의 그림은 에 해당하는 cube graph이며, 모든 cube graph는 bipartite graph임을 확인할 수 있다.




1.4 A first theorem about graphs

  • 이번에는 graph에 대한 Theorem을 알아보자.


degree

Definition 1.7

In an undirected graph the degree of a vertex is the number of edges that include the vertex. One writes for "the degree of ".

  • degree는 위의 정의에서도 알 수 있듯이, vertex 가 가지는 edge의 개수를 말한다.

    • complete graph 의 모든 vertex 이다.

    • cycle graph 의 모든 vertex 이다.

  • digraph(directed graph)는 두 종류의 degree를 가진다:

    • in-degree : vertex tip vertex가 되는 즉, 화살표가 들어오는 edge의 개수를 말한다.

    • out-degree는 vertex tail vertex가되는 즉, 화살표가 나가는 edge의 개수를 말한다.


  • 아래의 예시 그림은 두개의 "pieces"로 구성되어 있는 undirected graph의 각 vertex에 해당하는 degree를 나타낸 것이다.

  • 아래의 그림은 digraph의 각 vertex에 대해 in-degreeout-degree를 나타낸 것이다.


Handshaking Lemma

  • 위에서 살펴본 degree를 바탕으로 다음의 정리(theorem)를 도출할 수 있다.

Theorem 1.8 Handshaking Lemma, Euler 1736

If is an undirected graph then


  • 위의 정리를 바탕으로 다음을 알 수 있다.

Corollary 1.9

In an undirected graph there must be an even number of vertices that have odd degree.

  • 정리 1.8에서 undirected graph에서의 모든 노드 의 degree의 합은 짝수이기 때문에, 홀수개의 degree를 가지는 짝수개의 어떤 노드 가 존재한다.


  • 위에서 살펴본 cube graph 의 edge의 개수 에 대해 살펴보자.

Corollary 1.10

The cube graph has

  • cube graph 개의 vertex 개수를 가지며, 이 때 각 vertex 이다.

  • 따라서, Handshaking Lemma에 의해 다음과 같이 구할 수 있다.


'Graph Theory' 카테고리의 다른 글

3. Graph Colouring  (2) 2020.03.22
2. Representation, Sameness and Parts  (0) 2020.03.01
Comments