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