Bài giảng Tin học: Chu Trình Hamilton

7.5. CHU TRÌNH HAMILTONTrò chơi Hamilton.Khái niệm chu trình Hamilton.Tính chất Hamilton trong một số lớp đồ thị.Điều kiện tồn tại chu trình Hamilton1TRÒ CHƠI HAMILTON	Năm 1857 W. R. Hamilton đưa trò chơi sau đây:Trên mỗi đỉnh trong số 20 đỉnh của khối đa diện ngũgiác đều 12 mặt ghi tên một thành phố trên thế giớiHãy tìm cách đi bằng các cạnh của khối đa diện để qua tất cả các thành phố, mỗi thành phố đúng một lần.2KHÁI NIỆM CHU TRÌNH HAMILTONĐịnh nghĩa 7.2Đườ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.3VÍ DỤ 7.5Tổ 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ầnBài toán mã đi tuần: cho con mã đi trên bàn cờ vua sao cho nó đi qua mỗi ô đúng một lần. Đường Hamilton biểu diễn nước đi của con mã trên bàn cờ 3x4123456789101112H = [ 8, 10, 1, 7, 9, 2, 11, 5, 3, 12, 6, 4 ] 4TÍNH CHẤT HAMILTON TRONG MỘT SỐ LỚP ĐỒ THỊ1. Tính chất Hamilton trong lớp đồ thị đầy đủ.2. Tính chất Hamilton trong lớp đồ thị có đồ thị riêng bậc 1.5TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ ĐẦY ĐỦĐịnh lý 7.3 (Rédei)	Đồ thị đầy đủ luôn có đường đi HamiltonadbceH = [ a, b, d, c, e ]6TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ ĐẦY ĐỦ (tiếp)Chứng minh định lý 7.3:Chứng minh bằng quy nạp theo số đỉnh n của đồ thịcó hướng G.- n = 1, 2: hiển nhiên.(n)  (n+1): G là đồ thị đầy đủ n+1 đỉnh, 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à đầy đủ nên có đường Hamilton: (H) = .7TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ ĐẦY ĐỦ (tiếp)Chứng minh định lý 7.3:ax1xixi+1xnĐường đi Hamilton8TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ ĐẦY ĐỦ (tiếp)Nếu G’ có cạnh (xn,a) thì đường sẽ là đường Hamilton trong G.Nếu G’ có cạnh (a,x1) thì đường sẽ là đường Hamilton trong G.Ngược lại, thì hai cạnh (a,xn) và (x1,a) ngược hướng nhau. Khi đó, có cặp cạnh sát nhau nhưng ngược hướng nhau, chẳng hạn (xi,a) và (a,xi+1). Đường đi sẽ là đường Hamilton trong G.  9TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1Đồ thị bậc 1Là đồ thị mà mỗi đỉnh có đúng một cạnh vào và một cạnh ra.Ví dụ: Chu trình Hamilton (nếu có) của G là đồ thị riêng bậc 1 của G	Định lý 7.4Đồ thị G = (V, F) có đồ thị riêng bậc 1 khi và chỉ khi	 B  V, | B |  | F(B) |.10TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)Chứng minh định lýGiả sử V = {a1, a2, ... , an} là tập đỉnh của đồ thịLập tập V’ = {b1, b2, ... , bn} sao cho V  V’ = . Xây dựng đồ thị hai phần H = (V, V’, F’) mà:	bj  F’(ai)  aj  F(ai).11Chứng minh định lý:Nếu G có đồ thị riêng bậc 1 là G1 = (V, F1)Xác định tập cạnh W: (ai,bj)  W  aj  F1(ai)W là cặp ghép n cạnh trong H.Ngược lại: ứng với một cặp ghép n cạnh trong H, cómột đồ thị riêng bậc 1 trong G. TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)12Chứng minh định lý:Theo Hệ quả 5.4: | W | = n  | V | - d0  d0 = 0.Mặt khác d0 = max {| B | - | F’(B) | B  V}	 = max {| B | - | F(B) | B  V} = 0. Suy ra: | B |  | F(B) |. TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)13Xét đồ thị có hướng:Đặt V’ = {1, 2, 3, 4}, xây dựng đồ thị hai phần H.Chọn cặp ghép lớn nhất W = {(a, 2), (b, 3), (c, 4), (d, 1)}. Từ đó, xây dựng được chu trình Hamilton: [a, b, c, d]. VÍ DỤ 7.6acdb1ad4c32b1ad4c32b14Hệ quả 7.3:	Nếu đồ thị có chu trình Hamilton thì:B  V , | B |  | F(B) |.	Từ hệ quả suy ra: 	Nếu trong G có tập B  V mà | B | > | F(B) | thì G không có chu trình Hamilton.TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)15Hệ quả 7.4:Giả sử đồ thị vô hướng G có đường đi Hamilton vàd = max {| B | - | F(B) |B  V}. Khi đó, số d  {0, 1}.TÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)16Chứng minh hệ quả:Giả sử H = là đường đi Hamilton trongG. Nếu trong G có cạnh (b,a) thì G có chu trình Hamilton, do đó, theo hệ quả 7.8, d = 0.Nếu không có cạnh (b,a):Thêm cạnh (b,a) vào G, nhận được đồ thị G’G’ có d’ = 0.d  d' +1, do chỉ thêm cạnh mà không thêm đỉnh. Suy ra d  1. Suy ra: Nếu d  2 thì G không có đường đi HamiltonTÍNH CHẤT HAMILTON TRONG LỚP ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)177.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTONBổ đề 7.1Giả sử đồ thị G có đường đi đơn vô hướng cực đại và r(a0) + r(aq)  q +1. Thế thì,G’ tạo bởi tập đỉnh {a0, a1, ..., aq} có chu trình vô hướng Hamilton. 187.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh bổ đề:Ký hiệu r'(a) là bậc của đỉnh a trong G’.Vì là đường đơn cực đại nên r'(a0) = r(a0) và r'(aq) = r(aq).Giả sử a0 kề với k đỉnh trên đường đi là: 	a1 , ai2 , ... , aik ( r(a0) = k )Nếu a0 kề với aq thì G’ có chu trình vô hướng Hamilton.197.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh bổ đề:	- Nếu aq không kề với các đỉnh a0 , ai2-1 , ... , aik-1 thì r(aq)  q - k. Do đó: r(a0) + r(aq)  q, trái với giả thiết. Vậy tồn tại đỉnh ai-1 sao cho a0 kề với ai và aq kề với ai-1. Khi đó [a0 , ai , ... , aq , ai-1, ..., a0] là một chu trình vô hướng của G’. a0ai-1aia0207.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Bổ đề 7.2Giả sử G là đồ thị liên thông và các đỉnh trên đườngđi đơn vô hướng dài nhất trong G tạo nên đồ thị conG’có chu trình Hamilton H. Khi đó, H là chu trình Hamilton trong G.217.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh bổ đề:Chứng minh đồ thị con G’ chính là đồ thị G.Phản chứng: Giả sử tồn tại đỉnh a G nhưng a  G’. Do G liên thông nên tồn tại đường đi vô hướng D = trong G.b  G’ và a  G’, do đó tồn tại ai là đỉnh đầu tiên	của D không thuộc G’.227.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh bổ đề:	Xây dựng đường D’: Bỏ ra khỏi chu trình Hamilton H cạnh kề với ai-1 và thêm vào cạnh (ai-1, ai). 	Đường D’ có độ dài bằng số đỉnh của G’.	Mặt khác, đường đơn dài nhất trong G có độ dài bằng số đỉnh của G’ trừ 1. Suy ra mâu thuẫn.	Vậy đồ thị con G’ chính là đồ thị G. 237.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Định lý 7.5Giả sử đồ thị G có n đỉnh.Nếu  a, b  V, r(a) + r(b)  n-1 thì G có đường đi vô hướng Hamilton.2) Nếu  a, b  V, r(a) + r(b)  n thì G có chu trình vô hướng Hamilton.247.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh định lý:Giả sử D = là đường đi đơn vô hướng dài nhất của G. 	- Nếu q = n-1 thì D là đường đi Hamilton của G. - Nếu q  n-2 thì r(x0) + r(xq)  n-1  q +1. Theo Bổ đề 7.10 , đồ thị con G’ tạo bởi tập đỉnh{x0 , ..., xq} có chu trình vô hướng Hamilton H = [y0 , y1 , ... , yq]. 257.6. ĐIỀUKIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh định lý:	Vì q  n-2 nên có ít nhất một đỉnh y của G nằm ngoài chu trình H. Suy ra, y được nối với yj nào đó bằng một đường đi đơn vô hướng. 	Từ đó: là đường đi đơn vô hướng có độ dài lớn hơn q+1. Mâu thuẫn với tính cực đại của đường đi . 	Do đó: q = n -1. Đồ thị G luôn có đường đi vô hướng Hamilton267.6. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Chứng minh định lý:2) Theo 1) đồ thị G có đường đi đơn vô hướng dài nhất chứa n đỉnh . 	Mặt khác, r(y0) + r(yn-1)  n = (n-1) +1.	Theo Bổ đề 7.10, đồ thị con G’ sinh bởi tập đỉnh {y0 , y1 , ... , yn-1} có chu trình vô hướng Hamilton, và do đó G có chu trình vô hướng Hamilton. 27VÍ DỤ 7.7Xét đồ thị có hướng:Đồ thị trên thỏa mãn điều kiện 2), do đó có chu trìnhvô hướng Hamilton.Nếu bỏ cạnh (c,d) thì điều kiện 1) thỏa mãn, điềukiên 2) không thỏa mãn, đồ thị chỉ có đường đi vôhướng Hamilton.abdc287.6. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Hệ quả 7.5 (Dirac)	Nếu  a  V, r(a)  (n/2) thì đồ thị G có chu trình vô hướng Hamilton.Chứng minh:Suy ra từ phần 2) của Định lý 7.5. 297.6. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)Nhận xét:Đồ thị có đỉnh bậc ≤ 1 thì không có chu trình Hamilton.Nếu đồ thị có các đỉnh đều có bậc  2 và có một đỉnh bậc 2 thì mọi chu trình Hamilton (nếu có) phải đi qua 2 cạnh kề của đỉnh này.Nếu trong đồ thị có một đỉnh kề với 3 đỉnh bậc 2 thì không có chu trình Hamilton.307.6. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH HAMILTON (tiếp)	4. Nếu đỉnh a có 2 đỉnh kề bậc 2 là b và c thì mọi cạnh (a, x), x  {b,c} sẽ không thuộc chu trình Hamilton nào.	5. Đồ thị có đường đi vô hướng , với k < n và các đỉnh trên đường đi (trừ a1 và ak) đều có bậc 2 thì không có chu trình Hamilton đi qua cạnh (a1, ak).	6. Đồ thị hai phần G = (V1,V2, F) với |V1|  |V2| không có chu trình Hamilton.31