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

CHƯƠNG IV  
ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON  
4.1. ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER.  
thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, với việc công bố lời giải  
“bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler (1707-1783). Thành  
phố Konigsberg thuộc Phổ (nay gọi là Kaliningrad thuộc Nga) được chia thành bốn  
vùng bằng các nhánh sông Pregel, các vùng này gồm hai vùng bên bờ sông, đảo  
Kneiphof và một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18, người ta xây  
bảy chiếc cầu nối các vùng này với nhau.  
B
B
D
A
D
A
C
C
G
Dân thành phố từng thắc mắc: “Có thể nào đi dạo qua tất cả bảy cầu, mỗi cầu chỉ  
một lần thôi không?”. Nếu ta coi mỗi khu vực A, B, C, D như một đỉnh mỗi cầu qua  
lại hai khu vực một cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị  
G như hình trên.  
Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu chỉ qua một lần thể được  
phát biểu lại bằng mô hình này như sau: Có tồn tại chu trình đơn trong đa đồ thị G chứa  
tất cả các cạnh?  
4.1.1. Định nghĩa: Chu trình (t.ư. đường đi) đơn chứa tất cả các cạnh (hoặc cung) của  
đồ thị (vô hướng hoặc hướng) G được gọi là chu trình (t.ư. đường đi) Euler. Một đồ  
thị liên thông (liên thông yếu đối với đồ thị hướng) chứa một chu trình (t.ư. đường  
đi) Euler được gọi đồ thị Euler (t.ư. nửa Euler).  
Thí dụ 1:  
Đồ thị Euler  
Đồ thị không nửa Euler  
Đồ thị nửa Euler  
54  
Đồ thị Euler  
Đồ thị nửa Euler  
Điều kiện cần đủ để một đồ thị đồ thị Euler được Euler tìm ra vào năm 1736  
khi ông giải quyết bài toán hóc búa nổi tiếng thời đó về bảy cái cầu ở Konigsberg và đây  
định đầu tiên của thuyết đồ thị.  
4.1.2. Định lý: Đồ thị (vô hướng) liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh  
của G đều bậc chẵn.  
Chứng minh:  
Điều kiện cần: Giả sử G là đồ thị Euler, tức tồn tại chu trình Euler P trong G. Khi đó  
cứ mỗi lần chu trình P đi qua một đỉnh nào đó của G thì bậc của đỉnh đó tăng lên 2. Mặt  
khác, mỗi cạnh của đồ thị xuất hiện trong P đúng một lần. Do đó mỗi đỉnh của đồ thị  
đều bậc chẵn.  
4.1.3. Bổ đề: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình  
đơn.  
Chứng minh: Nếu G có cạnh bội hoặc có khuyên thì khẳng định của bổ đề hiển  
nhiên. Vì vậy giả sử G là một đơn đồ thị. Gọi v là một đỉnh nào đó của G. Ta sẽ xây  
dựng theo quy nạp đường đi  
......  
v
v1  
v2  
trong đó v1 đỉnh kề với v, còn với i 1, chọn vi+1 đỉnh kề với vi và vi+1 vi 1 (có thể  
-
chọn như vậy vì deg(vi) 2), v0 = v. Do tập đỉnh của G là hữu hạn, nên sau một số hữu  
hạn bước ta phải quay lại một đỉnh đã xuất hiện trước đó. Gọi k là số nguyên dương đầu  
tiên để vk=vi (0i<k). Khi đó, đường đi vi, vi+1, ..., vk 1, vk (= vi) là một chu trình đơn cần  
-
tìm.  
Điều kiện đủ: Quy nạp theo số cạnh của G. Do G liên thông và bậc của mọi đỉnh là  
chẵn nên mỗi đỉnh bậc không nhỏ hơn 2. Từ đó theo Bổ đề 4.1.3, G phải chứa một  
chu trình đơn C. Nếu C đi qua tất cả các cạnh của G thì nó chính là chu trình Euler. Giả  
sử C không đi qua tất cả các cạnh của G. Khi đó loại bỏ khỏi G các cạnh thuộc C, ta thu  
được một đồ thị mới H (không nhất thiết là liên thông). Số cạnh trong H nhỏ hơn trong  
G và rõ ràng mỗi đỉnh của H vẫn bậc chẵn. Theo giả thiết quy nạp, trong mỗi thành  
phần liên thông của H đều tìm được chu trình Euler. Do G liên thông nên mỗi thành  
55  
phần trong H có ít nhất một đỉnh chung với chu trình C. Vì vậy, ta có thể xây dựng chu  
trình Euler trong G như sau:  
C
Bắt đầu từ một đỉnh nào đó của chu trình C, đi theo các cạnh của C chừng nào chưa gặp  
phải đỉnh không cô lập của H. Nếu gặp phải đỉnh như vậy thì ta đi theo chu trình Euler  
của thành phần liên thông của H chứa đỉnh đó. Sau đó lại tiếp tục đi theo cạnh của C cho  
đến khi gặp phải đỉnh không cô lập của H thì lại theo chu trình Euler của thành phần liên  
thông tương ứng trong H, ... Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát, tức là thu  
được chu trình đi qua mỗi cạnh của đồ thị đúng một lần.  
4.1.4. Hệ quả: Đồ thị liên thông G là nửa Euler (mà không là Euler) khi và chỉ khi có  
đúng hai đỉnh bậc lẻ trong G.  
Chứng minh: Nếu G là nửa Euler thì tồn tại một đường đi Euler trong G từ đỉnh u đến  
đỉnh v. Gọi G’ là đồ thị thu được từ G bằng cách thêm vào cạnh (u,v). Khi đó G’ là đồ  
thị Euler nên mọi đỉnh trong G’ đều bậc chẵn (kể cả u và v). Vì vậy u và v là hai đỉnh  
duy nhất trong G có bậc lẻ.  
Đảo lại, nếu đúng hai đỉnh bậc lẻ là u và v thì gọi G’ là đồ thị thu được từ G  
bằng cách thêm vào cạnh (u,v). Khi đó mọi đỉnh của G’ đều bậc chẵn hay G’ là đồ thị  
Euler. Bỏ cạnh (u,v) đã thêm vào ra khỏi chu trình Euler trong G’ ta có được đường đi  
Euler từ u đến v trong G hay G là nửa Euler.  
4.1.5. Chú ý: Ta có thể vạch được một chu trình Euler trong đồ thị liên thông G có bậc  
của mọi đỉnh chẵn theo thuật toán Fleury sau đây.  
Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy tắc sau:  
1. Mỗi khi đi qua một cạnh nào thì xoá nó đi; sau đó xoá đỉnh lập (nếu có);  
2. Không bao giờ đi qua một cầu, trừ phi không còn cách đi nào khác.  
u
t
v
x
w
y
s
z
56  
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, 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)). 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).  
4.1.6. Bài toán người phát thư Trung Hoa:  
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 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”. Ta 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 một hành trình  
trong 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 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ẻ 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 đó.  
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.  
Ta quy ước xem mỗi hành trình T trong G là một hành trình trong đồ thị Euler  
GT, 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. Bài toán đặt ra được đưa về bài toán sau:  
Trong các đồ thị Euler GT, tìm đồ thị 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 được xác định như sau:  
Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta 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 một phân hoạch cặp của V0(G).  
Ta 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, ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng d(Pi).  
Số m(G) bằng cực tiểu của các d(Pi):  
57