Bài giảng Lý thuyết đồ thị (Graph Theory) - Chương 2: Đường đi và chu trình Euler, Hamilton - Trần Quốc Việt

Nội dung text: Bài giảng Lý thuyết đồ thị (Graph Theory) - Chương 2: Đường đi và chu trình Euler, Hamilton - Trần Quốc Việt

1. 29/09/2014 Bài giảng Chương 2 LÝ THUYẾT ĐỒ THỊ ĐƯỜNG ĐI VÀ CHU TRÌNH EULER (GRAPH THEORY) ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON TRẦN QUỐC VIỆT 1 2 Ví dụ :Bài toán về các cây cầu ở Konigsberg (Nga) Nhà toán học Thụy sĩ - Tìm cách đi qua cả bảy cây cầu, sau đó về điểm xuất phát, mỗi cây cầu chỉ đi qua một lần ? Nhiều người đã đi thử nhưng không thành công - Năm 1736, L. Euler, đã dùng lý thuyết đồ thị, chứng minh được: Bài toán không thể có lời giải 3 4 1
2. 29/09/2014 Ví dụ :Bài toán về các cây cầu ở Ví dụ :Bài toán về các cây cầu ở Konigsberg (tt) Konigsberg (tt) Gọi 1, 2, 3 và 4 là 4 vùng đất bị ngăn cách bởi các Bài toán trở thành: Tìm một chu trình đơn đi qua tất cả nhánh sông các cạnh của đồ thị  Chu trình Euler? 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  1   3 4   3 4   2 2 Đường đi Euler và chu trình Euler Đườ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) Cho G là một đồ thị liên thông, một đường đi Euler (Eulerian path) của G là một chu trình đi đơn đi qua tất cả các cạnh (cung) của G của G là đường đi đơn đi qua tất cả các cạnh (cung) của G Ví dụ 1 5 Ví dụ 1,2,5,3,4,5,1: là một chu trình 1 2 4 Euler: 5 3 2,1,5,2,3,4,5: là một đường đi Euler 2 4 3 7 8 2
3. 29/09/2014 Định lý Euler 1 Đị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 h Euler  mọi đỉnh của G đều có bậc chẵn a 0 1 0 1 0 b g 1 0 2 1 0 Ví dụ: Đồ thị nào sau đây có chu trình Euler, không có chu trình A 0 2 0 1 1 Uuler 1 1 1 0 1 e f c 3 0 0 1 1 0 4 a b 3 b c d e d G4 G5 (cho bởi ma trận kề) e c 2 5 a d 1 f g G1 G2 G3 Bài toán về các cây cầu ở Konigsberg (trong ví dụ trước) Chứng minh Định lý Euler 1 C/m điều kiện cần:  1 G vô hướng liên thông có chu trình Euler mọi đỉnh của G có bậc chẵn   3 4 - Mỗi lần chu trình đi qua một đỉnh thì đỉnh đó bớt đi 2  cạnh kề 11 - Kết thúc chu trình Euler, số cạnh kề của mỗi đỉnh phải 2 bằng 0 Có lời giải cho bài toán các chiếc cầu? Vậy: Tổng số cạnh kề của mỗi đỉnh phải là số chẵn. Hay mọi đỉnh trong G đều có bậc chẵn 12 3
4. 29/09/2014 Chứng minh Định lý Euler 1 Chứng minh Định lý Euler 1 C/m điều kiện đủ: C/m điều kiện đủ (tt): G vô hướng liên thông, mọi đỉnh có bậc chẵn - Nếu C1 chứa tất cả các cạnh của G thì C1 chính là chu G có chu trình Euler trình Euler cần tìm. - Ngược lại: + Mở rộng C : chọn một đỉnh a trong C có cạnh liên - Xuất phát từ đỉnh a bất kỳ, đi theo các cạnh một cách 1 1 1 thuộc không nằm trong C1 làm đỉnh bắt đầu của chu ngẫu nhiên không lặp lại cạnh nào đã qua, cho đến trình mới, tương tự như tìm chu trình C , ta tìm chu khi không thể đi tiếp. Gọi đỉnh dừng là b 1 trình C2 với đỉnh bắt đầu a1 có chứa C1. - Nếu b ≠ a thì số lần đến b = số lần đi khỏi b+1 (vô lý, +`Mở rộng C2: Tương tự ta được chu trình C3 chứa C2 vì mọi đỉnh có bậc chẵn) - Vậy b ≡ a, nghĩa là ta có chu trình C1 Dừng khi nhận được Ck không thể mở rộng thêm: 13 14 Chứng minh Định lý Euler 1 Định lý Euler 2 C/m điều kiện đủ (tt): Đồ 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ẻ - Xét một cạnh e=(x,y) bất kỳ - Do G liên thông nên phải có một đường đi từ một 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 đỉnh a (trên Ck) đến x: av1v2 .vmx trình Euler và cũng không có đường đi Euler - Mọi đỉnh trên C đều không thể dùng để mở rộng chu k 2 h 6 3 trình, do vậy: (a,v1) Ck, (v1,v2) Ck, , (vm,x) Ck, 1 1 3 4 a và (x,y) Ck 6 2 b g - Kết luận: Ck chứa tất cả các cạnh của G hay Ck là một chu trình Euler cần tìm 3 3 e f c 2 5 4 1 5 4 d 5 15 G G 16 G1 G2 3 4 4
5. 29/09/2014 Chứng minh định lý Euler 2 Đị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 2 1 3 4 3 2 4 G2: G1: 17 cân bằng nên Có chu trình Euler Không cân bằng nên 18 Không Có chu trình Euler Định lý Euler 4 Ví dụ: Định lý Euler 4: 1 e 1 2 2 e 6 Cho G=(V,E) có hướng, không có đỉnh cô lập. Và |V|>1. G có 5 e7 5 7 đường đi Euler nhưng không có chu trình Euler G liên thông e1 e4 yếu và có đúng 2 đỉnh x,y thoả: e6 e8 + - 3 8 deg (x)=deg (x)+1 e3 4 deg- (y)=deg+(y)+1 G1 G2 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 G G -Đồ thị nào có chu trình Euler, đồ thị 1 2 G3 nào có đường đi Euler G3 -Tìm đường đi Euler, chu trình Euler 19 (nếu có) trong mỗi đồ thị 20 5
6. 29/09/2014 Bài tập Bài tập 1 Tìm chu trình Euler trên đồ thị được cho bởi ma trận kề 2 6 4 3 5 G H Tìm đường đi và chu trình Euler (nếu có) trong các đồ thị trên? 21 22 Thuật toán tìm chu trình Euler Bài tập thực hành 1. Chọn đỉnh v bất kỳ làm đỉnh bắt đầu 2. C {v}; 3. Nếu còn cạnh của G chưa đặt vào C 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 (a) Đặt G’=(VG’,EG’) có được từ G sau khi xóa các cạnh có trong C và xóa các đỉnh cô lập. Cài đặt thuật toán tìm đường đi và chu trình Euler trong đồ thị vô hướng (có hướng) (b) Chọn một đỉnh a {tập đỉnh có trong C} VG’ (c) Từ a, chọn một dãy các cạnh, đỉnh kề liên tiếp trong G’ (không có canh lặp lai), cho đến khi không chọn được nữa, ta được chu trình C1 (d) Thay thế vị trí a trong C bởi C1, lặp lại bước 3 end 23 24 4. Return C; 6
7. 29/09/2014 2. Đường đi và chu trình Hamilton 2. Đường đi và chu trình Hamilton (tt) 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 1 2 1 2 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. 5 5 . Một đồ thị có đường đi Hamilton được gọi là nữa Hamilton. 3 3 4 3 4 3 5 5 Ví dụ:   1 2 H Một chu trình Hamilton trong H 1 2 6 4 6 4 Một đường đi Hamilton trong G G 25 26 Quy tắc tìm chu hình Hamilton Ví dụ: 2 Nếu tồn tại 1 đỉnh của G có bậc ≤1 thì G không có chu trình Hamilton 1 2 3 1 3 Nếu đỉnh x có bậc 2 thì cả 2 cạnh tới x đều phải thuộc 9 9 chu trình Hamilton 8 4 8 10 4 Chu trình Hamilton không chứa bất kỳ chu trình con 11 thực sự nào H 7 6 5 7 Trong quá trình xây dựng chu trình Hamilton, sau khi 6 5 đã lấy 2 cạnh tới đỉnh x đặt vào chu trình Hamilton rồi G thì phải xóa mọi cạnh còn lại tới x -Đồ 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ị 27 28 7
8. 29/09/2014 2. Đường đi và chu trình Hamilton (tt) 2. Đường đi và chu trình Hamilton (tt) Định lý: Mọi đồ thị đủ đều có chu trình Hamilton Đị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 1 được nhiều hơn k thành phần liên thông. Thì G không 1 có chu trình Hamilton 2 1 2 3 3 1 2 6 6 7 7 5 5 4 5 5 4 1 2 5 4 3 1 9 3 K5 8 Là một chu trình Hamilton của K 3 4 5 9 Xóa 2 đỉnh 2 và 4 cùng với các 8 H cạnh liên kết của nó thu được 3 thành phần liên thông H không H có chu trình Hamilton không? có chu trình Hamilton 29 30 2. Đường đi và chu trình Hamilton (tt) 2. Đường đi và chu trình Hamilton (tt) Cho đồ thị G như hình dưới. G có chu trình Hamilton Định lý (Dirac): Cho G là đơn đồ thị có n đỉnh (n≥3). Nếu không? mọi đỉnh của G đều có bậc ≥ n/2 thì G có chu trình Giải: Hamilton 1 Nếu xóa đi 3 đỉnh 3,4 và 6 ta được Định lý: Mọi đồ thị có hướng, có n đỉnh, liên thông mạnh. 4 thành phần liên thông. Vậy G không là Hamilton 1 Nếu mỗi đỉnh v thuộc đồ thị thỏa: 2 deg-(v)≥n/2 và deg+(v)≥n/2 4 3 5 2 Thì G có chu trình hamilton 1 2 n=5 (>3) 5 Ví dụ: deg(1)=4 (≥5/2) 10 9 deg(2)=4 (≥5/2) Deg(3)=4 (≥5/2) 5 8 10 9 Deg(4)=3 (≥5/2) 7 6 Deg(5)=3 (≥5/2) 3 8 31 4 32 7 Vậy G có chu trình Hamilton 8
9. 29/09/2014 2. Đường đi và chu trình Hamilton (tt) 2. Đường đi và chu trình Hamilton (tt) Bao đóng của đồ thị: Định lý: Một đồ thị là Hamilton nếu và chỉ nếu bao Cho đơn đồ thị G có n đỉnh, bao đóng c(G) được tạo ra đóng của nó là Hamilton. từ G bằng cách bổ sung cho mỗi cặp đỉnh không kề Ví dụ: Cho đồ thị 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 G có phải là hamilton không? 33 34 2. Đường đi và chu trình Hamilton (tt) 2. Đường đi và chu trình Hamilton (tt) Đồ thị đấu loại: Là đồ thị có hướng có đỉnh bất kỳ Định lý (Ore, 1960): Một đơn đồ thị vô hướng G gồm luôn luôn được nối với nhau bởi đúng một cung 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 Định lý: Nên G có chu trình Hamilton  Mọi đồ thị đấu loại đều có đường đi Hamilton G  Mọi đồ thị đấu loại liên thông mạnh đề có chu trình Hamilton 35 36 9
10. 29/09/2014 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) // A là ma trận kề của G { for (j=0; j 0) // hc[0 n-1] chứa chu trình { if (i 0) x[0]=0;visited[0]=true; printHamiltonCycle(x); Expand(1); } } } 37 10