Bài giảng Lý thuyết đồ thị - Chương 4: Đồ thị Euler và đồ thị Halmito - Nguyễn Trần Phi Phượng

Chương 4
ĐỒ THỊ EULER 
và ĐỒ THỊ HALMITON
226/03/2011
4.1 Đồ thị Euler
Lý thuyết đồ thị
Định nghĩa
Xét đồ thị G = (V,E)
– Đường đi đơn trong G đượ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.
– Chu trình đơn trong G đượ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.
– Đồ thị G được gọi là đồ thị Euler nếu có chu trình Euler.
– Đồ thị G được gọi là đồ thị nửa Euler nếu có đường đi
Euler.
326/03/2011
4.1 Đồ thị Euler
Lý thuyết đồ thị
Ví dụ:
Đồ thị G1có 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
Đồ thị G2 có các chu trình Euler là:
C1: 1 2 3 4 2 5 4 1 5 6 1
C2: 1 2 4 3 2 5 1 4 5 6 1
1
2
3
4
5
G1
1
2
3
4
5
6
G2
Đồ thị nửa Euler
Đồ thị Euler
426/03/2011
4.1 Đồ thị Euler
Lý thuyết đồ thị
Định lý 1
Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ
khi mọi đỉnh của G đều có bậc chẵn.
Hệ quả
Đồ thị vô hướng liên thông G là đồ thị nửa Euler khi và
chỉ khi nó có không quá 2 đỉnh bậc lẻ.
526/03/2011
4.1 Đồ thị Euler
Lý thuyết đồ thị
Thuật toán Fleury xác định chu trình Euler
Xuất phát từ một đỉnh bất kỳ của G, đi theo các cạnh
một cách tùy ý, chỉ cần tuân thủ hai quy tắc sau:
i) Xóa bỏ cạnh đã đi qua và đồng thời xóa cả những đỉnh
cô lập tạo thành.
ii) Ở mỗi bước, chỉ đi qua cầu khi không còn cách chọn lựa
nào khác.
Ví dụ:
Tìm chu trình ở Euler
trong đồ thị
a b c d
efgh
626/03/2011
4.1 Đồ thị Euler
Lý thuyết đồ thị
Định lý 2
Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và
chỉ khi
deg+(v) = deg-(v), ∀v∈V
726/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Định nghĩa
Xét đồ thị G = (V,E)
– Đường đi trên G được gọi là đường đi Hamilton nếu nó
đi qua tất cả các đỉnh, mỗi đỉnh một lần.
– Chu trình trên G được gọi là chu trình Hamilton nếu nó
đi qua tất cả các đỉnh, mỗi đỉnh một lần.
– Đồ thị G được gọi là đồ thị Hamilton nếu có chu trình
Hamilton.
– Đồ thị G được gọi là đồ thị nửa Hamilton nếu có đường
đi Hamilton.
826/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Ví dụ:
Đồ thị G1có các đường đi Hamilton là:
d1: 3 4 2 5 1
d2: 3 4 5 1 2
Đồ thị G2 có các chu trình Hamilton là:
C1: 1 2 3 4 5 6 1
C2: 1 6 5 2 3 4 1
1
2
3
4
5
G1
1
2
3
4
5
6
G2
Đồ thị Hamilton
Đồ thị nửa Hamilton
926/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Định lý 3 (Dirak 1952)
Đơn đồ thị vô hướng G với n đỉnh (n > 2), mỗi đỉnh có
bậc không nhỏ hơn n/2 là đồ thị Hamilton.
Định lý 4
Đồ thị có hướng liên thông mạnh G với n đỉnh. Nếu
thì G là đồ thị Hamilton.
deg+(v) ≥ n/2, deg-(v) ≥ n/2, ∀v
1026/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Đồ thị đấu loại là đồ thị có hướng mà trong đó hai đỉnh bất
kỳ của nó được nối với nhau bởi đúng một cung.
Định lý 5
i) Mọi đồ thị đấu loại là nửa Hamilton.
ii) Mọi đồ thị đấu loại liên thông mạnh là Hamilton
1126/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Định lý 6 (Ore, 1960)
Cho đồ thị G có n đỉnh. Nếu deg(i)+deg(j)≥ n≥3 với i và
j là hai đỉnh không kề nhau tùy ý thì G là Hamilton.
1226/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Quy tắc để xây dựng một chu trình Hamilton (H)
Quy tắc 1. Tất cả các cạnh kề với đỉnh bậc 2 phải ở trong H
Quy tắc 2. Không có chu trình con (chu trình có chiều dài
<n) nào được tạo thành trong quá trình xây dựng H.
Quy tắc 3. Khi chu trình Hamilton mà ta đang xây dựng đi
qua đỉnh i thì xóa tất cả các cạnh kề với i mà ta chưa dùng
(vì không được dùng đến nữa).
Điều này lại có thể cho ta một số đỉnh bậc 2 và ta lại dùng
quy tắc 1.
Quy tắc 4. Không có đỉnh cô lập hay đỉnh treo nào được
tạo nên sau khi áp dụng quy tắc 3.
1326/03/2011
4.2 Đồ thị Hamilton
Lý thuyết đồ thị
Ví dụ
Đồ thị sau có là đồ thị Hamilton không?
1 2 3
4 5 6
7 8 9
Giả sử G có chu trình
Hamilton H. Theo quy tắc 1,
tất cả các cạnh kề với đỉnh
bậc 2 đều ở trong H: 12, 14,
23, 36, 47, 78, 69, 89. Ta có
chu trình con là 1, 2, 3, 6, 9,
8, 7, 4, 1.
Vậy G không là đồ thị
Hamilton.