CHU TRÌNH HAMILTON

7.5. CHU TRÌNH HAMILTON
Trò 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 Hamilton
TRÒ 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ới
Hã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.
KHÁ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.
VÍ DỤ 7.5
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
Bà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ờ 3x4
H = [ 8, 10, 1, 7, 9, 2, 11, 5, 3, 12, 6, 4 ]
TÍ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.
TÍNH CHẤT HAMILTON
TRONG LỚP ĐỒ THỊ ĐẦY ĐỦ
Định lý 7.3 (Rédei)
Đồ thị đầy đủ luôn có đường đi Hamilton
TÍ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) = < x1, x2, …, xn >.
TÍNH CHẤT HAMILTON
TRONG LỚP ĐỒ THỊ ĐẦY ĐỦ (tiếp)
Chứng minh định lý 7.3:
Đường đi Hamilton
TÍNH CHẤT HAMILTON
TRONG LỚP ĐỒ THỊ ĐẦY ĐỦ (tiếp)
Nếu G’ có cạnh (xn,a) thì đường < (H), a > sẽ là đường Hamilton trong G.
Nếu G’ có cạnh (a,x1) thì đường < a, (H) > 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 < x1, x2, …, xi, a, xi+1,…, xn > sẽ là đường Hamilton trong G. 


TÍNH CHẤT HAMILTON TRONG LỚP
ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1
Đồ thị bậc 1
Là đồ 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) |.


TÍ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).
Chứ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)
Chứ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)
Xé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.6
Hệ 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)
Hệ 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)
Chứng minh hệ quả:
Giả sử H = < a , ... , b > là đường đi Hamilton trong
G. 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 Hamilton
TÍNH CHẤT HAMILTON TRONG LỚP
ĐỒ THỊ CÓ ĐỒ THỊ RIÊNG BẬC 1 (tiếp)
7.6. ĐIỀUKIỆN TỒN TẠI
CHU TRÌNH HAMILTON
Bổ đề 7.1
Giả sử đồ thị G có đường đi đơn vô hướng cực đại
< a0 , a1 , ... , aq > 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.
7.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ì < a0 , a1 , ... , aq > 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.
7.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’. 
7.6. ĐIỀUKIỆN TỒN TẠI
CHU TRÌNH HAMILTON (tiếp)
Bổ đề 7.2
Giả 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ị con
G’có chu trình Hamilton H.
Khi đó, H là chu trình Hamilton trong G.
7.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 = < b = a0 , a1 , ... , a > 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’.
7.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. 
7.6. ĐIỀUKIỆN TỒN TẠI
CHU TRÌNH HAMILTON (tiếp)
Định lý 7.5
Giả 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.
7.6. ĐIỀUKIỆN TỒN TẠI
CHU TRÌNH HAMILTON (tiếp)
Chứng minh định lý:
Giả sử D = < x0 , ... , xq > 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].

7.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ừ đó: < y, ..., yj, yj-1, ..., y0, yq, ..., yj+2, yj+1 > 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 < x0 , ... , xq >.
Do đó: q = n -1. Đồ thị G luôn có đường đi vô hướng Hamilton
7.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 < y0 , y1 , ... , yn-1 >.
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. 
VÍ DỤ 7.7
Xét đồ thị có hướng:




Đồ thị trên thỏa mãn điều kiện 2), do đó có chu trình
vô hướng Hamilton.
Nếu bỏ cạnh (c,d) thì điều kiện 1) thỏa mãn, điều
kiên 2) không thỏa mãn, đồ thị chỉ có đường đi vô
hướng Hamilton.
7.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. 
7.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.
7.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 < a1 , a2, ..., ak >, 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.