Luận văn tốt nghiệp Phan Thanh Long
Chơng 3
Chu trình, đờng đi Euler và
Hamilton trong đồ thị
Lý thuyết về chu trình, đờng đi Euler và Hamilton đã có từ lâu và đợc nghiên
cứu nhiều. Ta có thể bắt gặp nhiều bài toán trong thực tiễn mà có thể sử dụng các
lý thuyết về chu trình, đờng đi Euler và Hamilton để giải quyết, ví dụ sử dụng lý
thuyết đờng đi, chu trình Euler để tìm hành trình đờng đi cho ngời phát th, cho xe
rửa đờng... sao cho hành trình là tối u nhất. Hoặc là trong một hệ thống mạng, một
máy đơn cần gửi 1 thông điệp đến tất cả các máy còn lại vậy thì đờng truyền tin sẽ
đi nh thế nào để cho hiệu quả nhất, bài toán này có thể đợc giải quyết bằng cách
vận dụng các lý thuyết chu trình và đờng đi Hamilton.
I. Chu trình và đờng đi Euler
1. Chu trình Euler
1.1 Định nghĩa
Cho đồ thị vô hớng G = <X,U>. Một chu trình trong đồ thị G đợc gọi là chu
trình Euler nếu nó đi qua tất cả các cạnh của G và đi qua mỗi cạnh đúng một lần.
Định lý 1: Đồ thị vô hớng G = <X,U> có chu trình Euler khi và chỉ khi G là liên
thông và bậc của tất cả các đỉnh trong đồ thị G là số chẵn.
Chứng minh
- Điều kiện cần: Giả sử đồ thị G = <X, U> có chu trình Euler. Ta cần chứng minh
G là đồ thị liên thông và với mỗi x X có m(x) = 2k với k là một số nguyên d-
ơng nào đó.
Thật vậy, giả sử G = <X, U> không liên thông hay G có ít nhất hai thành phần
liên thông G
1
= <X
1
, U
1
> và G

với định nghĩa của . Chứng tỏ đồ thị G = <X, U> là liên thông.
Bây giờ ta chứng minh mỗi đỉnh x X trong G đều có bậc chẵn, tức là cần chỉ ra
m(x) = 2k, với k {1,2,...}. Trớc hết thấy rằng k 0 bởi vì nếu k = 0 thì x là điểm
cô lập trong G, tức là G không liên thông, trái với điều đã chỉ ra. Giả sử ngợc lại
35
Luận văn tốt nghiệp Phan Thanh Long
tồn tại một đỉnh x
i
X mà m(x
i
) là một số lẻ, chẳng hạn m(x
i
) = 3. Đối với x
i
có 3
cạnh đi vào nó, giả sử đó là các cạnh (x
i
, x
k
), (x
i
, x
j
) và (x
i
, x
1
) U. Chu trình
Euler sẽ đi qua 3 cạnh đó. Khi đó một trong 3 cạnh trên có ít nhất một cạnh mà
chu trình Euler đi qua 2 lần. Điều đó mâu thuẫn với định nghĩa của chu trình .

ờng đi t x đến x
i
, qua các cạnh, mỗi cạnh đúng một lần. Quá trình trên không thể
kéo dài vô hạn do tính hữu hạn của đồ thị G. Giả sử số bớc hữu hạn đó là i. Điều
này chứng tỏ x và x
i
kề nhau, tức là có cạnh nối x và x
i
. Điều đó là đúng vì bớc i là
bớc cuối cùng. Nh vậy tại đỉnh x có chu trình đơn P đi qua.
Bây giờ ta chứng minh rằng trong đồ thị G = <X, U> có chu trình Euler. Theo
chứng minh trên với đỉnh x X có chu trình đơn đi qua là P
1
và P
1
là chu trình
trong đồ thị G. Hãy "đánh dấu xoá" các cạnh trong P
1
. Nếu sau khi "đánh dấu
xoá" các cạnh trên đờng P
1
tạo ra một số đỉnh cô lập mới thì hãy "đánh dấu loại
bỏ" các đỉnh cô lập mới đó. Kết quả thu đợc sẽ là một đồ thị mới G
1
= <X
1
, U
1
> là
đồ thị con của đồ thị G = <X, U> đã cho. Ta chỉ ra đồ thị G

P
1
chứa đỉnh đó thì bậc của đỉnh x
1
sẽ giảm đi 2 đơn vị, do đó m(x
1
) cũng là chẵn.
Tóm lại với mọi x X
1
thì m(x) là một số chẵn.
Ta có thể minh hoạ đồ thị với chu trình đơn P
1
và đồ thị con G
1
nh hình vẽ dới
đây:
36
G
1
= <X
1
, U
1
>
x x
1
Luận văn tốt nghiệp Phan Thanh Long
x
1
là đỉnh chung giữa P

, U
2
> của G
1
. Đồ thị cũng có tính chất
nh G
1
, là liên thông, mọi x X
2
đều có bậc chẵn và G
2
và P
2
có điểm chung
chẳng hạn x
2
Do tính hữu hạn của đồ thịi G, quá trình xây dựng các chu trình đơn sẽ dừng lại
ở bớc thứ k nào đó. Nh vậy, trớc khi sang bớc thứ k ta đã có k - 1 chu trình đơn P
1
,
P
2
, ..., P
k-1
và đồ thị G
k-1
= <X
k-1
, U
k-1

2
,...,P
k
tại các đỉnh chung ta đợc tập các chu trình
Euler trong đồ thị G = <X, U>. Định lý đợc chứng minh.
Định lý 2: Cho đồ thị có hớng G = <X, U> G có chu trình Euler khi và chỉ khi G
là liên thông và mỗi đỉnh đều có bậc vào bằng bậc ra.
1.2 Thuật toán tìm chu trình Euler
Cho đồ thị G = <X, U> xây dựng thuật toán tìm chu trình Euler
Bớc 1: Kiểm tra xem G có là đồ thị liên thông hay không. Nếu G là liên thông thì
chuyển sang bớc 2. Ngợc lại thì thuật toán dừng và kết luận rằng đồ thị không có
chu trình Euler
Bớc 2: Kiểm tra xem tất cả các đỉnh trong G đều có bậc chẵn hay không.
Nếu tất cả các đỉnh đều có bậc là chẵn thì chuyển sang bớc tiếp theo. Nếu không
dừng lại và kết luận đồ thị đã cho không có chu trình Euler.
37
G
2
= <X
2
, U
2
>
x
x
1
x
2
x x
1

1
và x
2
. Hãy thêm vào một
đỉnh mới x và hai cạnh (x, x
1
) và (x, x
2
) vào đồ thị G = <X, U>. Ta có đồ thị mới
G' = <X', U'>, ở đây X' = X {x}, U' = U {(x, x
1
), (x, x
2
)}. Rõ ràng là G' liên
thông và mọi đỉnh đều có bậc chẵn. Theo định lý về chu trình Euler đã nêu ở trên
thì trong G' có tồn tại chu trình Euler, cũng là đờng Euler.
Định lý 4: Cho đồ thị có hớng G = <X, U>, điều kiện cần và đủ để có đờng đi
Euler từ x đến y (x, y X) là G liên thông và đỉnh x có bậc ra lớn hơn bậc vào 1
đơn vị, đỉnh y có bậc vào lớn hơn bậc ra 1 đơn vị, còn tất cả các đỉnh khác đều có
bậc vào bằng bậc ra.
2.2 Thuật toán tìm đờng Euler
Bớc 1: Kiểm tra xem đồ thị G có liên thông hay không. Nếu có thì chuyển sang
bớc 2. Ngợc lại, thì dừng thuật toán và khẳng định rằng không có đờng Euler.
Bớc 2: Kiểm tra xem mọi đỉnh trong G đều có bậc chẵn hay không. Nếu có
chuyển sang bớc 4. Nếu không chuyển sang bớc 3.
Bớc 3: Kiểm tra xem số đỉnh bậc lẻ có bằng 2 hay không. Nếu có chuyển sang b-
ớc 4. Nếu không thì dừng lại và kết luận không có đờng Euler.
Bớc 4: Xây dựng đờng Euler trong G.
II. Chu trình và đờng đi Hamilton
1. Chu trình Hamilton

Định nghĩa: Đờng Hamilton trong đồ thị G = <X, U> là đờng đi qua tất cả các
đỉnh mỗi đỉnh đúng một lần.
39
a
b
c
d
k
g
e
h
a
y
b
a'
b'