Bài giảng Toán rời rạc: Đồ thị Hamilton - Trần Vĩnh Đức

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

38
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Đồ thị Hamilton cung cấp cho người học những nội dung kiến thức như: Định nghĩa (Đồ thị nửa Hamilton), định lý (Ore), chứng minh định lý Ore, định lý (Dirac), mã Gray. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Đồ thị Hamilton - Trần Vĩnh Đức

Đồ thị Hamilton Trần Vĩnh Đức Ngày 11 tháng 3 năm 2016 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 24
Tài liệu tham khảo ▶ Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, NXB ĐHQG Hà Nội, 2004. ▶ Douglas B. West. Introduction to Graph Theory. 2nd Edition, 2000. ▶ K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch Tiếng Việt) CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 24
Đi vòng quanh thế giới 10.5 Euler (a) (b) FIGU FIGURE 8 Hamilton’s “A Voyage Round the the “A World” Puzzle. World Because the author cannot supply each reader with a wooden solid w will consider the equivalent question: Is there a circuit in the graph sho CuuDuongThanCong.com passes through each vertex exactly once? This solves the puzzle because https://fb.com/tailieudientucntt 3 / 24 th
Con Mã đi trên bàn cờ CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 24
Con Mã đi trên bàn cờ 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 24
Định nghĩa (Đồ thị nửa Hamilton) ▶ Một đường đi trong đồ thị G được gọi là đường đi Hamilton nếu nó chứa tất cả các đỉnh của G. ▶ Một đồ thị được gọi là đồ thị nửa Hamilton nếu nó có đường đi Hamilton. Nói cách khác, đồ thị nửa Hamilton là đồ thị có đường đi bao trùm. CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 24
Solution: G1 has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in G be seen by noting that any circuit containing every vertex must contain the edge {a but G2 does have a Hamilton path, namely, a, b, c, d. G3 has neither a Hamilton c Ví dụ path, because any path containing all vertices must contain one of the ed Hamilton {e, f }, and {c, d} more than once. Đồ thị nào dưới đây là nửa Hamilton? a b a b a b g e c d c d c e f G1 G2 G3 d FIGURE 10 Three Simple Graphs. CONDITIONS FOR THE EXISTENCE OF HAMILTON CIRCUITS Is there a to determine whether a graph has a Hamilton circuit or path? At first, it might seem should be an easy way to determine this, because there is a simple way to answer question of whether a https://fb.com/tailieudientucntt CuuDuongThanCong.com graph has an Euler circuit. Surprisingly, there are no kno 7 / 24
Định nghĩa (Đồ thị Hamilton) ▶ Một chu trình trong đồ thị G được gọi là chu trình Hamilton nếu nó chứa tất cả các đỉnh của G. ▶ Một đồ thị được gọi là đồ thị Hamilton nếu nó có chu trình Hamilton. Nói cách khác, đồ thị Hamilton là đồ thị có chu trình bao trùm. CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 24
Solution: G1 has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in G be seen by noting that any circuit containing every vertex must contain the edge {a but G2 does have a Hamilton path, namely, a, b, c, d. G3 has neither a Hamilton c Ví dụ path, because any path containing all vertices must contain one of the ed Hamilton {e, f }, and {c, d} more than once. Đồ thị nào dưới đây là Hamilton? a b a b a b g e c d c d c e f G1 G2 G3 d FIGURE 10 Three Simple Graphs. CONDITIONS FOR THE EXISTENCE OF HAMILTON CIRCUITS Is there a to determine whether a graph has a Hamilton circuit or path? At first, it might seem should be an easy way to determine this, because there is a simple way to answer question of whether a https://fb.com/tailieudientucntt CuuDuongThanCong.com graph has an Euler circuit. Surprisingly, there are no kno 9 / 24
raphs Ví dụ Đồ thị nào dưới là Hamilton? Nếu không, có là nửa Hamilton? a d e a d c b c b e G H FIGURE 11 Two Graphs That Do Not Have a H MPLE 6 Show that neither graph displayed in Figure 11 has a CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 24
Ví dụ Chứng minh rằng đồ thị đầy đủ Kn có chu trình Hamilton với mọi n ≥ 3. CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 24
Mệnh đề Nếu G = (V, E) có chu trình Hamilton, vậy thì với mọi tập đỉnh khác rỗng S ⊆ V, đồ thị thu được từ G bằng cách xóa các đỉnh thuộc S chỉ có nhiều nhất |S| thành phần liên thông. Chứng minh. CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 24
Ví dụ Đồ thị sau có phải là Hamilton không? CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 24
Ví dụ Đồ thị sau đây chỉ ra rằng điều kiện cần trước không phải điều kiện đủ. Tại sao? CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 24
Bài tập Alice và Bob nhìn trộm đề thi Toán Rời Rạc của thầy Đức. Alice thấy thầy đang mô tả một đồ thị với 17 đỉnh và 129 cạnh; còn Bob thấy thầy hỏi xem đồ thị này có chu trình Hamilton không. - Bob nói rằng: ”không cần biết chi tiết đồ thị thầy đang vẽ thế nào, chắc chắn đồ thị này có chu trình Hamilton.” - Còn Alice nói: ”Nếu không biết chi tiết thì không thể quyết định được đồ thị này có chu trình Hamilton hay không.” Ai đúng, ai sai? Bạn hãy giải thích. CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 24
Định lý (Ore) Giả sử G là một đơn đồ thị với n ≥ 3 đỉnh thỏa mãn: với mọi cặp đỉnh không liền kề u và v, ta có deg(u) + deg(v) ≥ n, khi đó G là đồ thị Hamilton. CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 24
Chứng minh định lý Ore ▶ Giả sử định lý không đúng. ▶ Tồn tại đồ thị G = (V, E) với n đỉnh và có nhiều cạnh nhất thỏa mãn điều kiện của định lý Ore nhưng không là Hamilton. Tại sao? ▶ Vì G có nhiều cạnh nhất có thể nên đồ thị thu được bằng cách thêm một cạnh mới nối hai đỉnh không kề nhau phải có chu trình Hamilton chứa cạnh thêm đó. Tại sao? ▶ Vậy giữa hai đỉnh bất kỳ trong G có thể nối với nhau bằng một đường Hamilton. CuuDuongThanCong.com https://fb.com/tailieudientucntt 17 / 24
Chứng minh (tiếp) ▶ Vì đồ thị Kn có chu trình Hamilton nên G ̸= Kn . ▶ Vậy tồn tại hai đỉnh v1 và vn không kề nhau trong G, ▶ và tồn tại đường Hamilton: v1 v2 vn−1 vn ... CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 24
Chứng minh (tiếp) ▶ Giả sử v1 kề với k đỉnh là: vi1 , vi2 , · · · , vik và 2 = i1 < i2 < · · · < ik ▶ Đỉnh vn không thể kề với đỉnh vij −1 nào (2 ≤ j ≤ k) vì nếu không sẽ tồn tại chu trình Hamilton: v1 v2 vij −1 vij vn−1 vn ... ... CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 24
Chứng minh (tiếp) v1 v2 vij −1 vij vn−1 vn ... ... ▶ Vậy vn không kề với ít nhất k đỉnh {vi1 −1 , vi2 −1 , . . . , vik −1 , }. Tức là deg(vn ) ≤ n − 1 − k ▶ Nhưng vậy thì n ≤ deg(v1 ) + deg(vn ) ≤ k + (n − 1 − k) = n − 1 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 24