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

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

1. Chương 3 Đồ thị Euler và đồ thị Hamilton
2. Phần 3.1. Đồ thị Euler
3. Bài toán 7 cái cầu ở TP Konigsberg A B D C Graph Theory 6/14/2021 3
4. Bài toán 7 cái cầu ở Tp. Konigsberg A A Mô hình thành Đồ thị B B D D C C Graph Theory 6/14/2021 4
5. Đặt vấn đề (tt) n Hãy vẽ các hình sau bằng đúng một nét bút (không được nhấc bút lên trong khi vẽ) Không vẽ được bằng 1 nét. Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 2 nét. Tối thiểu phải vẽ bằng 6 nét. Lý thuyết đồ thị 6/14/2021 5
6. Đặt vấn đề (tt) n Hãy vẽ các hình sau bằng đúng một nét bút (không được nhấc bút lên trong khi vẽ) Lý thuyết đồ thị 6/14/2021 6
7. Đường đi, chu trình Euler n Xét đồ thị G = . u Một đường đi trên đồ thị được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. u Một chu trình trên đồ thị được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. VD: Đồ thị sau có các đường đi Euler là: d1: 1 2 3 4 2 5 4 1 5 3 d2: 1 2 4 3 2 5 1 4 5 2 4 1 5 Lý thuyết đồ thị 6/14/2021 7
8. Đường đi, chu trình Euler (tt) VD: Đồ thị sau có các chu trình Euler là: 3 d1: 1 2 3 4 2 5 4 1 5 6 1 d2: 1 2 4 3 2 5 1 4 5 6 1 2 4 1 5 6 Lý thuyết đồ thị 6/14/2021 8
9. Đồ thị Euler n Xét đồ thị G = . u Đồ thị G được gọi là đồ thị Euler nếu và chỉ nếu tồn tại một chu trình Euler trong G. u Đồ thị G được gọi là đồ thị nửa Euler nếu và chỉ nếu tồn tại một đường đi Euler trong G. 3 3 2 4 2 4 Đồ thị Euler (hiển nhiên cũng là đồ thị nửa Euler). 1 5 1 5 Đồ thị nửa Euler 6 Lý thuyết đồ thị 6/14/2021 9
10. Định lý Euler n Định lý. Đồ thị vô hướng, liên thông G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của nó đều có bậc chẵn. n Hệ quả. Đồ thị vô hướng, liên thông G là đồ thị nửa Euler nếu và chỉ nếu nó có không quá hai đỉnh bậc lẻ. Lý thuyết đồ thị 6/14/2021 10
11. Thuật toán xây dựng chu trình Euler n Thuật toán Fleury u Bắt đầu từ một đỉnh bất kỳ của đồ thị và tuân theo các quy tắc sau: l Quy tắc 1. Khi đi qua một cạnh nào đó thì xóa nó đi và xóa luôn đỉnh cô lập, nếu có. l Quy tắc 2. Không bao giờ đi qua cầu (cạnh cắt) trừ phi không còn cách nào khác. u VD: Tìm chu trình Euler trong đồ thị sau: a b c d h g f e Lý thuyết đồ thị 6/14/2021 11
12. Định lý Euler cho đồ thị có hướng n Định lý: Xét G là đồ thị có hướng, liên thông mạnh. Khi đó G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của G đều có bán bậc ra bằng bán bậc vào. Lý thuyết đồ thị 6/14/2021 12
13. Phần 3.2. Đồ thị Hamilton
14. Đường đi, chu trình Hamilton n Xét đồ thị G = . u Một đường đi trên đồ thị được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. u Một chu trình trên đồ thị được gọi là chu trình Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. VD: Đồ thị sau có các đường đi và chu trình Euler là: d1: 1 2 3 4 5 3 d2: 1 5 2 4 3 2 4 C1: 1 2 3 4 5 1 C2: 2 5 1 4 3 2 1 5 Lý thuyết đồ thị 6/14/2021 14
15. Đồ thị Hamilton n Xét đồ thị G = . u Đồ thị G được gọi là đồ thị Hamilton nếu và chỉ nếu tồn tại một chu trình Hamilton trong G. u Đồ thị G được gọi là đồ thị nửa Hamilton nếu và chỉ nếu tồn tại một đường đi Hamilton trong G. 3 3 2 4 2 4 Đồ thị Hamilton (hiển nhiên cũng là đồ thị nửa Hamilton). 1 5 1 5 Đồ thị nửa Hamilton 6 Lý thuyết đồ thị 6/14/2021 15
16. Một số kết quả trên đồ thị Hamilton n Định lý (Dirak, 1952). Xét G là đơn đồ thị vô hướng với n đỉnh (n>2). Nếu mỗi đỉnh của G đều có bậc không nhỏ hơn n/2 thì G là đồ thị Hamilton n Định lý (Dirak, 1952). Xét G là đơn đồ thị có hướng, liên thông mạnh với n đỉnh. Nếu mọi đỉnh của G đều có bán bậc ra và bán bậc vào không nhỏ hơn n/2 thì G là đồ thị Hamilton Lý thuyết đồ thị 6/14/2021 16
17. Một số kết quả trên đồ thị Hamilton (tt) n Định lý. u Mọi đồ thị đấu loại là nửa Hamilton u Mọi đồ thị đấu loại, liên thông mạnh là Hamilton n Định lý (Ore, 1960). Cho đồ thị G có n đỉnh. Nếu hai đỉnh không kề nhau bất kỳ của G đều có tổng bậc không nhỏ hơn n thì G là đồ thị Hamilton. Nghĩa là: Lý thuyết đồ thị 6/14/2021 17
18. Kiểm tra đồ thị Hamilton??? n Các quy tắc để xác định chu trình Hamilton (H) của đồ thị: u Quy tắc 1: Nếu có 1 đỉnh bậc 2 thì hai cạnh của đỉnh này bắt buộc phải nằm trong H u Quy tắc 2: Không được có chu trình con (độ dài nhỏ hơn n) trong H u Quy tắc 3: Ứng với một đỉnh nào đó, nếu đã chọn đủ 2 cạnh vào H thì phải loại bỏ tất cả các cạnh còn lại (vì không thể chọn thêm) u Không có đỉnh cô lập hoặc đỉnh treo nào khi áp dụng quy tắc 3. Lý thuyết đồ thị 6/14/2021 18
19. Kiểm tra đồ thị Hamilton (tt) n Đồ thị sau đây có Hamilton không? 1 2 3 5 4 6 7 8 9 Lý thuyết đồ thị 6/14/2021 19