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. Chương 4 Đồ thị Euler và đồ thị Hamilton
2. Đồ thị Euler ⚫ Bài toán mở đầu: – Sông Pregel và cù lao Kneiphof chia thành phố Konigsberg ở nước CH Litva thành 4 vùng đất. – 7 cây cầu nối giữa các vùng đất. B A D Pregel C
3. Đồ thị Euler (tt) ⚫ Bài toán: Liệu có thể đi qua cả 7 cây cầu, mỗi cầu đúng một lần, rồi quay về chỗ xuất phát được hay không? Bài toán đã làm say mê cư dân của thành phố. Họ háo hức đi thử nhưng không thành công. Năm 1736, L.Euler đã chứng minh rằng bài toán không giải được. ⚫ Từ bài toán này đưa đến các khái niệm về đường và chu trình Euler.
4. Đồ thị Euler (tt) ➢ Biểu diễn mỗi vùng đất bằng một đỉnh của một đa đồ thị vô hướng, hai đỉnh có cạnh nối nếu có cầu nối tương ứng. ➢ Bài toán trên đưa về việc tìm một chu trình của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần. Đồ thị biểu diễn bài toán Konigsberg
5. Đồ thị Euler (tt) ⚫ Định nghĩa 7.1 - Đường Euler của đa đồ thị là đường đi qua mỗi cạnh của đồ thị đúng một lần. - Chu trình Euler của đa đồ thị là đường đi qua mỗi cạnh của đồ thị đúng một lần.
6. Đồ thị Euler (tt) ⚫ Ví dụ: 7 a b 1 3 2 4 e 6 9 10 8 d c 5 Chu trình Euler: E = [1, 2, 3, 4, 5, 8, 9, 10, 6, 7]
7. Đồ thị Euler (tt) ⚫ Định lý 7.1 Đồ thị G có chu trình vô hướng Euler khi và chỉ khi mọi đỉnh đều có bậc chẵn. 4 3 5 1 6 2 8 7 9
8. Đồ thị Euler (tt) ⚫ Ví dụ: 4 C1 = [1, 3, 4, 5, 8, 2] 3 5 1 6 C2 = [2, 3, 5, 6, 7] 2 8 C3 = [6, 9, 7, 8] 7 9 C = [ 1, 3, 4, 5, 8, 2, 3, 5, 6, 9, 7, 8, 6, 7, 2 ]
9. Đồ thị Euler (tt) ⚫ Hệ quả 7.1: Đồ thị G có đường đi Euler vô hướng khi và chỉ khi số đỉnh bậc lẻ bằng 2. ⚫ Định lý 7.2: Đồ thị có hướng liên thông G có chu trình Euler có hướng khi và chỉ khi tại mỗi đỉnh số cạnh đi vào bằng số cạnh đi ra:  x V , r-(x) = r+(x) , trong đó: - r-(x): số cạnh đi vào đỉnh x - r+(x): số cạnh đi ra khỏi đỉnh x.
10. Đồ thị Euler (tt) ⚫ Hệ quả 7.2 Đồ thị có hướng liên thông G có đường Euler có hướng khi và chỉ khi trong G có 2 đỉnh a, b thoả mãn: r-(a) = r+(a) - 1 r-(b) = r+(b) + 1 còn các đỉnh khác đều cân bằng.
11. Đồ thị Euler (tt) ⚫ Thuật toán 7.1 Dữ liệu: Đồ thị liên thông G = (V, E) không có đỉnh bậc lẻ được biểu diễn bởi mảng các danh sách kề DK. Kết quả: Chu trình vô hưóng Euler với danh sách các đỉnh nằm trong stack CE.
12. ⚫ Sơ đồ giải thuật tìm chu trình Euler.
13. Thuật toán tìm chu trình Euler Thuật toán: 15 else 1 Begin 2 S :=  ; CE :=  ; 17 begin 3 v := đỉnh tuỳ ý của đồ thị ; 18 v := pop(S) ; push v onto S ; 4. while S  do 19 push v onto CE 6 begin 20 end 7 v := top(S) ; 8 if DK(v)  then 21 end 9 begin 22 End . 10 u := đỉnh đầu tiên trong danh sách DK[v] ; 11 push u onto S ; 12 DK[v] := DK[v] \ {u} ; 13 DK[u] := DK[u] \ {v}; { Xoá cạnh (v,u) } 14 end
14. Thuật toán tìm chu trình Euler (tt) ⚫ Độ phức tạp: Mỗi lần lặp của chu trình (5 - 20): - Hoặc là đặt đỉnh lên stack S và xoá cạnh, - Hoặc chuyển đỉnh từ stack S sang stack CE. Số lần lặp của chu trình không vượt quá số cạnh m. Độ phức tạp tổng thể của thuật toán là O(m).
15. Đồ thị Hamilton ⚫ Định nghĩa 7.2 - Đường Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần. - Chu trình Hamilton là chu trình đi qua mỗi đỉnh của đồ thị đúng một lần.
16. Đồ thị Hamilton (tt) ⚫ Tổ chức tour du lịch sao cho người du lịch thăm quan mỗi thắng cảnh trong thành phố đúng một lần ⚫ Bài toán mã đi tuần: cho con mã đi trên bàn cờ vua sao cho nó đi qua mỗi ô đúng một lần. 1 2 3 4 5 6 7 8 H = [ 8, 10, 1, 7, 9, 2, 11, 5, 3, 12, 6, 4 ] 9 10 11 12 Đường Hamilton biểu diễn nước đi của con mã trên bàn cờ 3x4
17. Đồ thị Hamilton (tt) ⚫ Định lý (Dirac) Nếu  a V, r(a) (n/2) thì đồ thị G có chu trình vô hướng Hamilton. ⚫ Nhận xét: 1. Đồ thị có đỉnh bậc ≤ 1 thì không có chu trình Hamilton. 2. Nếu đồ thị có các đỉnh đều có bậc 2 và có một đỉnh bậc 2 thì mọi chu trình Hamilton (nếu có) phải đi qua 2 cạnh kề của đỉnh này. 3. Nếu trong đồ thị có một đỉnh kề với 3 đỉnh bậc 2 thì không có chu trình Hamilton.