1. Introduction

이번 포스팅은 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 graph와 directed 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

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

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

Remark

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

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

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

---

Adjacent, Predecessor

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

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-degree와 out-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에 의해 다음과 같이 구할 수 있다.