Giáo trình Toán rời rạc - Chương 4: Đồ thị Euler và đồ thị Hamilton

ều biểu diẽn trong mặt phẳng) với chu trình 
Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (đường tô đậm). 
2) Trong một đợt thi đấu bóng bàn có n (n  2) đấu thủ tham gia. Mỗi đấu thủ gặp từng 
đấu thủ khác đúng một lần. Trong thi đấu bóng bàn chỉ có khả năng thắng hoặc thua. 
C 
B D 
A E 
J 
L H 
T 
K I 
O P 
F 
M G 
S 
R 
N Q 
 60 
Chứng minh rằng sau đợt thi đấu có thể xếp tất cả các đấu thủ đứng thành một hàng dọc, 
để người đứng sau thắng người đứng ngay trước anh (chị) ta. 
 Xét đồ thị có hướng G gồm n đỉnh sao cho mỗi đỉnh ứng với một đấu thủ và có 
một cung nối từ đỉnh u đến đỉnh v nếu đấu thủ ứng với u thắng đấu thủ ứng với v. Như 
vậy, đồ thị G có tính chất là với hai đỉnh phân biệt bất kỳ u và v, có một và chỉ một 
trong hai cung (u,v) hoặc (v,u), đồ thị như thế được gọi là đồ thị có hướng đầy đủ. Từ 
Mệnh đề 4.2.2 dưới đây, G là một đồ thị nửa Hamilton. Khi đó đường đi Hamilton trong 
G cho ta sự sắp xếp cần tìm. 
3) Một lời giải về hành trình của con mã trên bàn cờ 8 x 8: 
Đường đi Hamilton tương tự đường đi Euler trong cách phát biểu: Đường đi 
Euler qua mọi cạnh (cung) của đồ thị đúng một lần, đường đi Hamilton qua mọi đỉnh 
của đồ thị đúng một lần. Tuy nhiên, nếu như bài toán tìm đường đi Euler trong một đồ 
thị đã được giải quyết trọn vẹn, dấu hiệu nhận biết một đồ thị Euler là khá đơn giản và 
dễ sử dụng, thì các bài toán về tìm đường đi Hamilton và xác định đồ thị Hamilton lại 
khó hơn rất nhiều. Đường đi Hamilton và đồ thị Hamilton có nhiều ý nghĩa thực tiễn và 
đã được nghiên cứu nhiều, nhưng vẫn còn những khó khăn lớn chưa ai vượt qua được. 
Người ta chỉ mới tìm được một vài điều kiện đủ để nhận biết một lớp rất nhỏ các 
đồ thị Hamilton và đồ thị nửa Hamilton. Sau đây là một vài kết quả. 
4.2.2. Định lý (Rédei): Nếu G là một đồ thị có hướng đầy đủ thì G là đồ thị nửa 
Hamilton. 
 D 
T 
 61 
Chứng minh: Giả sử G=(V,E) là đồ thị có hướng đầy đủ và =(v1,v2, ..., vk-1, vk) là 
đường đi sơ cấp bất kỳ trong đồ thị G. 
-- Nếu  đã đi qua tất cả các đỉnh của G thì nó là một đường đi Hamilton của G. 
-- Nếu trong G còn có đỉnh nằm ngoài , thì ta có thể bổ sung dần các đỉnh này vào  và 
cuối cùng nhận được đường đi Hamilton. 
 Thật vậy, giả sử v là đỉnh tuỳ ý không nằm trên . 
a) Nếu có cung nối v với v1 thì bổ sung v vào đầu của đường đi  để được 1=(v, v1, v2, 
..., vk-1, vk). 
b) Nếu tồn tại chỉ số i (1  i  k-1) mà từ vi có cung nối tới v và từ v có cung nối tới vi+1 
thì ta chen v vào giữa vi và vi+1 để được đường đi sơ cấp 2=(v1, v2, ..., vi, v, vi+1, ..., vk). 
c) Nếu cả hai khả năng trên đều không xảy ra nghĩa là với mọi i (1  i  k) vi đều có 
cung đi tới v. Khi đó bổ sung v vào cuối của đường đi  và được đường đi 3=(v1, v2, 
..., vk-1, vk, v). 
 Nếu đồ thị G có n đỉnh thì sau n-k bổ sung ta sẽ nhận được đường đi Hamilton. 
4.2.3. Định lý (Dirac, 1952): Nếu G là một đơn đồ thị có n đỉnh và mọi đỉnh của G 
đều có bậc không nhỏ hơn 
2
n
 thì G là một đồ thị Hamilton. 
Chứng minh: Định lý được chứng minh bằng phản chứng. Giả sử G không có chu trình 
Hamilton. Ta thêm vào G một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, 
ta được đồ thị G’. Giả sử k (>0) là số tối thiểu các đỉnh cần thiết để G’ chứa một chu 
trình Hamilton. Như vậy, G’ có n+k đỉnh. 
 Gọi P là chu trình Hamilton ayb ...a trong G’, trong đó a và b là các đỉnh của G, 
còn y là một trong các đỉnh mới. Khi đó b không kề với a, vì nếu trái lại thì ta có thể bỏ 
đỉnh y và được chu trình ab ...a, mâu thuẩn với giả thiết về tính chất nhỏ nhất của k. 
 Ngoài ra, nếu a’ là một đỉnh kề nào đó của a (khác với y) và b’ là đỉnh nối tiếp 
ngay a’ trong chu trình P thì b’ không thể là đỉnh kề với b, vì nếu trái lại thì ta có thể 
thay P bởi chu trình aa’ ...bb’ ... a, trong đó không có y, mâu thuẩn với giả thiết về tính 
chất nhỏ nhất của k. 
 Như vậy, với mỗi đỉnh kề với a, ta có một đỉnh không kề với b, tức là số đỉnh 
không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không nhỏ hơn 
2
n
+k). 
a 
b’ 
 a' 
b 
y 
 62 
Mặt khác, theo giả thiết số đỉnh kề với b cũng không nhỏ hơn 
2
n
+k. Vì không có đỉnh 
nào vừa kề với b lại vừa không kề với b, nên số đỉnh của G’ không ít hơn 
2(
2
n
+k)=n+2k, mâu thuẩn với giả thiết là số đỉnh của G’ bằng n+k (k>0). Định lý được 
chứng minh. 
4.2.4. Hệ quả: Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ 
hơn 
2
1n
 thì G là đồ thị nửa Hamilton. 
Chứng minh: Thêm vào G một đỉnh x và nối x với mọi đỉnh của G thì ta nhận được 
đơn đồ thị G’ có n+1 đỉnh và mỗi đỉnh có bậc không nhỏ hơn 
2
1n
. Do đó theo Định lý 
4.2.3, trong G’ có một chu trình Hamilton. Bỏ x ra khỏi chu trình này, ta nhận được 
đường đi Hamilton trong G. 
4.2.5. Định lý (Ore, 1960): Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào 
không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. 
4.2.6. Định lý: Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh cùng 
bằng n (n  2) và bậc của mỗi đỉnh lớn hơn 
2
n
 thì G là một đồ thị Hamilton. 
Thí dụ 4: 
Đồ thị G này có 8 đỉnh, đỉnh nào cũng Đồ thị G’ này có 5 đỉnh bậc 4 và 2 đỉnh 
có bậc 4, nên theo Định lý 4.2.3, G là bậc 2 kề nhau nên tổng số bậc của hai đỉnh 
đồ thị Hamilton. không kề nhau bất kỳ bằng 7 hoặc 8, nên 
 theo Định lý 4.2.5, G’ là đồ thị Hamilton. 
e 
f 
g 
h 
b a c d 
a 
e 
f 
g 
b c 
d
a 
a b b 
d e f 
Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2 
hoặc 3 (> 3/2), nên theo Định lý 4.2.6, nó là đồ 
thị Hamilton. 
 63 
4.2.7. Bài toán sắp xếp chỗ ngồi: 
 Có n đại biểu từ n nước đến dự hội nghị quốc tế. Mỗi ngày họp một lần ngồi 
quanh một bàn tròn. Hỏi phải bố trí bao nhiêu ngày và bố trí như thế nào sao cho trong 
mỗi ngày, mỗi người có hai người kế bên là bạn mới. Lưu ý rằng n người đều muốn làm 
quen với nhau. 
 Xét đồ thị gồm n đỉnh, mỗi đỉnh ứng với mỗi người dự hội nghị, hai đỉnh kề nhau 
khi hai đại biểu tương ứng muốn làm quen với nhau. Như vậy, ta có đồ thị đầy đủ Kn. 
Đồ thị này là Hamilton và rõ ràng mỗi chu trình Hamilton là một cách sắp xếp như yêu 
cầu của bài toán. Bái toán trở thành tìm các chu trình Hamilton phân biệt của đồ thị đầy 
đủ Kn (hai chu trình Hamilton gọi là phân biệt nếu chúng không có cạnh chung). 
Định lý: Đồ thị đầy đủ Kn với n lẻ và n  3 có đúng 
2
1n
 chu trình Hamilton phân biệt. 
Chứng minh: Kn có 
2
)1( nn
 cạnh và mỗi chu trình Hamilton có n cạnh, nên số chu 
trình Hamilton phân biệt nhiều nhất là 
2
1n
. 
Giả sử các đỉnh của Kn là 1, 2, ..., n. Đặt đỉnh 1 tại tâm của một đường tròn và các đỉnh 
2, ..., n đặt cách đều nhau trên đường tròn (mỗi cung là 3600/(n-1) sao cho đỉnh lẻ nằm ở 
nửa đường tròn trên và đỉnh chẵn nằm ở nửa đường tròn dưới. Ta có ngay chu trình 
Hamilton đầu tiên là 1,2, ..., n,1. Các đỉnh được giữ cố định, xoay khung theo chiều kim 
đồng hồ với các góc quay: 
1
360 0
n
, 2.
1
360 0
n
, 3.
1
360 0
n
, ..., 
2
3n
.
1
360 0
n
, 
ta nhận được 
2
3n
 khung phân biệt với khung đầu tiên. Do đó ta có 
2
1n
 chu trình 
Hamilton phân biệt. 
Thí dụ 5: Giải bài toán sắp xếp chỗ ngồi với n=11. 
 Có (111)/2=5 cách sắp xếp chỗ ngồi phân biệt như sau: 
1 2 3 4 5 6 7 8 9 10 11 1 
1 3 5 2 7 4 9 6 11 8 10 1 
1 5 7 3 9 2 11 4 10 6 8 1 
1 7 9 5 11 3 10 2 8 4 6 1 
1 2 
3 
4 
5 
n 
 64 
1 9 11 7 10 5 8 3 6 2 4 1 
BÀI TẬP CHƯƠNG IV: 
1. Với giá trị nào của n các đồ thị sau đây có chu trình Euler ? 
a) Kn, b) Cn, c) Wn, d) Qn. 
2. Với giá trị nào của m và n các đồ thị phân đôi đầy đủ Km,n có: 
a) chu trình Euler ? b) đường đi Euler ? 
3. Với giá trị nào của m và n các đồ thị phân đôi đầy đủ Km,n có chu trình Hamilton ? 
4. Chứng minh rằng đồ thị lập phương Qn là một đồ thị Hamilton. Vẽ cây liệt kê tất cả 
các chu trình Hamilton của đồ thị lập phương Q3. 
5. Trong một cuộc họp có 15 người mỗi ngày ngồi với nhau quanh một bàn tròn một 
lần. Hỏi có bao nhiêu cách sắp xếp sao cho mỗi lần ngồi họp, mỗi người có hai người 
bên cạnh là bạn mới, và sắp xếp như thế nào ? 
6. Hiệu trưởng mời 2n (n  2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi quen ít nhất 
n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể xếp tất cả các sinh 
viên giỏi ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người mà sinh viên 
đó quen. 
7. Một ông vua đã xây dựng một lâu đài để cất báu vật. Người ta tìm thấy sơ đồ của lâu 
đài (hình sau) với lời dặn: muốn tìm báu vật, chỉ cần từ một trong các phòng bên ngoài 
cùng (số 1, 2, 6, 10, ...), đi qua tất cả các cửa phòng, mỗi cửa chỉ một lần; báu vật được 
giấu sau cửa cuối cùng. 
Hãy tìm nơi giấu báu vật 
 1 2 
3 
7 5 
1
1 
9 
8 6 
4 1
0 
 1 2 
3 
5 7 
9 
1
1 
4 
6 8 
1
0 
1 2 
3 
5 7 
9 
1
1 
4 
6 
1
0 8 
 2 1 
3 
1
1 
9 
7 5 
4 
6 8 
1
0 
1 1
1 
2 
3 
5 7 
9 
4 
6 8 
1
0 
 65 
8. Đồ thị cho trong hình sau gọi là đồ thị Peterson P. 
9. Giải bài toán người phát thư Trung Hoa với đồ thị cho trong hình sau: 
10. Chứng minh rằng đồ thị G cho trong 
hình sau có đường đi Hamilton (từ s đến r) 
nhưng không có chu trình Hamilton. 
2 1 
3 4 5 6 
7 8 9 10 
11 12 13 14 
15 
16 17 18 
19 20 21 
a 
e 
k i 
b g 
f h 
d c 
a) Tìm một đường đi Hamilton trong P. 
b) Chứng minh rằng P \ {v}, với v là một 
đỉnh bất kỳ của P, là một đồ thị Hamilton. 
a 
c 
b 
s 
r 
f 
e 
d 
g 
h 
 66 
11. Cho thí dụ về: 
1) Đồ thị có một chu trình vừa là chu trình Euler vừa là chu trình Hamilton; 
2) Đồ thị có một chu trình Euler và một chu trình Hamilton, nhưng hai chu trình đó 
không trùng nhau; 
3) Đồ thị có 6 đỉnh, là đồ thị Hamilton, nhưng không phải là đồ thị Euler; 
4) Đồ thị có 6 đỉnh, là đồ thị Euler, nhưng không phải là đồ thị Hamilton. 
12. Chứng minh rằng con mã không thể đi qua tất cả các ô của một bàn cờ có 4 x 4 hoặc 
5 x 5 ô vuông, mỗi ô chỉ một lần, rồi trở về chỗ cũ.