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

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

1. Chương 4 ĐỒ THỊ EULER và ĐỒ THỊ HALMITON
2. 4.1 Đồ thị Euler Định nghĩa Xét đồ thị G=(V,E) – Đường đi đơn trong G đượcgọilàđường điEulernếu nó đi qua tấtcả các cạnh, mỗicạnh mộtlần. –Chutrìnhđơn trong G đượcgọilàchu trình Euler nếu nó đi qua tấtcả các cạnh, mỗicạnh mộtlần. – Đồ thị G đượcgọilàđồ thị Euler nếu có chu trình Euler. – Đồ thị G đượcgọilàđồ thị nửaEulernếucóđường đi Euler. 26/03/2011 Lý thuyết đồ thị 2
3. 4.1 Đồ thị Euler 3 Ví dụ: Đồ thị G1có các đường điEulerlà: 2 4 G d1:123425415 1 5 d2:124325145 1 Đồ thị nửa Euler 3 Đồ thị G có các chu trình Euler là: 2 2 4 C1: 1 2 3 4 2 5 4 1 5 6 1 G2 C2: 1 2 4 3 2 5 1 4 5 6 1 1 5 Đồ thị Euler 6 26/03/2011 Lý thuyết đồ thị 3
4. 4.1 Đồ thị Euler Định lý 1 Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh củaGđềucóbậcchẵ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ậclẻ. 26/03/2011 Lý thuyết đồ thị 4
5. 4.1 Đồ thị Euler Thuật toán Fleury xác định chu trình Euler Xuấtpháttừ một đỉnh bấtkỳ củaG,đitheocáccạnh một cách tùy ý, chỉ cầntuânthủ hai quy tắcsau: i) Xóa bỏ cạnh đã đi qua và đồng thờixóacả những đỉnh cô lậptạo thành. ii) Ở mỗibước, chỉđiquacầu khi không còn cách chọnlựa nào khác. a b c d Ví dụ: Tìm chu trình ở Euler trong đồ thị h g f e 26/03/2011 Lý thuyết đồ thị 5
6. 4.1 Đồ thị Euler Đị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 26/03/2011 Lý thuyết đồ thị 6
7. 4.2 Đồ thị Hamilton Định nghĩa Xét đồ thị G=(V,E) – Đường đitrênGđượcgọilàđường đi Hamilton nếunó đi qua tấtcả các đỉnh, mỗi đỉnh mộtlần. –ChutrìnhtrênGđượcgọilàchu trình Hamilton nếunó đi qua tấtcả các đỉnh, mỗi đỉnh mộtlần. – Đồ thị G đượcgọilàđồ thị Hamilton nếucóchutrình Hamilton. – Đồ thị G đượcgọilàđồ thị nửa Hamilton nếucóđường đi Hamilton. 26/03/2011 Lý thuyết đồ thị 7
8. 4.2 Đồ thị Hamilton 3 Ví dụ: Đồ thị G1có các đường đi Hamilton là: 2 4 G d1:34251 1 d2:34512 1 5 Đồ thị nửa Hamilton 3 Đồ thị G2 có các chu trình Hamilton là: 2 4 C1: 1 2 3 4 5 6 1 G2 C2: 1 6 5 2 3 4 1 1 5 Đồ thị Hamilton 6 26/03/2011 Lý thuyết đồ thị 8
9. 4.2 Đồ thị Hamilton Định lý 3 (Dirak 1952) Đơn đồ thị vô hướng G vớinđỉ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ớinđỉnh. Nếu deg+(v) ≥ n/2, deg-(v) ≥ n/2, ∀v thì G là đồ thị Hamilton. 26/03/2011 Lý thuyết đồ thị 9
10. 4.2 Đồ thị Hamilton Đồ thịđấuloạilàđồ thị có hướng mà trong đóhaiđỉnh bất kỳ củanóđượcnốivới nhau bởi đúng một cung. Định lý 5 i) Mọi đồ thịđấuloạilànửa Hamilton. ii) Mọi đồ thịđấuloại liên thông mạnh là Hamilton 26/03/2011 Lý thuyết đồ thị 10
11. 4.2 Đồ thị Hamilton Định lý 6 (Ore, 1960) Cho đồ thị Gcónđỉnh. Nếu deg(i)+deg(j)≥ n≥3vớiivà jlàhaiđỉnh không kề nhau tùy ý thì G là Hamilton. 26/03/2011 Lý thuyết đồ thị 11
12. 4.2 Đồ thị Hamilton Quy tắc để xây dựng một chu trình Hamilton (H) Quy tắc1.Tấtcả các cạnh kề với đỉnh bậc2phải ở trong H Quy tắc2.Không có chu trình con (chu trình có chiềudài <n) nào đượctạo thành trong quá trình xây dựng H. Quy tắc3. Khi chu trình Hamilton mà ta đang xây dựng đi qua đỉnh i thì xóa tấtcả các cạnh kề vớiimàtachưa dùng (vì không được dùng đếnnữa). Điềunàylạicóthể cho ta mộtsốđỉnh bậc2vàtalại dùng quy tắc1. Quy tắc4.Không có đỉnh cô lậphayđỉnh treo nào được tạo nên sau khi áp dụng quy tắc3. 26/03/2011 Lý thuyết đồ thị 12
13. 4.2 Đồ thị Hamilton Ví dụ Đồ thị sau có là đồ thị Hamilton không? 1 2 3 Giả sử Gcóchutrình Hamilton H. Theo quy tắc1, 4 5 6 tấtcả các cạnh kề với đỉnh bậc2đều ở trong H: 12, 14, 7 8 9 23, 36, 47, 78, 69, 89. Ta có chutrìnhconlà1,2,3,6,9, 8, 7, 4, 1. Vậy G không là đồ thị Hamilton. 26/03/2011 Lý thuyết đồ thị 13