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

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.
Nội dung trích xuất từ tài liệu:
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 2016CuuDuongThanCong.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 shoCuuDuongThanCong.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ờ 2CuuDuongThanCong.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/tailieudientucnttCuuDuongThanCong.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/tailieudientucnttCuuDuongThanCong.com graph has an Euler circuit. Surprisingly, there are no kno 9 / 24raphs 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 HMPLE 6 Show that neither graph displayed in Figure 11 has aCuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 24 Ví dụ Chứng minh rằng đồ thị đầy đủ Kn có chu trì ...