Chapter 5 Fundamental Properties of Graphs and Digraphs Graph Theory Chapter 5 Fundamental Properties of Graphs and Digraphs 大葉大學 資訊工程系 黃鈴玲 2011.11

Contents 5.1 Bipartite Graphs 5.2 Eulerian Graph 5.3 Hamiltonian Graphs 5.4 Hamiltonian Cycles in Weighted Graphs 5.7 On the Adjacency Matrix of a Digraph

5.1 Bipartite Graphs Definition 5.1 Theorem 5.3 Observation 5.4

5.2 Eulerian Graphs Definition 5.6 Theorem 5.7 Corollary 5.8

edges: 所有黑色邊形成的集合 L: 紅色邊，每一步驟加一條邊 CurrentVertex edges: 所有黑色邊形成的集合 L: 紅色邊，每一步驟加一條邊 e 此時e是G[edges]的bridge， 能不走就不走 重複此做法至結束， 最後一條邊必定是e， Eulerian Circuit就找到了。

HW Find an Eulerian circuit for the following graph. (請試著trace前述的演算法) v2 v1 v3 v7 v4 v5 v6

5.3 Hamiltonian Graphs Example 5.12

Definition 5.13 Note 5.15

4個component 刪掉7點後，最多剩下7個component Thm 5.16: If G is a simple Hamiltonian graph, then for each S  V(G), the number of components of G- S is at most |S|. Example S={a, b, c, d, e, f, g} c a e d b g f 4個component 刪掉7點後，最多剩下7個component

故G- S 最多分成n個component. Thm 5.16: If G is a simple Hamiltonian graph, then for each S  V(G), the number of components of G- S is at most |S|. pf: G is hamiltonian   a hamiltonian cycle C Suppose S={v1, v2, …, vn}. 故G- S 最多分成n個component. v1 v3 vn v2 G1 G3 Gn G2 C …

證明下面兩圖 都不是Hamilton 的方法： 刪除紅點後，變成7個component 紅點只有6個 不是Hamiltonian 刪除紅點後，變成5個component 紅點只有4個 不是Hamiltonian

Lemma 5.19: Corollary 5.20: Corollary 5.21:

上述定理提供了判斷圖形是否 hamiltonian 的一種方法  重複將不相連但degree 和  n 的兩點連一條邊 新圖形是否 hamiltonian 決定了原圖是否hamiltonian 4+3  7 且不相連 4+3  7 且不相連 4+3  7 且不相連 Not hamiltonian!

n=7     若重複一直做，原圖會變成complete graph  原圖是Hamiltonian

 e3 e1 e2 e4 e5 e6 從K6任挑一個 Hamiltonian Cycle C(藍色) e5 e6 e1  e2 e3 e4 重複加邊變成K6 找ut使得 {u0, ut}, {u1, ut+1}為原圖的邊  e1 e2 C= u0, u1, u2, u3, u4, u5, u0 C= u0, u4, u3, u2, u1, u5, u0 u0 u2 u1 u4 u3 u5  e1 e2 將C中加入邊{u0, ut}, {u1, ut+1} 刪除 {u0, u1}及 {ut, ut+1} u0 u1 u2 u3 u4 u5 e6 C e5 C e4 C e3 C e2 C 重複此法至所有紅邊都刪除為止

HW：已知下圖任2個不相鄰的點degree和n， 試用Restricted Hamiltonian Cycle Algorithm找出一條 Hamiltonian cycle. v0 v1 v5 v2 v4 v3

5.4 Hamiltonian Cycles in Weighted Graphs Traveling Salesman Problem (TSP): Suppose that a salesman is required to make a round trip through a given collection of n(3) cities. What route should he take to minimize the total distance traveled? (本節以下內容取材自另一本課本)  G: connected weighted graph, vi  V(G): the cities, w(vivj) of edge vivj: the distance to travel directly between vi and vj . (Assume that G is complete) ※ TSP asks for a Hamiltonian cycle of minimum weight.

∵TSP is a NP-complete problem ∴改成 find low weight 的 HC TSP: Given a weighted complete graph G and a positive constant B, does there exist a hamiltonian cycle C in G so that w(C)  B? 此處提供兩種作法 前提: 需先符合triangle inequality (三角不等式) w(vi,vk)  w(vi,vj) + w(vj,vk) vi vj vk

Algorithm TSP-1 (a greedy algorithm) [ To determine a low weight HC in a weighted complete graph G of order(點數) p3 satisfying the triangle inequality. ] n  1. (n is the cycle length) Select any vertex of G to form Cn. (Cn剛開始只有一個點) If n < p, then find a vertex vn not on Cn s.t. w(unvn) is minimum for some un is on Cn, and go to Step 4. Otherwise, Cn is the desired HC. Let Cn+1 be the (n+1)-cycle obtained by inserting vn immediately before un on Cn. n  n +1 and return to Step 3.

1. C1: v1 2. ∵ v2, …, v6中，w(v1v4)最小 ∴C2: v1v4v1 3. v1 v2 v3 v4 v5 G若不是complete graph，要先加邊，使之成為complete。 加邊方式：若u,v兩點不相連，就加uv這條邊， 邊的權重為G中u-v shortest path上的權重和。 1. C1: v1 2. ∵ v2, …, v6中，w(v1v4)最小 ∴C2: v1v4v1 3. ∵ w(v3v4) 最小 ∴C3: v1v3v4v1 (加在要連的點之前) v1 v2 v3 v4 v5 v6 v1 v2 v3 v4 v5 v6 v2 v3 v5 v6 v1 v4

C6的 weight 總和為24, 而min weight 為18. v2 v5 v6 v1 v3 v4 3 7 3 3 4 4 4 5 5 4. ∵ w(v1v2) 最小 ∴C4: v1v3v4v2v1 v5 v1 v2 v3 v4 v6 7 5 4 6. 5. 7 3 5 5 4 4 v5 v6 v1 v2 v3 v4 C5: v1v3v4v2v6v1 C6: v1v5v3v4v2v6v1 C6的 weight 總和為24, 而min weight 為18. 原圖G若不是complete， 找到的HC要對應變成G 的closed walk 若改選別的點當C1,可能 weight 總和更小.

Theorem C : a HC given by Algorithm TSP-1 Cm : min weight HC  w(C)  2  w(Cm) (Algorithm TSP-1不保證能找出min HC, 但用 Algorithm TSP-1 找出的cycle 其weight 不會 大於 min HC 的兩倍.)

AlgorithmTSP-2 (利用 min spanning tree) [ To determine a low weight HC in a weighted complete graph G of order p3 satisfying the triangle inequality. ] 1. Find a min spanning tree T of G. 2. Conduct a depth-first search of T. (起點為 T 的leaf) 3. If vi1, vi2, …, vip is the order in which the vertices of T are visited in step 2, then output the hamiltonian cycle vi1, vi2, …, vip, vi1. (Algorithm TSP-2 找出的cycle 其 weight 也不會大於 min HC 的兩倍.)

A min spanning tree T (a) 3 v2 v5 v4 v3 v1 v6 A min spanning tree T (a) 3 4 2 1  v2 v5 v4 v3 v1 v6 A HC (c) 5 3 4 2 1      A depth-first search 從 leaf v2開始 (b) weight 總和為19 C: v2,v1,v4,v3,v5,v6,v2

Exercise Use Alg. TSP-1 and TSP-2 to find a closed walk whose weight does not exceed twice the weight of a shortest closed walk in the given weighted graph G. G v2 v5 v4 v3 v1 1 3 2 5 4 Sol: 先把 G 變成 complete v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 0 4 2 5 1 4 0 3 7 3 2 3 0 5 3 5 7 5 0 4 1 3 3 4 0 G v2 v5 v4 v3 v1 4 1 3 2 5 7

5.7 On the Adjacency Matrix of a Digraph u1 u2 u3 u4 u5 u1 u2 u3 u4 u5

u1 u2 u3 u4 u5 u1 u2 u3 u4 u5 u1 u2 u3 u4 u5 u1 u2 u3 u4 u5 有 2 條從u3到u4且長度為 3 的walk: u3  u1  u3  u4 u3  u4  u4  u4 (點及邊可重複的路徑) e2 e3 e5 e6

A(G)k 矩陣中的元素aij(k)， 代表了由ui節點到uj節點且長度為 k 的walk數 Theorem 5.39 A(G)k 矩陣中的元素aij(k)， 代表了由ui節點到uj節點且長度為 k 的walk數