Bài viết Giải bài toán người du lịch qua phép dẫn về bài toán chu trình Hamilton giới thiệu một thuật toán hiệu quả để giải quyết bài toán trên theo cách dẫn nó về bài toán chu trình Hamilton với thuật toán tìm chu trình Hamilton được đề xuất.

Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P.L. Hammer. Các đồ thị này đã và đang được nghiên cứu nhiều bởi vì chúng có liên quan nhiều đến các vấn đề về tổ hợp. Mặt khác, một trong những vấn đề cơ bản của lý thuyết đồ thị là bài toán Hamilton.

Bài giảng "Lý thuyết đồ thị - Bài 3: Đường đi, chu trình Hamilton" cung cấp cho người học các kiến thức: Đồ thị Hamilton, Đồ thị phẳng – Bài toán tô màu đồ thị, tập cắt – Bài toán luồng cực đại,... Mời các bạn cùng tham khảo nội dung chi tiết.

Luận án nghiên cứu bài toán xác định sự tồn tại của chu trình Hamilton trong đồ thị trên các lớp đồ thị, đánh giá độ phức tạp thời gian đa thức để xác định chu trình Hamilton trong một lớp đồ thị đã khảo sát, đánh giá tính hiệu quả và khả thi của các thuật toán bằng chương trình thực nghiệm trên các đồ thị lớn, đánh giá độ dài của chu trình dài nhất trong lớp đồ thị. Mời các bạn cùng tham khảo.

Chương 2 trình bày nội dung đường đi và chu trình Euler, đường đi và chu trình Hamilton. Chương này giúp người học dùng lý thuyết đồ thị để chứng minh 2 chu trình trên. Mời các bạn tham khảo tài liệu để nắm bắt nội dung chi tiết.

Chu trình Hamilton Năm 1857 W. R. Hamilton, nhà toán học người Ailen đã đưa ra trò chơi sau đây: Trên mỗi đỉnh trong số 20 đỉnh của một khối đa diện 12 mặt ngũ giác đều có ghi tên một thành phố lớn của thế giới. Hãy tìm cách đi bằng các cạnh của khối này để đi qua tất cả các thành phố, mỗi thành phố đúng một lần. Bài toán này đã dẫn tới những khái niệm sau đây.

Chu trình Euler và chu trình Hamilton là hai loại chu trình rất nổi tiếng trong Lý thuyết Đồ thị, mà tên gọi của chúng gắn với tên của các nhà khoa học tìm ra nó. Không những thế, chúng còn nổi tiếng vì một số bài toán liên quan vẫn còn là những bài toán mở. Chu trình Euler Khái niệm chu trình Euler được ra đời từ bài toán nổi tiếng sau đây. Ví dụ 7.1 (Bài toán 7 cây cầu ở Konigsberg): Thành phố Konigsberg thuộc nước Cộng hoà Litva có con sông Pregel chảy qua,...