CHU TRÌNH EULER VÀ CHU TRÌNH HAMILTON

CHƯƠNG 7


CHU TRÌNH EULER VÀ
CHU TRÌNH HAMILTON
NỘI DUNG
Chu trình Euler
Điều kiện tồn tại chu trình Euler
Chu trình Hamilton
Điều kiện tồn tại chu trình Hamilton

7.1. CHU TRÌNH EULER
Bài toán 7 cây cầu
Định nghĩa chu trình Euler
Điều kiện tồn tại chu trình Euler vô hướng
Điều kiện tồn tại chu trình Euler có hướng
Thuật toán tìm chu trình Euler
BÀI TOÁN 7 CÂY CẦU
Sông Pregel và cù lao Kneiphof chia thành phố Konigsberg ở nước CH Litva thành 4 vùng đất.
7 cây cầu nối giữa các vùng đất.


B

A



D
Pregel

C

BÀI TOÁN 7 CÂY CẦU (tiếp)
Bài toán: Liệu có thể đi qua cả 7 cây cầu, mỗi cầu đúng một lần, rồi quay về chỗ xuất phát được hay không?

Bài toán đã làm say mê cư dân của thành phố. Họ háo hức đi thử nhưng không thành công.


BÀI TOÁN 7 CÂY CẦU (tiếp)
Năm 1736, L.Euler đã chứng minh rằng bài toán không giải được.

Từ bài toán này đưa đến các khái niệm về đường và chu trình Euler.
BÀI TOÁN 7 CÂY CẦU (tiếp)
Biểu diễn mỗi vùng đất bằng một đỉnh của một đa đồ thị vô hướng, hai đỉnh có cạnh nối nếu có cầu nối tương ứng.
Bài toán trên đưa về việc tìm một chu trình của đồ thị đi qua mỗi cạnh của đồ thị đúng một lần.
ĐƯỜNG VÀ CHU TRÌNH EULER
Định nghĩa 7.1
Đường Euler của đa đồ thị là đường đi qua mỗi
cạnh của đồ thị đúng một lần.
Chu trình Euler của đa đồ thị là đường đi qua mỗi
cạnh của đồ thị đúng một lần.
VÍ DỤ 7.1
Chu trình Euler: E = [1, 2, 3, 4, 5, 8, 9, 10, 6, 7]
7.2. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER VÔ HƯỚNG
Định lý 7.1
Đa đồ thị G có chu trình vô hướng Euler khi và chỉ khi mọi đỉnh đều có bậc chẵn.
7.2. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER VÔ HƯỚNG (tiếp)
Chứng minh định lý
1) Điều kiện cần
Mỗi lần chu trình đi qua một đỉnh thì đỉnh đó bớt
đi 2 cạnh kề.
Cuối cùng, số cạnh kề của mỗi đỉnh bằng 0.
Vì vậy, số cạnh kề của mỗi đỉnh phải là một số
chẵn.

7.2. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER VÔ HƯỚNG (tiếp)
Chứng minh định lý:
2) Điều kiện đủ
Xuất phát từ đỉnh a bất kỳ, lập dãy cạnh kề liên
tiếp cho đến khi hết khả năng đi tiếp.
Khi dừng phải dừng ở đỉnh a vì bậc các đỉnh đều
chẵn, thu được chu trình C1.
Nếu C1 vét hết các cạnh của đồ thị thì C1 là chu
trình cần tìm.
Nếu còn cạnh ngoài C1, thì cạnh đó phải kề với
đỉnh a1 của C1, xuất phát từ a1 tìm chu trình C2 …

7.2. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER VÔ HƯỚNG (tiếp)
Chứng minh định lý:
Khi C1, C2,… đã vét hết các cạnh của đồ thị, lập
chu trình Euler như sau:
Từ đỉnh a đi theo nửa trên của C1 đến a1
Từ a1 đi theo nửa trên của C2 đến a2
……
Khi đã đến chu trình con cuối cùng thì đi ngược lại theo nửa dưới các chu trình để trở về a. 
VÍ DỤ 7.2
Tìm chu trình Euler cho đồ thị:
C1 = [1, 3, 4, 5, 8, 2]
C2 = [2, 3, 5, 6, 7]
C3 = [6, 9, 7, 8]
C = [ 1, 3, 4, 5, 8, 2, 3, 5, 6, 9, 7, 8, 6, 7, 2 ]
7.2. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER VÔ HƯỚNG (tiếp)
Hệ quả 7.1: Đa đồ thị G có đường đi Euler vô hướng khi và chỉ khi số đỉnh bậc lẻ bằng 2.
Chứng minh:
1. Điều kiện cần: Nếu có đường đi Euler vô hướng nối a với b thì a và b là 2 đỉnh duy nhất có bậc lẻ.
2. Điều kiện đủ:
Nếu a, b là 2 đỉnh duy nhất có bậc lẻ, xây dựng G’ từ G bằng cách thêm cạnh (a,b).
G’ không có đỉnh bậc lẻ do đó có chu trình Euler C.
Bỏ cạnh (a,b) khỏi chu trình C, thu được đường Euler trong G. 
7.3. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER CÓ HƯỚNG
Định lý 7.2:
Đa đồ thị có hướng liên thông G có chu trình Euler
có hướng khi và chỉ khi tại mỗi đỉnh số cạnh đi vào
bằng số cạnh đi ra:
x  V , r-(x) = r+(x) , trong đó:
- r-(x): số cạnh đi vào đỉnh x
- r+(x): số cạnh đi ra khỏi đỉnh x.



VÍ DỤ 7.3
Chu trình Euler: E = [1, 2, 3, 4, 5, 8, 9, 10, 6, 7]
7.3. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER CÓ HƯỚNG (tiếp)
Hệ quả 7.2
Đa đồ thị có hướng liên thông G có đường Euler có
hướng khi và chỉ khi trong G có 2 đỉnh a, b thoả
mãn:
r-(a) = r+(a) - 1
r-(b) = r+(b) + 1
còn các đỉnh khác đều cân bằng.

7.3. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER CÓ HƯỚNG (tiếp)
Chứng minh hệ quả
Điều kiện cần:
Giả sử đồ thị G có đường Euler có hướng  đi qua
tất cả các cạnh của đồ thị.
- Với đỉnh xuất phát a của ,
Trừ cạnh đầu tiên của  đi ra từ a, cứ một cạnh đi vào a thì phải có một cạnh đi ra khỏi a vì  kết thúc ở đỉnh khác.
Do đó: r-(a) = r+(a) - 1.
7.3. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER CÓ HƯỚNG (tiếp)
Với đỉnh kết thúc b của ,
Trừ cạnh cuối cùng của  đi tới b, cứ một cạnh đi
ra khỏi b thì phải có một cạnh đi vào b vì  kết
thúc ở b.
Do đó: r-(b) = r+(b) + 1.

7.3. ĐIỀU KIỆN TỒN TẠI CHU TRÌNH
EULER CÓ HƯỚNG (tiếp)
2) Điều kiện đủ:
Giả sử G có các đỉnh a, b thoả mãn:
r-(a) = r+(a) - 1 và r-(b) = r+(b) + 1.
Thêm vào cạnh mới (b,a), khi đó theo định lý 7.3 ta có chu trình Euler có hướng C.
Bỏ cạnh (b,a) khỏi C ta được một đường Euler có hướng. 
7.4. THUẬT TOÁN TÌM
CHU TRÌNH EULER
Thuật toán 7.1
Dữ liệu: Đồ thị liên thông G = (V, E) không có đỉnh
bậc lẻ được biểu diễn bởi mảng các danh sách kề
DK.
Kết quả: Chu trình vô hưóng Euler với danh sách các
đỉnh nằm trong stack CE.
7.4. THUẬT TOÁN TÌM
CHU TRÌNH EULER (tiếp)
Thuật toán:
1 Begin
2 S :=  ; CE :=  ;
3 v := đỉnh tuỳ ý của đồ thị ;
push v onto S ;
while S   do
6 begin
7 v := top(S) ;
7.4. THUẬT TOÁN TÌM
CHU TRÌNH EULER (tiếp)
8 if DK(v)   then
9 begin
10 u := đỉnh đầu tiên trong danh sách DK[v] ;
11 push u onto S ;
12 DK[v] := DK[v] {u} ;
13 DK[u] := DK[u] {v}; { Xoá cạnh (v,u) }
14 v := u
15 end


7.4. THUẬT TOÁN TÌM
CHU TRÌNH EULER (tiếp)
16 else
17 begin
18 v := top(S) ;
19 push v onto CE
20 end
21 end
22 End .





7.4. THUẬT TOÁN TÌM
CHU TRÌNH EULER (tiếp)
Độ phức tạp:
Mỗi lần lặp của chu trình (5 - 20):
- Hoặc là đặt đỉnh lên stack S và xoá cạnh,
- Hoặc chuyển đỉnh từ stack S sang stack CE.
Số lần lặp của chu trình không vượt quá số cạnh m.
Độ phức tạp tổng thể của thuật toán là O(m).