TAILIEUCHUNG - Giáo trình lý thuyết đồ thị - Bài 13

Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 13', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | BÀI 13 . 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. Định nghĩa Đường Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần. Chu trình Hamilton là chu trình đi qua mỗi đỉnh của đồ thị đúng một lần. Ví dụ 1. Tổ chức tour du lịch sao cho người du lịch thăm quan mỗi thắng cảnh trong thành phố đúng một lần. 2. Cho quân mã đi trên bàn cờ vua sao cho nó đi qua mỗi ô đúng một lần bài toán mã đi tuần . Với một đồ thị đã cho đường chu trình Hamilton có thể tồn tại hoặc không. Ví dụ Hình . Đồ thị có và đồ thị không có chu trình Hamilton Định lý Rédei Đồ thị đầy đủ luôn có đường đi Hamilton. Chứng minh Xét đồ thị có hướng G. Ta chứng minh bằng quy nạp theo số đỉnh n của G. n 1 2 hiển nhiên. n n 1 Giả sử G là đồ thị đầy đủ có n 1 đỉnh và đồ thị G xây dựng từ G bằng cách bớt một đỉnh a và các cạnh kề với a. Đồ thị G có n đỉnh và cũng đầy đủ nên theo giả thiết quy nạp nó có đường Hamilton H Xj X2 . Xn Nếu trong G có cạnh xn a thì đường H a sẽ là đường Hamilton. Nếu trong G có cạnh a x1 thì đường a H sẽ là đường Hamilton. Trong trường hợp ngược lại đồ thị G phải có các cạnh a xn và x1 a nghĩa là có các cạnh ngược hướng nhau. Khi đó sẽ phải có ít nhất một cặp cạnh sát nhau nhưng ngược hướng nhau là Xị a và a xi 1 . Hình . Cách tìm đường đi Hamilton Ta có đường X1 . Xị a xi 1 . xn là một đường đi Hamilton của G. Đồ thị G được gọi là đồ thị có bậc 1 nếu tại mỗi đỉnh có đúng một cạnh vào và một cạnh ra. Hiển nhiên chu trình Hamilton là một đồ thị riêng bậc 1 của đồ thị đã cho. Định lý Đồ thị G V F có đồ thị riêng bậc 1 khi và chỉ khi V B -. V B F B . Chứng minh Ký hiệu tập đỉnh của đồ thị là V a1 a2 . an . Lập tập V b1 b2 . bn sao cho VnV .

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton