tailieunhanh - 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. | Đồ thị Hamilton Trần Vĩnh Đức Ngày 11 tháng 3 năm 2016 https 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 https tailieudientucntt 2 24 Đi vòng quanh thế giới 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 passes through each vertex exactly once This solves the puzzle because https tailieudientucntt 3 24 th Con Mã đi trên bàn cờ https tailieudientucntt 4 24 Con Mã đi trên bàn cờ 2 https 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. https 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 tailieudientucntt .