Bài giảng Lý thuyết đồ thị - Chương 4: Đồ thị Euler và đồ thị Hamilton

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 4: Đồ thị Euler và đồ thị Hamilton

1. Môn học: Lý thuyết đồ thị Chương 4: Đồ thị Euler và đồ thị Hamilton Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
2. Nội dung I. Đồ thị Euler II. Đồ thị Hamilton Chương 4 – Đồ thị Euler và Hamilton 2 Lý thuyết đồ thị
3. I. Đồ thị Euler Đồ thị Euler 1. Định nghĩa 2. Định lý Euler 3. Giải thuật xây dựng chu trình Euler Chương 4 – Đồ thị Euler và Hamilton 3
4. I.1. Định nghĩa ™Giả sử G là đơn (đa) đồ thị vô (có) hướng: ƒ Chu trình Euler trong G là chu trình đơn đi qua tất cả các cạnh của đồ thị. Nếu G có chu trình Euler thì G được gọi là đồ thị Euler. ƒ Đường đi Euler trong G là đường đi đơn qua tất cả các cạnh của đồ thị. Nếu G có đường đi Euler thì G được gọi là đồ thị nửa Euler. Đồ thị Euler Đồ thị nửa Euler Chương 4 – Đồ thị Euler và Hamilton 4
5. I.2. Định lý ™Định lý 1 ƒ Đồ thị vô hướng, liên thông G=(V, E) có chu trình Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. ™Chứng minh ƒ G có chu trình Euler => Mọi đỉnh đều bậc chẵn ƒ Mọi đỉnh đều bậc chẵn => G có chu trình Euler Chương 4 – Đồ thị Euler và Hamilton 5
6. I.2. Định lý ™Bổ đề ƒ “Cho đồ thị G=(V, E), nếu mọi đỉnh của G có deg(u)≥ 2 thì G có chu trình” ™Chứng minh ? Chương 4 – Đồ thị Euler và Hamilton 6
7. I.2. Định lý ™ Định lý 2: ƒ Đồ thị vô hướng, liên thông G=(V, E) có đường đi Euler mà không có chu trình Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ. ƒ Chứng minh: ? ™ Định lý 3: ƒ Đồ thị có hướng, liên thông yếu G=(V, E) có chu trình Euler khi và chỉ khi mọi đỉnh của G có bán bậc vào bằng bán bậc ra. => Khi G (có hướng) có chu trình Euler thì nó liên thông mạnh. ™ Định lý 4: ƒ Đồ thị có hướng, liên thông yếu G=(V, E) có đường đi Euler nhưng không có chu trình Euler khi và chỉ khi G tồn tại duy nhất hai đỉnh sao cho: deg+(u) – deg-(u) = deg+(v) - deg-(v) = 1, và tất cả các đỉnh còn lại có bán bậc vào bằng bán bậc ra. Chương 4 – Đồ thị Euler và Hamilton 7
8. I.3.Giải thuật x/d chu trình Euler CT, CTcon là các chu trình Bước 1: Đầu tiên, xây dựng 1 chu trình CT trong G Bước 2: H Å ( G \ CT ) \ {Các đỉnh cô lập sau khi bỏ CT khỏi G}. Bước 3: Nếu H vẫn còn cạnh thì đến bước 4. Ngược lại đến bước 8. Bước 4: Xây dựng chu trình con CTcon trong H với đỉnh đầu thuộcchu trình CT Bước 5: H Å ( H \ CTcon) \ {Các đỉnh cô lập sau khi bỏ CTcon khỏi H} Bước 6: CT Å CT ∪ CTcon Bước 7: Đến bước 3. Bước 8: Kết thúc. CT là chu trình Euler Chương 4 – Đồ thị Euler và Hamilton 8
9. I.3.Giải thuật x/d chu trình Euler CT= {3, 7, 8, 9}. H={G\CT)}\{Các đỉnh cô lập} = {1, 2, 4, 5, 6, 10, 11, 12}. + Lần 1: CTcon = {10, 11, 12}. H={H\Hcon}\{Các đỉnh cô lập}={1, 2, 4, 5, 6}. + Lần 2: CTcon={1, 2, 5, 6, 4} H={H\Hcon}\{Các đỉnh cô lập}= Ø. DỪNG. Cuối cùng ta có chu trình Euler: 3, 2, 1, 4, 6, 5, 9, 10, 12, 11, 8, 7. Chương 4 – Đồ thị Euler và Hamilton 9
10. I.3.Giải thuật x/d chu trình Euler ™Cài đặt main(){ STACK = ∅; CE = ∅; /* CE - Chu trình Euler */ Chọn u là 1 đỉnh bất kỳ của đồ thị; STACK ⇐ u; while (STACK != ∅){ x = top(STACK); if (Ke(x) != ∅ ){ y = Đỉnh đầu trong danh sách Ke(x); STACK ⇐ y; Ke(x) = Ke(x) \ {y}; Ke(y) = Ke(y) \ {x}; /* Bỏ cạnh (x,y) */ }else { x ⇐ STACK; CE ⇐ x; } } } Chương 4 – Đồ thị Euler và Hamilton 10
11. I.3.Giải thuật x/d chu trình Euler ™ Cài đặt Đỉnh v Ke(v) 16, 5 25, 6 36, 5 4 6, 5, 7, 8 5 4, 3, 2, 1 6 4, 3, 2, 1 74, 8 84, 7 Chương 4 – Đồ thị Euler và Hamilton 11
12. I.3.Giải thuật x/d chu trình Euler STACK CE 3, 6 ∅ 3, 6, 4 ∅ 3, 6, 4, 5 ∅ 3, 6, 4, 5, 3 ∅ 3, 6, 4, 5 3 3, 6, 4, 5, 2 3 Đỉnh v Ke(v) 3, 6, 4, 5, 2, 6 3 16, 5 3, 6, 4, 5, 2, 6, 1 3 25, 6 3, 6, 4, 5, 2, 6, 1, 5 3 36, 5 3, 6, 4 3, 5, 1, 6, 2, 5 4 6, 5, 7, 8 3, 6, 4, 7 3, 5, 1, 6, 2, 5 5 4, 3, 2, 1 3, 6, 4, 7, 8 3, 5, 1, 6, 2, 5 6 4, 3, 2, 1 3, 6, 4, 7, 8, 4 3, 5, 1, 6, 2, 5 74, 8 ∅ 3, 5, 1, 6, 2, 5, 4, 8, 7, 4, 6, 3 84, 7 Chương 4 – Đồ thị Euler và Hamilton 12
13. I.3.Giải thuật x/d chu trình Euler ™Thuật toán Fleury Bắt đầu từ một đỉnh bất kỳ, đi theo các cạnh của đồ thị theo quy tắc sau: ƒ Qui tắc 1: Xóa các cạnh đã đi qua và các đỉnh cô lập nếu có ƒ Qui tắc 2: Tại mỗi đỉnh, ta chỉ đi qua cầu nếu không còn đường nào khác. Chương 4 – Đồ thị Euler và Hamilton 13
14. Nội dung I. Đồ thị Euler II. Đồ thị Hamilton Chương 4 – Đồ thị Euler và Hamilton 14 Lý thuyết đồ thị
15. II. Đồ thị Hamilton Đồ thị Hamilton 1. Định nghĩa 2. Định lý 3. Giải thuật xây dựng chu trình Hamilton Chương 4 – Đồ thị Euler và Hamilton 15
16. II.1. Định nghĩa ™Lịch sử ƒ “Giả sử ta có một khối 12 mặt, mỗi mặt là một hình ngũ giác đều. Mỗi đỉnh trong 20 đỉnh của khối này được đặt bằng tên của một thành phố. Hãy tìm một đường xuất phát từ một thành phố, đi dọc theo các cạnh của khối, ghé thăm mỗi một trong 19 thành phố còn lại đúng một lần, cuối cùng trở lại thành phố ban đầu” Trong đồ thị hình trên có hay không một chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần ? Chương 4 – Đồ thị Euler và Hamilton 16
17. II.1. Định nghĩa ™Giả sử G là đơn đồ thị vô (có) hướng, ta có các định nghĩa sau: ƒ Chu trình Hamilton là chu trình xuất phát từ một đỉnh, đi thăm tất cả các đỉnh còn lại mỗi đỉnh đúng một lần, cuối cùng quay trở lại đỉnh xuất phát. Đồ thị có chu trình Hamilton gọi là đồ thị Hamilton. ƒ Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Đồ thị có đường đi Hamilton gọi là đồ thị nửa Hamilton. Chương 4 – Đồ thị Euler và Hamilton 17
18. II.2. Định lý ™Nhận biết đồ thị Hamilton ƒ Chưa có chuẩn để nhận biết 1 đồ thị có là Hamilton hay không ƒ Chưa có thuật toán để kiểm tra ƒ Các kết quả thu được ở dạng điều kiện đủ ƒ Nếu G có số cạnh đủ lớn thì G là Hamilton Chương 4 – Đồ thị Euler và Hamilton 18
19. II.2. Định lý ™Định lý Dirac ƒ Cho đồ thị vô hướng G=(V, E) có n đỉnh (n ≥ 3). Nếu mọi đỉnh v của đồ thị đều có deg(v) ≥ n/2 thì G có chu trình Hamilton. Chương 4 – Đồ thị Euler và Hamilton 19
20. II.2. Định lý ™Chứng minh ƒ Thêm vào G k đỉnh mới và nối chúng với tất cả các đỉnh của G ta được G’. ƒ Giả sử k là số nhỏ nhất sao cho G’ là đồ thị Hamilton. ƒ Ta sẽ chứng minh là k = 0. Chương 4 – Đồ thị Euler và Hamilton 20
21. II.2. Định lý ™Chứng minh ƒ Giả sử k > 0, Xét chu trình Hamilton trong G’: v → p → w → v. Với p là 1 trong những đỉnh mới. Ta thấy: • v và w không thể kề nhau ( Ngược lại khi đó có thể bỏ p – vô lý vì k là min ) • Nếu v’ kề v và w’ kề w thì w’ không thể đi liền sau v’. Trái lại: Ta thay v → p → w → v’ → w’ → → v bởi: v → v’ → → w → w’ → → v bỏ qua p. Do đó: Với mỗi đỉnh kề với v ta luôn tìm được 1 đỉnh không kề với w: ƒ Số đỉnh không kề với w ≥ số đỉnh kề với v ≥ (n/2 + k) ƒ Mà số đỉnh kề với w ≥ (n/2 + k) ƒ Do đó |VG’| ≥ (n + 2k) > n + k Vô lý !!! (ĐPCM) Chương 4 – Đồ thị Euler và Hamilton 21
22. II.2. Định lý ™Định lý Dirac cho đồ thị có hướng ƒ Cho đồ thị có hướng, liên thông mạnh G=(V, E) và có n đỉnh. Nếu mọi đỉnh v V đều có và thì G có chu trình Hamilton. Chương 4 – Đồ thị Euler và Hamilton 22
23. II.3. Giải thuật x/d chu trình Hamilton ™Dùng giải thuật quay lui ƒ Bắt đầu từ 1 đỉnh, đi theo con đường dài nhất có thể được (depth – first) ƒ Nếu đường đóchứa mọi đỉnh và có thể nối 2 đỉnh đầu và cuối bằng 1 cạnh thì đólàchu trình Hamilton ƒ Nếu trái lại ta lùi lại một đỉnh để mở con đường theo chiều sâu khác ƒ Cứ tiếp tục quá trình trên cho đến khi thu được chu trình Hamilton. Chương 4 – Đồ thị Euler và Hamilton 23
24. II.3. Giải thuật x/d chu trình Hamilton ™Cài đặt thuật toán void hamilton(k) /*Phát triển dãy X1,X2, ,Xk-1 G=(V,E) được cho bởi Danh Sách kề: Ke(v), v ∈ V */ { for ( y ∈ Ke(Xk-1) ) if ( ( k = = n+1 ) && ( y = = v0 ) ) Xuất(X1, Xn,v0); else if ( Chuaxet[y] ) { Xk = y; Chuaxet[y] = 0; Hamilton(k+1); Chuaxet[y] = 1; //Quay lui } } main(){ for (v ∈ V) Chuaxet[v] = 1; X1 = v0; Chuaxet[v0] = 0; Hamilton(2); } Chương 4 – Đồ thị Euler và Hamilton 24
25. II.3. Giải thuật x/d chu trình Hamilton ™Ví dụ Chương 4 – Đồ thị Euler và Hamilton 25
26. II.3. Giải thuật x/d chu trình Hamilton ™Ví dụ Chương 4 – Đồ thị Euler và Hamilton 26