Bài giảng
LÝ THUYẾT ĐỒ THỊ (GRAPH THEORY)
1
Chương 2: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON
ĐƯỜNG ĐI VÀ CHU TRÌNH EULER
ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON
2
3
Nhà toán học Thụy sĩ
Ví dụ :Bài toán về các cây cầu ở Konigsberg (Nga)
- Xác định một chu trình đi qua tất cả 7 cây cầu, mỗi cái đúng 1 lần.
4
Ví dụ :Bài toán về các cây cầu ở Konigsberg (tt)
Gọi 1, 2, 3 và 4 là 4 vùng đất bị ngăn cách bởi các
nhánh sông
Biểu diễn mỗi vùng đất bởi một đỉnh của đồ thị Một cạnh: một cây cầu nối giữa 2 vùng đất
1
3 4
2
Ví dụ :Bài toán về các cây cầu ở Konigsberg (tt)
Bài toán trở thành: Tìm một chu trình đơn đi qua tất cả
các cạnh của đồ thị Chu trình Euler?
1
3 4
2
Đường đi Euler và chu trình Euler
Cho G là một đồ thị liên thông, một chu trình Euler (Eulerian circuit) của G là một chu trình đi đơn đi qua tất cả các cạnh (cung) của G
1 Ví dụ 5
4 2 1,2,5,3,4,5,1: là một chu trình Euler:
7
3
Đường đi Euler và chu trình Euler
Cho G là một đồ thị liên thông, một đường đi Euler (Eulerian path)
của G là đường đi đơn đi qua tất cả các cạnh (cung) của G
Ví dụ
1 5
2,1,5,2,3,4,5: là một đường đi Euler
4 2
8
3
Định lý Euler 1
Định lý Euler 1:
Đồ thị vô hướng G=(V,E) liên thông và |V|>1, G có chu trình Euler mọi đỉnh của G đều có bậc chẵn
Ví dụ: Đồ thị nào sau đây có chu trình Euler, không có chu trình
Uuler
3
4 b c b 3 a
e d c 2 5 a e
d 1 f g
G1 G2 G3
Định lý Euler 1
h
0 1
1 0
0 2
1 1
0 0
a
A
0
2
0
1
1
1
1
1
0
1
b g
0
0
1
1
0
c e f
d
G4 G5 (cho bởi ma trận kề)
Định lý Euler 2
Đồ thị vô hướng liên thông G=(V,E) và có |V|>1, G có đường đi Euler và không có chu trình Euler G có đúng 2 đỉnh bậc lẻ
Ví dụ: Đồ thi nào sau đây có chu trình Euler, đồ thi nào có đường đi Euler nhưng không có chu trình Euler, đồ thị nào không có chu trình Euler và cũng không có đường đi Euler
1
2 h 3 6 1 3 4 a
b 6 2 g
5
3 3 c e f 2
4 1 5 4 d
11
5 G4 G3 G1 G2
Định lý Euler 3
Định lý Euler 3:
Đồ thị có hướng G=(V,E) liên thông yếu và |V|>1. G có chu trình Euler mọi đỉnh trong G đều có nữa bậc trong bằng nữa bậc ngoài (hay G cân bằng)
1 1 2 3
4 2 3 4
G1: cân bằng nên Có chu trình Euler
G2: Không cân bằng nên 12 Không Có chu trình Euler
Định lý Euler 4
Định lý Euler 4:
Cho G=(V,E) có hướng, không có đỉnh cô lập. Và |V|>1. G có đường đi Euler nhưng không có chu trình Euler G liên thông yếu và có đúng 2 đỉnh x,y thoả:
deg+(x)=deg-(x)+1 deg- (y)=deg+(y)+1
Các đỉnh còn lại cân bằng
Ví dụ: Đồ thị nào có chu trình Euler, đồ thị nào chỉ có đường đi Euler
13
G1 G2 G3
Ví dụ:
1 e2 2 6 1 e5 e7 5 7 e4 e1
e6 e8
3 8 4 e3
G1 G2
14
G3
-Đồ thị nào có chu trình Euler, đồ thị nào có đường đi Euler -Tìm đường đi Euler, chu trình Euler (nếu có) trong mỗi đồ thị
Bài tập
1
2 6
4
3 5
G H
15
Tìm đường đi và chu trình Euler (nếu có) trong các đồ thị trên?
Bài tập
Tìm chu trình Euler trên đồ thị được cho bởi ma trận
kề
16
Thuật toán tìm chu trình Euler
Thuật toán tìm chu trình Euler của đồ thị G(V, E). Kết quả sẽ cho ra
C là một chu trình Euler bao gồm thứ tự các cạnh của chu trình.
17
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 1 1 0 0 0
1
3 2
4
1 2 3 4 5 6
6 5
1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0
C = Ø, v = 1
18
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 1 0 0 0
1
3 2
4
1 2 3 4 5 6
6 5
0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0
C = 1,2
19
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 1 0 0 0
1
3 2
4
1 2 3 4 5 6
6 5
0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0
C = 1,2,3
20
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 0 0 0 0
1
3 2
4
1 2 3 4 5 6
0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0
C = 1,2,3,1
E Ø
21
6 5
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 0 0 0 0
1
3 2
4
1 2 3 4 5 6
0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0
C = 1,2,4, ,3,1
22
6 5
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 0 0 0 0
1
3 2
4
1 2 3 4 5 6
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0
C = 1,2,4,3, ,3,1
23
6 5
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 0 0 0 0
1
3 2
4
1 2 3 4 5 6
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0
C = 1,2,4,3,6, ,3,1
24
6 5
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 0 0 0 0
1
3 2
4
1 2 3 4 5 6
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
C = 1,2,4,3,6,5, ,3,1
25
6 5
Ví dụ tìm chu trình Euler
1 2 3 4 5 6
0 0 0 0 0 0
1
3 2
4
1 2 3 4 5 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
C = 1,2,4,3,6,5,2,3,1
E = Ø
26
6 5
Ví dụ tìm chu trình Euler Euler() { // Tim chu trinh Euler cua do thi Euler G = (V, E)
// PATH chua danh dinh cua chu trinh Euler // STACK ngan xep dieu khien viec tim kiem
// dua u vao dua ngan xep
// gan x bang phan tu dau STACK
STACK = ; PATH = ; Chon u la mot dinh nao do cua do thi; STACK u; While (STACK <> ) { x top(STACK); If (Ke(x) <> ) {
// huy phan tu dau STACK va gan cho y
y dinh dau tien trong danh sach Ke(x); STACK y;
// loai bo canh (x,y) khoi do thi
Ke(x) = Ke(x) \ {y}; Ke(y) = Ke(y) \ {x};
} Else {
x STACK; // huy phan tu dau STACK va gan cho x PATH x;
27
}
}
}
Bài tập thực hành
Cài đặt thuật toán kiểm tra một đồ thị (vô hướng hoặc có
hướng) có là Euler (hoặc nữa Euler) hay không
Cài đặt thuật toán tìm đường đi và chu trình Euler trong
đồ thị vô hướng (có hướng)
28
2. Đường đi và chu trình Hamilton
Cho G liên thông, đường đi (tương tự chu trình) Hamilton trong G là đường đi (tương tự chu trình) đi qua tất các đỉnh của G, mỗi đỉnh chỉ qua đúng một lần Một đồ thị có chu trình Hamilton được gọi là thị Hamilton. Một đồ thị có đường đi Hamilton được gọi là nữa Hamilton.
3
3
5
5
Ví dụ:
1
2
1
2
6
4
6
4
29
Một đường đi Hamilton trong G G
2. Đường đi và chu trình Hamilton (tt)
1
1
2 2
5 5
3 3 4 4
30
H Một chu trình Hamilton trong H
Quy tắc tìm chu hình Hamilton
Nếu tồn tại 1 đỉnh của G có bậc ≤1 thì G không có chu
trình Hamilton
Nếu đỉnh x có bậc 2 thì cả 2 cạnh tới x đều phải thuộc
chu trình Hamilton
Chu trình Hamilton không chứa bất kỳ chu trình con
thực sự nào
Trong quá trình xây dựng chu trình Hamilton, sau khi đã lấy 2 cạnh tới đỉnh x đặt vào chu trình Hamilton rồi thì phải xóa mọi cạnh còn lại tới x
31
Ví dụ:
2
1
3
2
1
3
9
9
8
4
8
4
10
11
5
7
7
6
6
5
H
-Đồ thị nào có chu trình Hamilton, đồ thị nào không có chu trình Hamilton? -Tìm một chu trình Hamilton (nếu có) trên mỗi đồ thị
32
G
2. Đường đi và chu trình Hamilton (tt)
Định lý: Mọi đồ thị đủ đều có chu trình Hamilton
1 1
2 3 2 3
5 4 5 4 12 5 4 3 1
K5
33
Là một chu trình Hamilton của K5
2. Đường đi và chu trình Hamilton (tt)
Định lý: Cho đồ thị G, giả sử có k đỉnh sao cho khi xoá k đỉnh này cùng với các cạnh liên kết với chúng thì ta được nhiều hơn k thành phần liên thông. Thì G không có chu trình Hamilton
1
1
2 6
6
7
5 7 5
9 3 8 3 4 9
H 8
34
H có chu trình Hamilton không? Xóa 2 đỉnh 2 và 4 cùng với các cạnh liên kết của nó thu được 3 thành phần liên thông H không có chu trình Hamilton
2. Đường đi và chu trình Hamilton (tt)
Cho đồ thị G như hình dưới. G có chu trình Hamilton
không?
Giải:
1
1 Nếu xóa đi 3 đỉnh 3,4 và 6 ta được 4 thành phần liên thông. Vậy G không là Hamilton
2
4 3
2
5
5
10 9
35
10 9 8 7 6
8 7
2. Đường đi và chu trình Hamilton (tt)
Định lý (Dirac): Cho G là đơn đồ thị có n đỉnh (n≥3). Nếu
mọi đỉnh của G đều có bậc ≥ n/2 thì G có chu trình Hamilton
Định lý: Mọi đồ thị có hướng, có n đỉnh, liên thông mạnh.
Nếu mỗi đỉnh v thuộc đồ thị thỏa:
deg-(v)≥n/2 và deg+(v)≥n/2
Thì G có chu trình hamilton 1 2
Ví dụ:
5
n=5 (>3) deg(1)=4 (≥5/2) deg(2)=4 (≥5/2) Deg(3)=4 (≥5/2) Deg(4)=3 (≥5/2) Deg(5)=3 (≥5/2) 36 4
3 Vậy G có chu trình Hamilton
2. Đường đi và chu trình Hamilton (tt)
Bao đóng của đồ thị:
Cho đơn đồ thị G có n đỉnh, bao đóng c(G) được tạo ra từ G bằng cách bổ sung cho mỗi cặp đỉnh không kề nhau u và v với deg(v) + deg(u) ≥ n một cạnh mới uv.
Ví dụ: Cho G, tìm bao đóng của G
37
2. Đường đi và chu trình Hamilton (tt)
Định lý: Một đồ thị là Hamilton nếu và chỉ nếu bao
đóng của nó là Hamilton.
Ví dụ: Cho đồ thị
38
G có phải là hamilton không?
2. Đường đi và chu trình Hamilton (tt)
Đồ thị đấu loại: Là đồ thị có hướng có đỉnh bất kỳ luôn luôn được nối với nhau bởi đúng một cung
Định lý:
Mọi đồ thị đấu loại đều có đường đi Hamilton Mọi đồ thị đấu loại liên thông mạnh đều có chu trình
39
Hamilton
2. Đường đi và chu trình Hamilton (tt)
Định lý (Ore, 1960): Một đơn đồ thị vô hướng G gồm n đỉnh với n≥3. Nếu deg(u)+deg(v)≥n với mọi cặp đỉnh u,v không kề nhau trong G thì G là đồ thị Hamilton
Ví dụ:
Mọi cặp đỉnh khác nhau u, v trong G đều thỏa:
deg(u)+deg(v)≥n=6
Nên G có chu trình Hamilton
40
G
Thuật toán tìm tất cả các chu trình Hamilton của G (Thuật toán quay lui)
FindHamiltonCycles(int[][] A)
Expand(i) {
for (j=0; j // A là ma trận kề của G if (visited[j]==false && a[x[i]-1][j]>0)
{ // G có n đỉnh
// hc[0..n-1] chứa chu trình
tìm được x[i]=j;
if (i //visited[0…n-1] đánh dấu visited [j]=true;
Expand(i+1);
visited[j]=false; }
else
if (a[x[i]][0]>0) các đỉnh đã xét
int[] hc= new int[n];
visited = new boolean[n];
for (j=0; j printHamiltonCycle(x); } } 41 }
