tailieunhanh - Bài giảng Lý thuyết đồ thị - Bài 3: Đường đi, chu trình 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,. nội dung chi tiết. | Bài giảng Lý thuyết đồ thị - Bài 3: Đường đi, chu trình Hamilton Bài 3 Đường đi, chu trình Hamilton . Đồ thị Hamilton Giới thiệu Năm 1857, nhà toán học người Ailen là Hamilton(1805-1865) đưa ra trò chơi “đi vòng quanh thế giới” như sau. Cho một hình thập nhị diện đều (đa diện đều có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình mang tên một thành phố nổi tiếng, mỗi cạnh của hình (nối hai đỉnh) là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ một thành phố, hãy tìm đường đi thăm tất cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chỗ cũ. 3 Giới thiệu (tt) Trước Hamilton, có thể là từ thời Euler, người ta đã biết đến một câu đố hóc búa về “đường đi của con mã trên bàn cờ”. Trên bàn cờ, con mã chỉ có thể đi theo đường chéo của hình chữ nhật 2 x 3 hoặc 3 x 2 ô vuông. Giả sử bàn cờ có 8 x 8 ô vuông. Hãy tìm đường đi của con mã qua được tất cả các ô của bàn cờ, mỗi ô chỉ một lần rồi trở lại ô xuất phát. Khảo sát một lớp đồ thị đặc biệt: đồ thị Hamilton. 4 Đường đi, chu trình Hamilton Xét đồ thị G = . Một đường đi trên đồ thị được gọi là đường đi Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. Một chu trình trên đồ thị được gọi là chu trình Hamilton nếu nó đi qua tất cả các đỉnh, mỗi đỉnh một lần. VD: Đồ thị sau có các đường đi và chu trình Hamilton là: 3 d1: 1 2 3 4 5 d2: 1 5 2 4 3 2 4 C1: 1 2 3 4 5 1 1 5 C2: 2 5 1 4 3 2 5 Đồ thị Hamilton Xét đồ thị G = . Đồ thị G được gọi là đồ thị Hamilton nếu và chỉ nếu tồn tại một chu trình Hamilton trong G. Đồ thị G được gọi là đồ thị nửa Hamilton nếu và chỉ nếu tồn tại một đường đi Hamilton trong G. 3 3 2 4 2 4 Đồ thị Hamilton (hiển nhiên cũng là đồ thị nửa Hamilton). 5 1 5 1 Đồ thị nửa Hamilton 6 6 Một số kết quả trên đồ thị Hamilton Định lý (Dirak, 1952). Xét G là đơn đồ thị vô hướng với n đỉnh (n>2). Nếu mỗi đỉnh của G đều có bậc không nhỏ hơn n/2 thì G là đồ thị Hamilton