Bài giảng Lý thuyết về đồ thị - Bài 2: Đường đi, chu trình Euler

Bài 2 
Đường đi, chu trình Euler 
2.1. Đồ thị Euler 
Bài toán 7 cái cầu ở TP Konigsberg 
12/3/2021 
Graph Theory 
3 
A 
B 
C 
D 
Bài toán 7 cái cầu ở Tp. Konigsberg 
4 
A 
B 
C 
D 
A 
B 
D 
C 
Mô hình thành 
Đồ thị 
Đặt vấn đề (tt) 
Hãy vẽ các hình sau bằng đúng một nét bút (không được nhấc bút lên trong khi vẽ) 
5 
Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 2 nét. 
Không vẽ được bằng 1 nét. Tối thiểu phải vẽ bằng 6 nét. 
Đặt vấn đề (tt) 
Hãy vẽ các hình sau bằng đúng một nét bút (không được nhấc bút lên trong khi vẽ) 
6 
Đường đi, chu trình Euler 
Xét đồ thị G = . 
Một đường đi trên đồ thị được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. 
Một chu trình trên đồ thị được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh, mỗi cạnh một lần. 
VD: Đồ thị sau có các đường đi Euler là: 
d1: 1 2 3 4 2 5 4 1 5 
d2: 1 2 4 3 2 5 1 4 5 
7 
1 
2 
3 
4 
5 
Đường đi, chu trình Euler (tt) 
VD: Đồ thị sau có các chu trình Euler là: 
d1: 1 2 3 4 2 5 4 1 5 6 1 
d2: 1 2 4 3 2 5 1 4 5 6 1 
8 
1 
2 
3 
4 
6 
5 
Đồ thị Euler 
Xét đồ thị G = . 
Đồ thị G được gọi là đồ thị Euler nếu và chỉ nếu tồn tại một chu trình Euler trong G. 
Đồ thị G được gọi là đồ thị nửa Euler nếu và chỉ nếu tồn tại một đường đi Euler trong G. 
9 
1 
2 
3 
4 
5 
1 
2 
3 
4 
6 
5 
Đồ thị nửa Euler 
Đồ thị Euler (hiển nhiên cũng là đồ thị nửa Euler). 
Định lý Euler 
Định lý. Đồ thị vô hướng, liên thông G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của nó đều có bậc chẵn. 
Hệ quả. Đồ thị vô hướng, liên thông G là đồ thị nửa Euler nếu và chỉ nếu nó có không quá hai đỉnh bậc lẻ. 
10 
Thuật toán xây dựng chu trình Euler 
Thuật toán Fleury 
Bắt đầu từ một đỉnh bất kỳ của đồ thị và tuân theo các quy tắc sau: 
Quy tắc 1. Khi đi qua một cạnh nào đó thì xóa nó đi và xóa luôn đỉnh cô lập, nếu có. 
Quy tắc 2. Không bao giờ đi qua cầu (cạnh cắt) trừ phi không còn cách nào khác. 
VD: Tìm chu trình Euler trong đồ thị sau: 
11 
a 
b 
c 
d 
e 
f 
g 
h 
Thuật toán xây dựng chu trình Euler 
Gọi chu trình Euler cần tìm là C. Thuật toán sẽ tiến hành theo các bước sau: 
Khởi tạo: Chọn một đỉnh bất kỳ cho vào C. 
Lặp trong khi G vẫn còn cạnh 
Chọn cạnh e nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cầu nếu không còn cạnh nào khác để chọn. 
Bổ sung e và đỉnh cuối của nó vào C. 
Xóa e khỏi G. Sau đó xoá đỉnh cô lập (nếu có). 
12 
Ví dụ 
13 
Ví dụ (tt) 
Xuất phát từ u, ta có thể đi theo cạnh (u, v) hoặc (u, x), giả sử là (u, v) (xoá (u,v)). Từ v có thể đi qua một trong các cạnh (v, w), (v, x), (v, t), giả sử (v, w) (xoá (v,w)). Tiếp tục, có thể đi theo một trong các cạnh (w, s), (w, y), (w, z), giả sử (w, s) (xoá (w, s)). 
Đi theo cạnh (s, y) (xoá (s, y) và s). Vì (y, x) là cầu nên có thể đi theo một trong hai cạnh (y, w), (y, z), giả sử (y, w) (xoá (y, w)). Đi theo (w, z) (xoá (w, z) và w) và theo (z, y) (xoá (z, y) và z). Tiếp tục đi theo cạnh (y, x) (xoá (y, x) và y). Vì (x, u) là cầu nên đi theo cạnh (x, v) hoặc (x, t), giả sử (x, v) (xoá (x, v)). 
14 
Ví dụ (tt) 
Tiếp tục đi theo cạnh (v, t) (xoá (v, t) và v), theo cạnh (t, x) (xoá cạnh (t, x) và t), cuối cung đi theo cạnh (x, u) (xoá (x, u), x và u). 
Sau khi thực hiện xong thuật toán ta có chu trình Euler như sau: (u, v, w, s, y, w, z, y, x, v, t, x, u) 
15 
Định lý Euler cho đồ thị có hướng 
Định lý: Xét G là đồ thị có hướng, liên thông mạnh. Khi đó G là đồ thị Euler nếu và chỉ nếu mọi đỉnh của G đều có bán bậc ra bằng bán bậc vào. 
16 
2.2. Bài toán người phát thư Trung Hoa 
17 
Phát biểu bài toán 
Một nhân viên đi từ Sở Bưu Điện, qua một số đường phố để phát thư, rồi quay về Sở. Người ấy phải đi qua các đường theo trình tự nào để đường đi là ngắn nhất? 
Bài toán được nhà toán học Trung Hoa Guan nêu lên đầu tiên (1960), vì vậy thường được gọi là “bài toán người phát thư Trung Hoa”. 
18 
Giải bài toán người đưa thư 
X ét bài toán ở một dạng đơn giản như sau : 
Cho đồ thị liên thông G. Một chu trình qua mọi cạnh của G gọi là một hành trình trong đồ thị G. Trong các hành trình đó, hãy tìm hành trình ngắn nhất, tức là qua ít cạnh nhất. 
Rõ ràng rằng nếu G là đồ thị Euler (mọi đỉnh đều có bậc chẵn) thì chu trình Euler trong G (qua mỗi cạnh của G đúng một lần) là hành trình ngắn nhất cần tìm . 
Chỉ còn phải xét trường hợp G có một số đỉnh bậc lẻ (số đỉnh bậc lẻ là một số chẵn). Khi đó, mọi hành trình trong G phải đi qua ít nhất hai lần một số cạnh nào đó. 
19 
Giải bài toán người đưa thư (tt) 
X ét bài toán ở một dạng đơn giản như sau : (tt) 
Dễ thấy rằng một hành trình qua một cạnh (u, v) nào đó quá hai lần thì không phải là hành trình ngắn nhất trong G. Vì vậy, ta chỉ cần xét những hành trình T đi qua hai lần một số cạnh nào đó của G. 
Q uy ước mỗi hành trình T trong G là một hành trình trong đồ thị Euler G T , có được từ G bằng cách vẽ thêm một cạnh song song đối với những cạnh mà T đi qua hai lần. 
20 
Giải bài toán người đưa thư (tt) 
Bài toán đặt ra được đưa về bài toán sau: 
T rong các đồ thị Euler G T , tìm đồ thị có số cạnh ít nhất (khi đó chu trình Euler trong đồ thị này là hành trình ngắn nhất). 
Định lý (Gooodman và Hedetniemi, 1973). Nếu G là một đồ thị liên thông có q cạnh thì hành trình ngắn nhất trong G có chiều dài q + m(G), trong đó m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như sau: 
21 
Giải bài toán người đưa thư (tt) 
Bài toán đặt ra được đưa về bài toán sau: (tt) 
Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V 0 (G). 
G ọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u, v). Đối với mọi phân hoạch cặp Pi, tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng d(P i ). Số m(G) bằng cực tiểu của các d(P i ): 
	 m(G)=min d(P i ). 
22 
Ví dụ bài toán người đưa thư 
Giải bài toán người phát thư Trung Hoa với đồ thị sau: 
23 
Ví dụ bài toán người đưa thư (tt) 
Tập hợp các đỉnh bậc lẻ VO(G)={B, G, H, K} và tập hợp các phân hoạch cặp là P={P1, P2, P3}, trong đó 
P 1 = {(B, G), (H, K)} 
	 d(P 1 ) = d(B, G)+d(H, K) = 4+1 = 5, 
P 2 = {(B, H), (G, K)} 
	 d(P 2 ) = d(B, H)+d(G, K) = 2+1 = 3, 
P 3 = {(B, K), (G, H)} 
	 d(P 3 ) = d(B, K)+d(G, H) = 3+2 = 5. 
Vậy m(G) = min(d(P 1 ), d(P 2 ), d(P 3 )) = 3. 
24 
Ví dụ bài toán người đưa thư (tt) 
Do đó G T có được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K) và G T là đồ thị Euler. 
Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong G T : ( A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A ) 
25 
Ví dụ bài toán người đưa thư (tt) 
Đồ thị sau khi thêm cạnh: 
26