tailieunhanh - Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton

Nội dung của tài liệu trình bày về các khái niệm về chu trình Hamilton, đường đi Hamilton, đồ thị Hamilton, thuật toán tìm chu trình Hamilton, tìm đường đi Hamilton, nội dung thực hành, bài tập và tài liệu tham khảo. | Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton Chu trình, Đường đi Hamilton I. Chu trình Hamilton, Đường đi Hamilton, Đồ thị Hamilton 1. Các khái niệm: Chu trình Hamilton là chu trình xuất phát từ 1 đỉnh đi thăm tất cả những đỉnh còn lại mỗi đỉnh đúng 1 lần, cuối cùng quay trở lại đỉnh xuất phát. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. 2. Ví dụ 1: b a c e d Chu trình Hamilton: baedcb Đường đi Hamilton (nhưng không phải là chu trình Hamilton): baecd 3. Ví dụ 2: Xét 3 đơn đồ thị G1, G2, G3 sau: a b e e c d f G1 GVHD: Lương Trần Hy Hiến G2 m G3 Trang 1 Thực hành Lý thuyết đồ thị Chu trình, Đường đi Euler, Haminton G1 có chu trình Hamilton (a, b, c, d, e, a). G2 không có chu trình Hamilton vì deg(a) = 1 nhưng có đường đi Hamilton (a, b, c, d). G3 không có cả chu trình Hamilton lẫn đường đi Hamilton. II. Thuật toán Dưới đây là phần hướng dẫn cài đặt thuật toán liệt kê tất cả các chu trình Hamilton xuất phát từ đỉnh 0, các chu trình Hamilton khác có thể có được bằng cách hoán vị vòng quanh. Lưu ý rằng cho tới nay, người ta vẫn chưa tìm ra một phương pháp nào thực sự hiệu quả hơn phương pháp đệ qui quay lui để tìm dù chỉ một chu trình Hamilton cũng như đường đi Hamilton trong trường hợp đồ thị tổng quát. 1. Tìm chu trình Hamilton Thuật toán gọi đệ qui hàm tìm trong đó thực hiện những công việc sau: B1: Kiểm tra nếu số lần gọi đệ qui > số đỉnh của đồ thị và tồn tại cạnh nối từ x tới đỉnh đầu tiên trong đường đi thì kết luận có chu trình Hamilon. Ngược lại làm tiếp B2 B2: Duyệt qua tất cả các đỉnh i (chưa xét) kề với đỉnh x B3: Lưu lại đỉnh i trong đường đi và đánh dấu i đã xét. Gọi đệ qui tìm tiếp. B4: Bỏ đánh dấu i đã xét. Lưu ý: ban đầu đỉnh 0 được đánh dấu đã xét và được lưu trong đường đi. 2. Tìm đường đi Hamilton Cũng làm tương tự như tìm chu trình chỉ khác trong điều kiện kiểm tra ở B1. Chỉ cần kiểm tra số lần gọi đệ qui == số đỉnh của đồ thị là được. III. Nội