9. Graphs

9.1. Graphs and Graph Models

Graph $G=(V,E)$는 비어 있지 않은 Vertex $V$와 Edge $E$로 이루어져 있는 Set이다.
각 Edge는 하나 혹은 두 개의 Vertex와 연결되어 있으며 이를 Endpoint라 한다.
Edge는 Endpoint를 Connect한다고 한다.

경고

Remark

Graph $G$의 Vertex set $V$가 Infinite할 수 있다.
이를 Infinite graph라고 하며 Finite한 Vertex를 가진 Graph를 Finite graph라 한다.

한 Vertex pair에 하나의 Edge만 있다면 그 Graph를 Simple graph라 하고 한 Vertex pair에 여러 Edge가 존재할 수 있다면 Multigraph라 하며 $\{u, v\}$로 Edge를 나타낼 때 이 Edge가 $m$개 존재한다면 Multiplicity가 $m$이라고 표현한다.
Vertex pair가 $\{u,u\}$ 꼴이라면 이를 Loop라고 하고 동일한 Vertex pair를 연력하는 여러 Edge를 가질 수 있는 Graph를 Pseudograph라고도 한다.
위 Edge들의 방향성이 없는 Graph들을 Undirected graph라고 한다.

Diagraph $(V,E)$는 Nonempty vertex set $V$와 Directed edge $E$로 구성된다.
각 Directed edge는 Vertex의 Ordered pair와 관련이 있다.
Ordered pair $(u, v)$는 Vertex $u$에서 $v$로의 Directed edge를 의미하며 Multiple directed edge도 Loop도 존재할 수 있다.
Multiple directed edge가 존재할 수 없는 Graph를 Simple directed graph라 하고 Multiple directed edge가 존재할 수 있는 Graph를 Directed multigraph라 한다.
Directed multigraph의 Edge $(u,v)$가 $m$개 존재한다면 Multiplicity가 $m$이라고 표현한다.

Directed edge와 Undirected edge가 혼용된다면 그 Graph를 Mixed graph라고 표현한다.

Type	Edges	Multiple Edges Allowed?	Loops Allowed?
Simple graph	Undirected	No	No
Multigraph	Undirected	Yes	No
Pseudograph	Undirected	Yes	Yes
Simple directed graph	Directed	No	No
Directed multigraph	Directed	Yes	Yes
Mixed graph	Directed, Undirected	Yes	Yes

Graph Models

Graph는 다양한 Model에서 사용된다.

팁

Example

생태학에서 종간 경쟁은 Niche overlap graph를 사용한다.
두 종이 경쟁할 경우 두 종을 연결하는 Undirected edge가 생성되며 Multiple edge나 Loop가 필요하지 않은 Simple graph로 사용된다.

팁

Example

Influence graph는 집단 행동 연구등에 사용할 수 있고 Vertex는 각 사람, Directed edge는 시작 Vertex인 사람 $a$가 끝 Vertex의 $b$에게 영향을 줌을 나타낼 수 있고, Loop를 포함하지 않고 Multiple Edge가 생성되지 않으므로 Simple directed graph로 사용된다.

9.2. Graph Terminology and Special Types of Graphs

Basic Terminology

Undirected graph $G$에서 두 Vertex $u, v$는 $G$의 Edge의 endpoint가 될 때 Adjacent(neighbor)라 한다.
Edge $e$가 $\{u,v\}$가 연관이 있다면 이를 Edge $e$는 Vertex $u$, $v$와 Incident이라고 하고 Connect라도고 한다.
Undirected graph에서 Vertex의 Degree는 Vertex에 Incidented edge의 수를 의미하며 Vertex에 Loop가 있을 경우 Degree에 두번 기여한다.
Vertex $v$의 Degree를 $\deg(v)$라고 표현한다.

팁

Example\

각 Vertex의 Degree$\deg$

• Solution
  $\deg(a)=4, \deg(b)=6, \deg(c)=1, \deg(d)=5, \deg(e)=6$

정보

Theorem

The handshaking theorem
Undirected graph $G=(V,E)$가 $e$개의 Edge를 가질 때 $2e=\sum_{v\in V}\deg(v)$

정보

Theorem

Undirected graph는 홀수 degree를 가진 Vertex가 짝수개 있다.

• Proof
  Undirected graph $G=(V,E)$에서 홀수, 짝수 Degree를 가진 Vertex set $V_1, V_2$로 두면 $2e=\sum_{v\in V}\deg(v)=\sum_{v\in V_1}\deg(v)+\sum_{v\in V_2}\deg(v)$이다.
  두 분리된 Graph 역시 $v\in V_2$ 역시 짝수이므로 $\sum_{v\in V_1}\deg(v)$역시 짝수이다.

$(u,v)$가 Digraph $G$의 Edge일 때 $u$는 $v$에 Adjacent하다고 하고 $v$는 $u$로 부터 Adjacent하다고 한다.
Vertex $u$는 $(u,v)$의 Initial vertex, $v$는 Terminal 혹은 End vertex라고 한다.
Loop의 경우 Inital과 Terminal vertex가 동일하다.
Digraph에서 Degree는 In-degree와 Out-degree가 존재하며 Notation으로 각각 $\deg^-(v),\deg^+(v)$로 표현한다.
In-degree $\deg^-(v)$는 $v$를 Terminal vertex로 두는 Edge의 수이며 Out-degree $\deg^+(v)$의 경우 $v$가 Inital vertex인 Edge의 수를 의미한다.
$v$Digraph에서 Loop는 In/Out-degree에 1씩 기여한다.

정보

Theorem

Digraph $G=(V,E)$에 대해 $\sum_{v\in V}\deg^-(v)=\sum_{v\in V}\deg^+(v)=|E|$

Digraph의 Edge에는 Direction 상관없이 영향을 미치지 않는 여러 Property가 존재한다.
Digraph의 Direction을 무시하여 얻은 Graph를 Underlying undirected graph라고 한다.

Some Special Simple Graphs

팁

Example

• Complete graph
  Complete graph $K_n$은 $n$개의 Vertex가 있고 서로 다른 Vertex끼리의 Edge가 1개 씩 포함된다.
• Cycle
  Cycle $C_n$은 $n\geq 3$일 때 Vertex $v_1,v_2,\dots,v_n$과 Edge $\{v_1, v_2\},\cdots,\{v_{n-1},v_{n}\},\{v_n,v_1\}$으로 구성되어 있다.
• Wheels
  Wheel $W_n$은 $n\geq 3$일 때 Cycle $C_n$에 추가 Vertex를 더하여 이 Vertex에 $C_n$의 Vertex들을 모두 연결하는 Edge를 얻는다.
• $n$-cubes
  $n$-cube($n$-dimensional hypercube) $Q_n$은 길이가 $n$인 $2^n$ Bit string을 나타내는 Vertex가 있는 Graph이다.
  두 Vertex는 나타내는 Bit 문자열이 정확히 하나의 Bit 위치에서 다를 때 Adjaccent하다.
  $Q_n$에서 $Q_{n+1}$을 생성할 수 있는데 이 때 $Q_n$을 복사하여 원본 첫 Bit에 0, 복사본엔 1을 둬 첫 Bit만이 다른 Vertex들을 연결하는 Edge를 추가함으로 얻을 수 있다.

Bipartite Graphs

Simple graph $G$의 Vertex set $V$를 두 개의 분리된 Set $V_1, V_2$로 나눌 때 이를 Bipartite graph라고 한다.
Bipartite graph는 $V_1$에서 $V_2$만을 연결하므로 $G$의 어떤 Edge도 같은 Set에 존재하는 Vertex를 연결하지 않고 이 때 $(V_1,V_2)$는 Graph $G$의 Vertex set $V$를 Bipartition하였다고 표현한다.

팁

Example

• Complete bipartite graph
  Complete bipartite graph $K_{m,n}$은 Vertex set이 각각 $m,n$개인 두 개의 Subset으로 나누어진 Graph

Some Applications of Special Types of Graphs

Simple graph에서 Matching은 Graph의 Edge set의 Subset으로 두 개의 Edge가 동일한 Vertex에 Connect되지 않는 것을 의미한다.
Maximal matching은 가장 많은 Edge를 가진 Matching을 의미한다.

New Graphs from Old

문제 해결을 위해 Original graph 전체가 다 필요하지 않을 수 있다.
이 때 Original graph의 Subgraph만을 이용하여 조금 더 편하게 문제를 해결 가능하다.

Graph $G=(V,E)$의 Subgraph $H=(W,F)$($W\subseteq V\land F\subseteq E$)가 존재할 때 $H$가 $G$의 Proper subgraph이기 위해 $H\not=G$여야 한다.

팁

Example

$K_5$의 Subgraph $G$

Simple graph $G_1=(V_1,E_1), G_2=(V_2,E_2)$의 Union은 Vertex set이 $V_1\cup V_2$이고 Edge set이 $E_1\cup E_2$인 Simple graph이다.
$G_1, G_2$의 Union을 Notation $G_1\cup G_2$로 나타낸다.

팁

Example

$G_1\cup G_2$

• Solution\

9.3. Representing Graphs and Graph Isomorphism

두 Graph가 동일한 형태를 가질 때 Vertex set 간 One-to-one correspondence가 존재해 Edge를 보존함을 의미하며 이 때 두 Graph가 Isomorphic(동형)이라고 한다.

Representing Graphs

Multiple edge가 없는 Graph를 표현하는 하나의 방법은 Graph의 모든 Edge를 나열하는 것이다.
다른 방법으로는 Adjacency list(인접 목록)을 사용하여 Graph의 각 Vertex에 Adjacent한 Vertex들을 지정한다.

팁

Example

Adjacency list를 사용하여 위 Simple graph를 표현

• Solution
  (Vertex : Adjacent vertices)
  a : b, c, e
  b : a
  c : a, d, e
  d : c, e
  e: a, c, d

팁

Example

Adjacency list를 사용하여 위 Directed graph를 표현

• Solution
  (Initial vertex : Terminal vertices)
  a : b, c, d, e
  b : b, d
  c : a, c, e
  d :
  e : b, c, d

Adjacency Matrices

Graph를 Edge list나 Adjacency list로 표현하여 Graph algorithm을 수행하는 것이 번거로울 때 Matrix로 표현하곤 한다.

$G=(V,E)$가 Simple graph이고 $|V|=n$일 때 $G$의 Vertex들 $V_1, V_2, \dots, V_n$과 같이 임의로 나열되어 있을 때 $G$의 Adjacency matrix $A(A_G)$는 이 Vertex들의 나열에 대해 $n\times n$ 크기의 Zero-one matrix로 $V_i, V_j$가 Adjacent일 때 $(i, j)$ Entry가 1이고 그렇지 않다면 0을 갖는다.
즉 $A=[aij]$, $a_{ij}=\begin{cases}1 & \text{if }\{v_i,v_j\}\text{is an edge of }G\\0 & \text{otherwise}\end{cases}$이다.

팁

Example

위 Simple graph의 Adjacency matrix

• Solution
  $\begin{bmatrix}0&1&1&0\\1&0&0&1\\1&0&0&1\\0&1&1&0\end{bmatrix}$

Graph의 Adjacency matrix는 Vertex에 대해 선택된 순서에 따라 결정이 된다.
$n$개의 Vertex를 가진 Graph에는 $n!$개의 서로 다른 Adjacency matrix가 존재한다($n$개의 Vertex의 순서는 $n!$개 이기에).
Simple graph의 Adjacency matrix는 Symmetric($a_{ij}=a_{ji}$) $v_i,v_j$가 Adjacent할 때 두 Entry가 1이 되고 그렇지 않다면 0이 된다.
Simple graph의 경우 Loop가 없기에 $a_{ii}=0$이다.
Multigraph일 경우 Adjacency matrix는 Zero-one matrix가 아니고 Matrix의 $(i,j)$ Entry는 $\{a_i,a_j\}$와 Connect된 Edge의 수와 같다.
모든 Undirected graph는 Symmetric adjacency matrix를 가진다.

Simple graph가 Sparse(Edge의 수가 적을 때)할 때 Graph를 표현하기 위해 Adjacency list를 사용하는 것이 더 효과적이다.
각 Vertex의 Degree가 $c$를 초과하지 않고 $c$가 $n$보다 훨씬 작은 Constant일 경우 각 Adjacency list는 $c$개 이하의 Vertex만 포함한다.

Simple graph가 Dense(조밀하다, Edge의 수가 많을 때)할 때, 즉 가능한 모든 Edge의 절반 이상을 포함하는 Graph와 같이 많은 Edge를 포함하고 있을 때 Adjacency matrix를 사용하여 Graph를 표현하는 것이 더 효과적이다.

Incidence Matrices

Graph를 나타내는 다른 방법 중 하나는 Incidence matrix를 사용하는 것이다.
$G=(V,E)$의 Undirected graph라고 할 때 $v_1,v_2,\dots,v_n$의 Vertex와 $e_1,e_2,\dots,e_m$의 Edge가 $G$에 존재할 때 Incidence matrix는 $V,E$에 대한 Ordering에 대한 $n\times m$ matrix로 정의되며 $M=[m_{ij}]$의 $m_{ij}=\begin{cases}1&\text{when edge }e_j\text{ is incident with }v_i\\0&\text{otherwise}\end{cases}$이다.

팁

Example

1.
2.
위 Graph의 Incidence matrix

• Solution 1
  $\begin{bmatrix}1&1&0&0&0&0\\0&0&1&1&0&1\\0&0&0&0&1&1\\1&0&1&0&0&0\\0&1&0&1&1&0\end{bmatrix}$
• Solution 2
  $\begin{bmatrix}1&1&1&0&0&0&0&0\\0&1&1&1&0&1&1&0\\0&0&0&1&1&0&0&0\\0&0&0&0&0&0&1&1\\0&0&0&0&1&1&0&0\end{bmatrix}$

Isomorphism of Graphs

Simple graph $G_1=(V_1,E_1), G_2=(V_2,E_2)$가 $V_1$에서 $V_2$로 One-to-one 그리고 Onto function이 존재하는 경우 Isomorphic이라고 한다.
이 때 $a, b$가 $G_1$에 Adjacent하면 그 경우 $f(a)$와 $f(b)$가 $G_2$에서 Adjacent해야 한다.
이런 Function $f$를 Isomorphism이라고 한다.

팁

Example

Graph $G=(V,E),H=(W,F)$가 Isomorphic인지 여부

• Solution
  $f(u_1)=v_1, f(u_2)=v_4,f(u_3)=v_3, f(u_4)=v_2$로 One-to-one correspondence을 형성한다.

두 Simple graph가 Isomorphic인 지 확인하는 것은 Vertex $n$의 수가 조금이라도 커질 경우 어렵기에 두 Graph가 Isomorphic이 아님을 보여주는 것이 더 쉽다.
Graph 중 하나만 갖는 Property를 찾는다면 그 Property는 Isomorphism에 의해 보존된다.
Isomorphism에 의해 보존되는 Property를 Graph invariant라고 한다.

팁

Example

Graph $G,H$가 Isomorphic인 지 확인

• Solution
  $G,H$ 모두 6개의 Vertex와 7개의 Edge를 가졌고 Degree 2인 Vertex로 구성된 Subgraph와 Connect하는 Edge들이 Isomorphic인 것을 확인할 수 있다.
  $G,H$가 Graph invariant가 일치하기에 Function $f$가 Isomorphism인 지 확인하면 된다.
  $u_1=v_6, u_2=v_3, u_3=v_4,u_4=v_5,u_5=v_1,u_6=v_2$로 놓고 Adjacency matrix를 구할 경우 $A_G=A_H=\begin{bmatrix}0&1&0&1&0&0\\1&0&1&0&0&1\\0&1&0&1&0&0\\1&0&1&0&1&0\\0&0&0&1&0&1\\0&1&0&0&1&0\end{bmatrix}$이다.
  즉 $G,H$는 Isomorphic이다.

9.4. Connectivity

Paths

Path는 Graph의 Vertex에서 시작하여 Graph의 Edge를 따라 Vertex에서 Vertex로 이동하는 Edge의 순서이다.
Nonnegative integer $n$, Undirected graph $G$에 대해 길이가 $n$인 Path는 Vertex $u$에서 $v$로의 Graph $G$의 $n$개의 Edge의 Sequence이다.
Graph가 Simple graph인 경우 이 Vertex Sequnce를 $x_0,x_1,\dots, x_n$으로 나타낸다.
Path는 Begin vertex $u$, End vertex $v$가 같으며 길이 $n>0$일 경우 Circuit이라고 한다.
Path와 Circuit은 해당 Vertex를 Pass through한다고 하거나 Edge를 Traverse한다고 하며 같은 Edge를 포함하지 않을 경우 Simple이라고 말한다.

경고

Remark

Path 대신 Walk라는 용어를 사용하여 Graph의 Vertex와 Edge의 교대로 이루어진 Sequence를 의미할 수도 있다.
이 때 Circuit 대신 Close walk라는 용어를 사용한다.
Simple path 대신 Trail이라는 용어를 사용한다.

팁

Example

그림의 Simple graph에서 $a, b, c, d, e$는 길이가 4인 Simple Path이다.
$a,b,e,d,a,b$는 길이가 5인 Simple이 아닌 Path이다.

Nonnegative integer $n$과 Digraph $G$에 대해 Vertex $u$에서 $v$까지의 길이가 $n$인 Path는 Edge들의 Sequence이며 Multiple graph가 아닌 경우 Vertex의 Sequence나 나열로 나타내기도 한다.
앞전과 마찬가지로 Begin vertex와 End vertex가 같으며 길이가 0이 아니라면 Circuit이나 Cycle이라고 부른다.
중복된 Edge가 없을 경우 Simple하다고 표현한다.

Connectedness in Undirected Graphs

Undirected graph의 Vertex들이 서로 Connected라고 표현하기 위해서는 모든두 Vertex를 연결할 수 있는 Path가 존재해야 한다.

팁

Example

그림의 왼쪽 Graph는 Connected graph, 오른쪽 그래프는 Not connected graph이다.
예시로 $a,d$가 서로 연결되어 있지 않기 때문이다.

정보

Theorem

Connected undirected graph의 모든 두 개의 Distinct vertex들은 Simple path가 존재한다.

Connected component란 Connected graph $G$의 Connect subgraph에 대해 Not a proper subgraph이다.

팁

Example

위 그림에서의 Graph $H$의Connected component

• Solution
  Graph $H$는 3개의 Disjoint connected subgraph $H_1, H_2, H_3$의 Union이다.
  즉, $H_1, H_2, H_3$는 $H$의 Connected component이다.

Connectedness in Directed Graphs

Digraph에서의 Connected는 Vertex $u$에서 $v$로도, $v$에서 $u$로도 갈 수 있는 Path가 모든 Vertex에 존재할 경우 Strongly connected, Undirected graph로 전환하였을 때 Connected될 경우 Weakly connected라고 한다.

Digraph $G$의 Subgraph 중에서 Strongly connected인 Component를 Strong component라고 한다.

Paths and Isomorphism

Path와 Circuit은 두 Graph가 Isomorphic인지 판단하는 데 사용될 수 있다.
특정 길이의 Simple path로 두 Graph가 Isomorphic이 아닌 지 보여줄 수 있는 Invariant이다.

팁

Example

Graph $G, H$가 Isomorphic인 지 확인

• Solution
  $G, H$는 모두 8개의 Edge와 6개의 Vertex로 구성되어 있고 각 Graph에는 Degree가 3인 Vertex가 4개, Degree 2인 Vertex가 2개 있다.
  $H$는 길이가 3인 Simple Circuit $v_1, v_2, v_6, v_1$을 가지고 있으나 $G$는 길이가 3인 Curcuit을 가지고 있지 않으므로 $G,H$는 Not isomorpic이다.

Counting Paths Between Vertices

정보

Theorem

Graph $G$를 Vextex $v_1, \dots, v_n$에 대한 Adjacency matrix $A$를 갖는 Graph라고 할 때 길이 $r$인 $v_i$에서 $v_j$의 서로 다른 Path의 수는 $A^r$의 $(i,j)$번째 Entry 수와 같다.

• Proof
  Mathematical induction을 사용하여 $G$가 Adjacency matrix $A$를 가지는 Graph라고 할 때 $A^{r+1}=A^rA$이므로 $A^{r+1}$의 $(i,j)$번째 Entry는 $b_{ij}a_{1j}+b_{i2}a_{2j}+\cdots+b_{in}a_{nj}$($b_{ik}=(i,k)$번째 $A^r$의 Entry)이다.
  Induction hypothesis에 따라 $b_{ik}$는 길이가 $r$인 $v_i$에서 $v_k$의 Path의 수이다.
  길이가 $r+1$인 $v_i$에서 $v_j$까지의 Path는 $v_i$에서 Intermediate vertex $v_k$까지의 길이 $r$인 Path와 $v_k,v_j$로 이루어진 Edge로 구성되므로 $v_i$에서 $v_k$까지의 길이 $r$인 Path의 수인 $b_{ik}$와 $v_k$에서 $v_j$까지의 Edge수인 $a_{ki}$의 Product이므로 증명할 수 있다.

팁

Example

$a$에서 $d$로의 길이가 4인 Path의 개수

• Solution
  Graph의 Adjacency matrix는 $A=\begin{bmatrix}0&1&1&0\\1&0&0&1\\1&0&0&1\\0&1&1&0\end{bmatrix}$이다.
  $A^4=\begin{bmatrix}8&0&0&8\\0&8&8&0\\0&8&8&0\\8&0&0&8\end{bmatrix}$이므로 $(1,4)$번째 Entry인 8이다.

9.5. Euler and Hamilton Paths

Euler Paths and Circuits

Graph $G$에 해당하는 Euler circuit은 $G$의 모든 Edge를 포함하는 Simple circuit을 의미한다.
$G$의 Euler path는 $G$의 모든 Edge를 포함하는 Simple path를 의미한다.

간단히 요약하여 Euler path(circuit)은 한붓 그리기이다.

팁

Example

해당 Digraph 중 Euler curcuit의 유무

• Solution
  Graph $H_2$는 $a,g,c,b,g,e,d,f,a$로 Euler circuit을 가지고 있다.
  추가적으로 $H_3$은 $c,a,b,c,d,b$로 Euler path를 가지고 있다.

정보

Theorem

두 개 이상의 Vertex가 있는 Connected multigraph는 모든 Vertex의 Degree가 짝수일 때 Euler circuit이 존재

정보

Pseudocode

Algorithm Constructing Euler Circuits

procedure $Euler$($G$: connected multigraph with all vertices of even degree)
$circuit$ := a circuit in $G$ beginning at an arbitrarily chosen vertex with edges successively added to form a path that returns to this vertex
$H$ := $G$ with the edges of this circuit removed
while $H$ has edges
begin
$subsircuit$ := a circuit in $H$ beginning at a vertex in $H$ that also is an endpoint of an edge of $circuit$
$H$ := $H$ with edges of $subcircuit$ and all isolated vertices removed
$circuit$ := $circuit$ with $subcircuit$ inserted at the appropriate vertex
end {$circuit$ is and Euler circuit}

팁

Example

Mohammed's Scimitars 모양의 Graph $G$에 Euler circuit이 있는 지 확인

• Solution
  모든 Vertex들의 Degree가 짝수이기에 존재한다.
  위 Pseudocode를 참조하여 Euler circuit을 구성할 수 있다.
  먼저 $a,b,d,c,b,e,i,f,e,a$인 Circuit을 형성하고 이 Circuit에서의 모든 Edge와 이 Edge가 제거될 때 Isolated(고립)되는 모든 Vertex를 삭제하여 Subgraph $H$를 얻는다. $H$는 $d,g,h,j,i,h,k,g,f,d$이며 $G$의 모든 Edge를 사용하였기에 $a,b,d,g,h,j,i,h,k,g,j,d,c,b,e,i,j,e,a$가 Euler circuit임을 알 수 있다.

정보

Theorem

Connected multigraph는 정확히 두 개의 홀수 Degree인 Vertex가 있을 때 Euler path를 가짐(Not an Euler circuit)

팁

Example

그림의 Graph들 중 어떤 Graph가 Euler path를 가지고 있는가

• Solution
  $G_1$은 Degree가 홀수인 Vertex가 $b, d$이므로 정확히 두 개 가지고 있기에 $b,d$가 End vertex인 Euler path를 가진다($d,a,b,c,d,b$).
  $G_2$는 Degree가 홀수인 Vertex가 $b,d$이므로 Euler path를 가진다($b,a,g,j,e,d,c,g,b,c,j,d$).
  마지막으로 $G_3$는 Degree가 홀수인 Vertex가 $a,b,c,d,e,f$이므로 Euler path를 가지지 못한다.

Hamilton Paths and Circuits

Hamilton path의 경우 Graph의 모든 Vertex를 정확히 한 번씩 통과하는 Simple Path를 의미하며 이가 Circuit일 경우 Hamilton circuit이라고 한다.
즉 Vertex set $V=\{x_0,\dots,x_{n-1},x_n\}$에 대해 $0\leq i<j\leq n$에 대해 $x_i\not=x_j$일 때 Path $x_0,\dots,x_n$은 Hamilton path가 된다.

간단히 요약하여 Hamilton path와 circuit의 경우 모든 구역을 돌기 위한 동선과 같다.

팁

Example

Graph들의 Hamilton circuit이나 Hamilton path의 유무

• Solution
  $G_1$은 Hamilton circuit이 존재한다($a,b,c,d,e,a$).
  $G_2$는 모든 Vertex를 지나는 Circuit을 위해서$\{a,b\}$ Edge를 두 번 포함해야 하므로 Hamilton circuit은 존재하지 않으나 Hamilton path는 존재한다($a,b,c,d$).
  $G_3$눈 Hamilton circuit, Hamilton path가 존재하지 않는다.

정보

Theorem

Dirac's Theorem

$G$가 $n$개의 Vertex를 가진 Simple graph이며 $n\geq 3$이고 $G$의 모든 Vertex들의 Degree가 $\frac{n}{2}$이상일 경우 $G$는 Hamilton circuit을 가진다.

정보

Theorem

Ore's Theorem

$G$가 $n$개의 Vertex를 가진 Simple graph이며 $n\geq 3$이고 $G$의 모든Nonadjacent vertex pair $u,v$에 대해 $\deg(u)+deg(v)\geq n$을 만족할 경우 Hamilton circuit을 가진다.

팁

Example

Graycode는 1940년대 AT&T Bell Lab.에서 Digital signal transmitting error의 Effect를 Minimize하기위해 Frank Gray가 발명했다.
회전하는 Pointer의 위치를 Digital form으로 표현할 수 있다.

위 그림은 길이가 3인 Bit string을 사용하는 두 가지 방법이다.
즉 $2^n$개의 Arc로 나눈 후 각 Arc에 $n$-bit string을 할당한 것이다.

Pointer가 두 Arc의 Boundary 근처에 있을 때 Pointer의 위치를 읽는데 실수가 발생할 수 있다.
예시로 Bit string 010대신 011이 읽힐 수 있다.
Gray code는 Adjacent arc가 정확히 하나의 Bit만 다르게 Label이 붙은 Arc의 Labeling이다.
즉 이는 길이가 $n$인 Bit string을 나열하여 각 String이 정확히 하나의 위치에서만 다르며 이는 $n$-cube인 $Q_n$을 Modeling할 수 있다.
즉 위 예시에서의 Gray code는 $Q_3$에 대한 Hamilton circuit을 사용하여 쉽게 찾을 수 있다.

예시로 $Q_3$에 의한 Hamilton circuit에 의해 생성된 Bit string의 순서는 000, 001, 011, 010, 110, 111, 101, 100이다.

9.6. Shortest-Path Problems

Edge마다 숫자(비용)가 할당된 Graph를 Weighted graph라고 한다.
Weighted graph 관련 Problem은 주로 모든 Vertex에서 Complete graph를 정확히 한번 방분하는 최단 비용 Path(Circuit)을 찾는 것이다.

A Shortest-Path Algorithm

Weighted graph에서 두 Vertex 간 Shortest path를 찾는 다양한 Algorithm이 존재한다.

팁

Example

위 Weighted graph에서 $a$에서 $z$ 사이 Shortest path

• Solution
  $a$에서 시작하는 Path는 $a, b$와 $a, d$만 존재하므로 다른 Path가 포함되지 않는다.
  $a, b$보다 $a, d$가 작으므로 $d$는 $a$에 $b$보다 더 가까운 Vertex이다.
  다음으로 가까운 Vertex를 찾기 위해 $a$와 $d$를 통과하는 모든 Path를 살펴보면 $b$로 가는 Shortest path는 $a, b$로 4이며, $e$는 $a,d,e$로 5이다. 즉 $a$에서 두 번째로 가까운 Vertex는 $b$이다.
  $a$에서 세 번째로 가까운 Vertex를 찾기 위해 $a, d, b$를 통과하는 Path를 살펴보면 되므로 $c$는 $a,b,c$, 즉 7이고 $z$는 $a,d,e,z$로 6이다.
  위 과정으로 인해 $a$에서 $z$로 가는 Shortest path는 $6$이 된다.

앞전 Example에서 사용한 Algorithm을 Dijkstra's algorithm이라고 한다.
Dikstra's algorithm은 첫 Vertex $a$에는 0, 나머지 Vertex들에게는 $\infin$을 Labeling한 후 $a$에서 각 Vertex까지의 Shortest path를 나타내는 값으로 대치하는 Algorithm이다.

Vextex들의 Distinguished set $S_k$를 만들며 이때의 $k$는 반복 횟수가 된다.
Initial set $S_0=\empty$이다.
Set $S_k$는 $S_{k-1}$에서 $S_{k-1}$에 포함되지 않은 Label이 가장 작은 Vertex $u$를 추가하며 형성한다.
$u$가 $S_k$에 추가되면 $S_k$에 포함되지 않은 모든 Vertex의 Label을 Update한다.
이 때 $L_k(v)$는 $k$번째 Step에서 Vertex $v$의 Label로 $S_k$에 포함된 Vertex만을 포함하는 $a$에서 $v$까지의 Shortest path의 길이이다.

Vertex $v$가 $S_k$에 포함되지 않은 경우 $v$의 Label을 Update하기 위해 $L_k(v)$는 $S_k$에 포함된 Vertex만을 포함하는 $a$에서 $v$까지의 Shortest path의 길이이다.
즉 $L_k(a,v)=\min\{L_{k-1}(a,v),L_{k-1}(a,u)+w(u,v)\}$이다($w$는 $u$와 $v$의 Weight이다).

이 Procedure를 Target vertex가 추가될 때 까지 순차적으로 추가하며 반복하여 Shortest path를 구할 수 있다.

정보

Pseudocode

Algorithm Dijkstra's Algorithm

procedure $Dijkstra$($G$: weighted connected simple graph, with all weights positive){$G$ has vertices $a=v_0,v_1,\dots,v_n=z$ and weights $w(v_i,v_j)$ where $w(v_i,v_j)=\infin$ if $\{v_i,v_j\}$ is not an edge in $G$}
for $i$ := 1 to $n$
$L(v_i)$ := $\infin$
$L(a)$ := 0
$S$ := $\empty$ {the labels are now initialized so that the label of $a$ is 0 and all other labels are $\infin$, and $S$ is the empty set}
while $z\notin S$
begin
$u$ := a vertex not in $S$ with $L(u)$ minimal
$S$ := $S\cup \{u\}$
for all vertices $v$ not in $S$
if $L(u)+w(u,v)<L(v)$ then $L(u)+w(u,v)$
{this adds a vertex to $S$ with minimal label and updates the labels of vertices not in $S$}
end {$L(z)$= length of a shortest path from $a$ to $z$}

정보

Theorem

Dijkstra's algorithm은 Connected simple undirected weighted graph의 Shortest path를 찾으며 $O(n^2)$의 Operator(Addition, Condition)을 사용한다.

The Traveling Salesman Problem

Traveling salesman problem은 각 Vertex를 정확히 한 번 방문하고 Begin vertex로 돌아오는 Weighted undirected graph에서 Shortest Hamilton circuit을 찾는 것과 같다.

즉, Traveling slaesman problem을 해결하기 위해 가장 간단한 방법은 모든 Hamilton circuit을 찾은 후 그 중 Shortest circuit을 찾는 것이다.
Graph에 $n$개의 Vertex들이 존재하면 시작점 선택 시 $(n-1)!$개의 서로 다른 Hamilton circuit을 조하새야 한다.
첫 Vertex 선택에 $n$, 두 번째 Vertex 선택에 $n-1,\dots$로 반복하기 때문이다.
Undirected graph임을 이용하여 $\frac{(n-1)!}{2}$개의 Circuit을 조사하여야 한다.

Traveling salesman problem은 실용적, 이론적 중요성을 가지므로 이를 해결하기 위한 효율적인 Algorithm 개발에 많은 노력을 가졌으나 이 문제를 해결하기 위한 Polynomial worst-case time complexity algorithm은 알려져있지 않다.

대신 이를 해결하기 위한 실용적인 접근법은 Approximation algorithm(근사 알고리즘)을 사용할 수 있다.
Algorithm 문제에 정확한 Solution을 제공하지 않으나 정확한 Solution에 근접한 Solution을 제공하는 것이 보장된다.
즉, 총 Weight $W'$가 $W\leq W' \leq cW$가 성립하도록 Hamilton circuit을 생성할 수 있다.
예시로 Weighted graph가 Triangle inequality를 만족하는 경우 $c=\frac{3}{2}$를 만족하는 Polynomial worst-case time complexity algorithm이 존재한다.
일반 Weighted graph에 대해 모든 Positive real number $k$에 해당하는 최선의 Solution의 $k$배 이하의 Solution을 생성할 수 있는 Algorithm은 알려져있지 않으며 이를 찾는다면 Class P와 Class NP가 동일하다는 것을 보여줄 수 있다.

9.7. Planar Graphs

Graph가 Edge가 교차하지 않고 Plane에 그릴 수 있는 경우 Planar(평면적)이라고 한다.

팁

Example

$K_4$는 Planar인 지

• Solution
  
  Planar이다.

팁

Example

$Q_3$는 Planar인 지

• Solution
  
  Planar이다.

팁

Example

$K_{3,3}$은 Planar인 지

• Solution
  $K_{3,3}$을 Plane에 그릴 때 Planar graph로 그릴 수 없다.
  $K_{3,3}$의 어떤 Planar representation에도 Vertex $v_1,v_2$는 $v_4,v_5$와 Connected여야 한다.
  이 네 개의 Edge는 Plane을 두 개의 Region $R_1, R_2$로 나누는 Closed curve를 형성한다($(a)$ 참조).
  
  Vertex $v_3$는 $R_1, R_2$ 중 하나에 위치해야 하고 만약 $v_3$가 $R_2$에 위치한다고 가정할 때 Closed curve의 내부에서 $v_3$와 $v_4,v_5$의 Edge가 $R_2$를 두 개의 Subregion $R_{21}, R_{22}$로 나누게 된다($(b)$ 참조).
  이 때 어떠한 방법으로도 마지막 Vertex $v_6$를 Crossing edge가 없이 배치할 수 없다.
  그렇기에 $K_{3,3}$은 Not planar graph이다.

Euler's Formula

Graph의 Planar representation은 Plane을 여러 Region으로 나누며 그 중 Unbounded region도 포함된다(아래 예시에서 $R_6$에 해당).

\

정보

Theorem

Euler's formula

$G$를 $e$개의 Edge와 $v$개의 Vertex를 가진 Simple planar graph라고 할 때 $G$의 Planar representation에서 $r$을 Region의 수라고 할 때 $r=e-v+2$이다.

• Proof
  Induction에 의해 증명 가능하다.
  Initial condition인 Relationship $r_1=e_1-v_1+2$라고 할 때 $e_1=1, v_1=2, r_1=1$이 되므로 성립한다.
  $r_n=e_n-v_n+2$가 성립하는 지 확인을 위해 $\{a_{n+1},b_{n+1}\}$를 Graph $G$에서 $G_{n+1}$이 될 때 추가된 Edge로 가정한다.
  이 두 Vertex들은 공통 Region $R$의 Boundary에 존재하여야만이 Crossing edge 없이 $G_n$에 추가할 수 있다.
  새로운 Edge에 의해 $R$은 두 개의 Region으로 나뉘게 된다.
  따라서 $r_{n+1}=r_n+1, e_{n+1}=e_n+1, v_{n+1}=v_n$이므로 Formula는 여전히 Valid하다.
  다른 경우 새로운 Edge의 두 Vertex중 하나가 $G_n$에 포함되어 있지 않을 경우 새 Region으로 분할하지 않으며 이 때 $r_{n+1}=r_n, e_{n+1}=e_n+1, v_{n+1}=v_n+1$이므로 Formula는 여전히 Valid하다.
  모든 상황에서 Formula가 Valid함을 증명했기에 $r_n=e_n-v_n+2$가 성립함을 증명하였다.\

팁

Example

Connected planar simple graph가 20개의 Vertex, 각 Vertex의 Degree가 3일 때 이Planar graph의Region의 개수

• Solution
  $v=20, 3v=60, 2e=60, e=30$이므로 $r=e-v+2=30-20+2=12$이다.

정보

Corollary

Connected planar simple graph $G$가 $e$개의 Edge와 $v$개의 Vertex를 가지며 $v\geq 3$일 때 $e\leq 3v-6$이다.

• Proof
  Region의 Degree 개념에 기반하여(Region의 Degree는 Region의 Bound에 있는 Edge의 개수) Connected planar simple graph는 Plane을 $r$개의 Region으로 나눈다.
  각 Region의 Degree는 최소 3이 된다(평면 도형은 Triangle부터).
  Region의 Degree의 합은 Graph의 Edge수의 정확히 두 배이므로 각 Region의 Degree가 3 이상이므로 $2e=\sum_{r\in R}\deg(R)\geq 3$이 성립한다.
  따라서 $\frac{2}{3}e\geq r$ 이며 Euler's fomula를 사용하여 $r=e-v+2$이므로 $e-v+2\leq \frac{2}{3}e$를 얻는다.
  정리하여 $e\leq 3v-6$임을 알 수 있다.

정보

Corollary

Connected planar simple graph $G$가 Degree 5를 초과하는 Vertex를 가질 수 없다.

• Proof
  $G$가 Vertex의 개수가 1, 2일 경우 참이다.
  $G$에 Vertex가 3개 이상 있을 경우 위 Corollary에 의해 $e\leq 3v-6$이므로 $2e\leq 6v-12$이다.
  Vertex의 Degree가 6 이상이라면 Handshaking theorem에 따라 $2e=\sum_{v\in V} \deg(v)$가 성립하므로 $2e\geq 6v$가 성립하게 되나 앞전 Corollary와 Contradiction이 되므로 Degree는 5를 초과할 수 없다.

정보

Corollary

Connected planar simple graph가 $e$개의 Edge와 $v$개의 Vertex를 가질 때 $v\geq 3$이고 길이가 3인 Circuit$G$이 존재하지 않을 경우 $e\leq 2v-4$이다.

• Proof
  Region의 Degree 개념에 기반해 구한 Colorary에서 원래 최소 3이였으나 이는 Triangle(즉, 길이가 3인 circuit의 존재)을 의미하므로 Degree가 4 이상이므로 $2e=\sum_{r\in R}\deg(R)\geq 4$를 의미하며 $e-v+2\leq \frac{1}{2}e$임을 얻기에 정리하여 $e\leq 2v-4$임을 알 수 있다.

팁

Example

$K_{3,3}$이 Nonplanar임을 증명

• Solution
  $K_{3,3}$은 길이가 3인 Circuit이 없으므로 6개의 Vertex와 9개의 Edge를 가졌기에 $9\leq 2v-4=8$이므로 거짓이므로 Nonplanar이다.

Kuratowski's Theorem

어떤 Graph가 $K_{3,3}$이나 $K_5$를 Subgraph로 가질 경우 그 Graph는 Nonplanar graph가 된다.
만약 Graph가 Planar graph라면 Edge $\{u,v\}$를 제거하고 추가 Vertex $w$를 추가하여 Edge $\{u,w\},\{w,v\}$를 추가하여 얻은 Graph 또한 Planar graph이다.
이러한 Operation을 Elementary subdivision(초등 분할)이라 하고 Graph $G_1=(V_1,E_1)$과 $G_2=(V_2,E_2)$는 동일한 Graph의 Elementary subdivision으로 얻을 수 있을 때 Homeomorphic(동형)이라고 한다.

팁

Example

위 세 Graph가 Homeomorphic임을 증명

• Solution
  이 세 Graph는 $G_1$에서 Elementary subdivision을 통해 얻을 수 있어 Homeomorphic이다.
  $G_1$은 Elementary subdivision의 Empty sequence를 통해 자신으로 부터 얻을 수 있고 $G_2$를 얻기 위해서 $G_1$에서 $\{a,c\}$를 제거한 후 Vertex $f$를 추가한 후 $\{a,f\},\{f,c\}$를 추가하고 $\{b,g\}$를 제거한 후 Vertex $g$를 추가하여 $\{g,h\}, \{g,c\}$를 추가한다.
  $G_3$의 경우 $G_1$에서 $\{b,e\}$를 제거하고 Vertex $k,j$를 추가해 $\{b,k\},\{k,j\}, \{j,e\}$를 추가하고 $\{b,c\}$를 제거하고 Vertex $g,i$를 추가하여 $\{b,i\},\{i,g\},\{g,c\}$를 추가하여 얻어 Homeomorphic임을 알 수 있다.

정보

Theorem

Kuratowski's theorem

어떤 Graph가 Nonplanar이기 위해 $K_{3,3},K_5$ 중 하나의 Homeomorphic인 Graph를 Subgraph로 가져야 한다.

팁

Example

위 Petersen graph가 Planar인 지

• Solution
  Petersen graph는 $b$와 $b$가 Endpoint인 세 Edge를 삭제하여 얻은 Subgraph $H$가 $K_{3,3}$과 Homeomorphic이므로 Nonplaner이다.
  
  $\{d,h\}$를 삭제한 후 $\{e,h\}, \{e,d\}$를 추가, $\{e,f\}$를 삭제한 후 $\{a,e\}, \{a,j\}$를 추가, $\{i,j\}$ 삭제한 후 $\{g,i\}, \{g,j\}$를 추가하는 Operation을 통해 가능해진다.

9.8. Graph Coloring

Simple graph의 Coloring은 각 vertex에 색을 부여하였을 때 Adjacent vertex끼리 같은 색을 할당하지 않음을 의미한다.

Graph coloring의 최소한의 색깔 수를 Chromatic number라고 하며 이를 Notation $\chi(G)$로 나타낸다.

정보

Theorem

The four color theorem

Planar graph의 Chromatic number는 4를 초과하지 않는다.

팁

Example

Graph $G, H$의 Chromatic number

• Solution
  Graph $G$의 Chromatic number의 수는 3이 된다.
  이유로 Vertex $a,b,c$를 서로 다른 색으로 칠해야 하기 때문이다.
  $G$를 세 가지 색으로 칠할 수 있는지 확인하기 위해 각각 색을 할당할 경우 $d$는 $b, c$와 Adjacent이므로 $a$의 색으로, $g$는 $a$와 다른 색으로 칠해진 두 Vertex와 Adjacent이므로 $a$와 같은 색으로 칠해 증명할 수 있다.
  Graph $H$의 Chomatic number의 수는 추가된 Region에 의해서 $a,g$가 Adjacent이므로 Chromatic number는 4가 된다.

팁

Simple Example

Chromatic number of $K_n=n$

• Solution
  모든 Vertex가 Adjacent이므로 $\chi(K_n)=n$이 된다.

Chromatic number of $K_{m,n}=2$

• Solution
  모든 Vertex가 Adjacent 하지 않는 Group이 두 개 이므로 $\chi(K_{m,n})=2$가 된다.

Chromatic number of $C_n=2+(n\%2)$

• Solution
  Cycle $C_n$은 짝수 일 경우 번갈아가며 색칠하여 2, 홀수 일 경우 최대 3개의 색이 필요하다.

Applications of Graph Colorings

Graph coloring은 Scheduling과 Assignment에 관한 다양한 Application이 존재하나 효율적인 Algorithm이 발견되지 않았다.

팁

Example

기말 시험이 대학에서 학생이 동시에 두 개의 시험을 보지 않도록 Scheduling

• Solution
  Graph model을 사용해 Vertex는 과목, Edge는 과목을 듣는 공통 학생이 존재할 때 존재한다면 이 때 Graph coloring을 통하여 문제를 해결할 수 있다.
  
  예시로 Graph가 과목 Vertex set$\{1,2,3,4,5,6,7\}$이 존재하고 Edge가 위와 같이 생성되었다면 Coloring을 통해 총 필요한 구분 수는 4임을 알 수 있다.\