›
›

Bài giảng Lý thuyết đồ thị - Chương 3: Các bài toán đường đi

ppt 74 trang ngocly 2470
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 3: Các bài toán đường đi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_ly_thuyet_do_thi_chuong_3_cac_bai_toan_duong_di.ppt

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 3: Các bài toán đường đi

  1. CÁC BÀI TOÁN ĐƯỜNG ĐI ntsonptnk@gmail.com
  2. NỘI DUNG Đường đi ngắn nhất Bài toán Nguyên lý Bellman Thuật toán Dijkstra Thuật toán Floyd Thuật toán Ford-Bellman Đồ thị Euler Đồ thị Hamilton Lý thuyết đồ thị , chương 3 - Nguyễn Thanh Sơn 2
  3. 0 8 A 4 2 8 2 3 7 1 B C D 3 9 5 8 2 5 E F ĐƯỜNG ĐI NGẮN NHẤT Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 3
  4. BÀI TOÁN Cho đồ thị có hướng có trọng G=(X, E) và hai đỉnh s, t X, gọi P là một đường đi từ đỉnh s đến đỉnh t, trọng lượng (hay giá) của đường đi P được định nghĩa là: L(P) = (e P)L(e) Bài toán: tìm đường đi từ s đến t có trọng lượng nhỏ nhất Lý thuyết đồ thị - Nguyễn Thanh Sơn 4
  5. NHẬN XÉT  Bài toán được phát biểu cho đồ thị có hướng có trọng, nhưng các thuật toán sẽ trình bày đều có thể áp dụng cho các đồ thị vô hướng có trọng bằng cách xem mỗi cạnh của đồ thị vô hướng như hai cạnh có cùng trọng lượng nối cùng một cặp đỉnh nhưng có chiều ngược nhau.  Khi tìm đường đi ngắn nhất có thể bỏ bớt đi các cạnh song song và chỉ chừa lại một cạnh có trọng lượng nhỏ nhất.  Đối với các khuyên có trọng lượng không âm thì cũng có thể bỏ đi mà không làm ảnh hưởng đến kết quả của bài toán. Đối với các khuyên có trọng lượng âm thì có thể đưa đến bài toán đường đi ngắn nhất không có lời giải. Lý thuyết đồ thị - Nguyễn Thanh Sơn 5
  6. ĐIỀU KIỆN TỒN TẠI LỜI GiẢI P là một đường đi từ s đến t, giả sử P có chứa một mạch . Nếu L() 0 thì có thể cải tiến đường đi P bằng cách bỏ đi mạch . Nếu L() < 0 thì không tồn tại đường đi ngắn nhất từ đỉnh s đến đỉnh t vì nếu quay vòng tại  càng nhiều vòng thì trọng lượng đường đi P càng nhỏ đi, tức là L(P)→ - . k s t  Lý thuyết đồ thị - Nguyễn Thanh Sơn 6
  7. DỮ LIỆU NHẬP Ma trận trọng lượng LNxN được định nghĩa: Lij = trọng lượng cạnh nhỏ nhất nối i đến j nếu có, Lij = nếu không có cạnh nối i đến j. Khi cài đặt thuật toán có thể dùng 0 thay cho bằng cách đưa thêm một số kiểm tra thích hợp. 12 B 0 12 7 A 16 0 15 14 7 5 15 14 0 5 0 C D Lý thuyết đồ thị - Nguyễn Thanh Sơn 7
  8. P k P s 1 2 t ’ P1 NGUYÊN LÝ BELLMAN Lý thuyết đồ thị - Nguyễn Thanh Sơn 8
  9. NGUYÊN LÝ BELLMAN Gọi P là đường đi ngắn nhất từ đỉnh s đến đỉnh t; k P. Giả sử P=P1P2 với P1 là đường đi con của P từ s đến k và P2 là đường đi con của P từ k đến t. Khi đó P1 cũng là đường đi ngắn nhất từ s đến k. P k P s 1 2 t ’ P1 L(P1’) < L(P1) L(P1’P2) < L(P1P2)=L(P) Lý thuyết đồ thị - Nguyễn Thanh Sơn 9
  10. 0 8 A 4 2 8 7 2 1 3 B C D 5 3 9 8 2 5 E F TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ CÓ TRỌNG SỐ DƯƠNG THUẬT TOÁN DIJKSTRA Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 10
  11. THUẬT TOÁN DIJKSTRA Input: N, L, s, t – số đỉnh, ma trận trọng lượng, đỉnh xuất phát, đỉnh kết thúc Output: D, Labels – D[k]: trọng lượng ĐĐNN s→k, Labels[k]: đỉnh ngay trước k trong ĐĐNN s→k 1. V=X; D[s]=0; D[k]= , k X\{s}; Labels[k]=-1, k X. 2. Trong khi t V: 1. Chọn đỉnh v V với D[v] nhỏ nhất; 2. V := V\{v}; 3. Với mọi đỉnh k V và có cạnh nối từ v đến k, Nếu D[k] > D[v]+Lvk thì D[k] = D[v]+Lvk và Labels[k]=v Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 11
  12. VÍ DỤ d(u) = 50 d(z) = 75 u s z d(u) = 50 d(z) = 60 u s z Cập nhật độ dài ĐĐ từ s đến đỉnh z: 75 → 60 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 12
  13. VÍ DỤ Đồ thị G gồm 7 đỉnh, 12 cạnh như hình bên. Tìm 2 đường đi ngắn nhất từ đỉnh 9 8 1 đến đỉnh 5 4 3 0 9 3 6 1 3 1 0 8 4 6 8 5 0 5 2 4 1 0 8 4 5 0 17 7 12 0 12 17 6 2 4 0 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 13
  14. VÍ DỤ V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có màu xanh lá -1 2 9 8 0 4 3 -1 1 3 1 -1 4 6 -1 5 2 8 4 7 5 -1 -1 12 17 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 14
  15. VÍ DỤ V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có màu xanh lá 9 1 2 9 8 0 4 3 -1 1 3 1 -1 4 6 3 1 5 2 8 6 4 7 5 -1 1 12 17 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 15
  16. VÍ DỤ V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có màu xanh lá 7 4 2 9 8 0 4 4 3 -1 1 3 1 4 4 6 3 1 5 2 8 6 4 11 7 5 4 1 12 17 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 16
  17. VÍ DỤ V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có màu xanh lá 7 4 2 9 8 0 4 4 3 -1 1 3 1 4 4 6 3 1 5 2 8 6 4 9 7 5 3 1 12 17 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 17
  18. VÍ DỤ V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có màu xanh lá 7 4 2 9 8 0 4 4 3 -1 1 3 1 4 4 6 3 1 5 2 8 6 4 9 7 5 3 1 12 17 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 18
  19. VÍ DỤ ĐĐNN từ 1 đến 5 có trọng lượng D[5]=9: 5  3  4  1 7 4 2 9 8 0 4 4 3 -1 1 3 1 4 4 6 3 1 5 2 8 6 4 9 7 5 3 1 12 17 6 26 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 19
  20. GIÁ TRỊ CÁC BIẾN D, Labels D Labels 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 0 0 -1 -1 -1 -1 -1 -1 -1 1 9 3 6 1 1 -1 1 -1 -1 1 2 7 4 11 6 2 4 4 4 -1 1 3 7 9 6 3 4 3 -1 1 4 7 9 4 4 3 -1 5 9 5 3 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 20
  21. VÍ DỤ 0 0 8 A 4 8 A 4 2 2 8 7 2 1 4 8 7 2 1 3 B C D B C D 3 9 5 3 9 8 2 5 2 5 E F E F 0 0 8 A 4 8 A 4 2 2 8 7 2 1 3 7 7 2 1 3 B C D B C D 5 3 9 11 5 3 9 8 2 5 2 5 E F E F Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 21
  22. VÍ DỤ 0 8 A 4 2 7 7 2 1 3 B C D 5 3 9 8 2 5 E F 0 8 A 4 2 7 7 2 1 3 B C D 5 3 9 8 2 5 E F Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 22
  23. THUẬT TOÁN DIJKSTRA – CÀI ĐẶT Graph Graph::Dijkstra(int s, int t) { //Tìm đường đi ngắn nhất từ s đến t } Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 23
  24. THUẬT TOÁN DIJKSTRA – CÀI ĐẶT Graph Graph::PrintPath(int s, int t) { int temp[MAX]; int dem = 0; //In đường đi ngắn nhất từ s đến t dựa vào Labels while(Labels[t] != -1) { temp[dem++]=t; t=Labels[t]; } temp[dem++]=s; while (dem > 0) printf(“%d “, temp[ dem]); } Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 24
  25. TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA CÁC CẶP ĐỈNH TRÊN ĐỒ THỊ THUẬT TOÁN FLOYD Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 25
  26. THUẬT TOÁN FLOYD Input: N, L – số đỉnh, ma trận trọng lượng của G(X, E) Output: L, Nexts – L[u, v]: trọng lượng ĐĐNN u→v, Nexts[u, v]: đỉnh ngay sau u trong ĐĐNN u→v 1.Nếu L[u, v] : Nexts[u, v]=v Ngược lại: Nexts[u, v]=-1 , (u, v) X2. 2.Với mọi t X Với mọi u X có L[u, t] Với mọi v X có L[t, v] Nếu L[u, v] > L[u, t] + L[t, v] thì 1. L[u, v] = L[u, t] + L[t, v] 2. Nexts[u, v] = Nexts[u, t] Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 26
  27. VÍ DỤ Xác định đường đi ngắn nhất giữa các cặp đỉnh trên đồ thị gồm 4 đỉnh 6 cạnh 2 4 8 9 4 1 3 3 1 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 27
  28. VÍ DỤ 2 4 9 2 -1 8 2 -1 3 -1 3 4 4 1 3 -1 -1 1 -1 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 28
  29. VÍ DỤ t = 1 u = 3 v = 2 2 4 9 2 -1 8 14 2 -1 3 -11 3 4 4 1 3 -1 -1 1 -1 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 29
  30. VÍ DỤ t = 1 u = 3 v = 4 2 4 9 2 -1 8 14 2 -1 3 1 3 4 4 1 3 -1 8-11 1 -1 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 30
  31. VÍ DỤ t = 2 u = 1 v = 3 2 4 9 2 -1 8 14 2 -1 3 1 3 4 4 1 3 -1 8 1 1 17 -21 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 31
  32. VÍ DỤ t = 2 u = 3 v = x 2 4 9 2 -1 8 14 2 -1 3 1 3 4 4 1 3 -1 8 1 1 17 2 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 32
  33. VÍ DỤ t = 2 u = 4 v = 3 2 4 9 2 -1 8 14 2 -1 3 1 3 4 4 1 3 -1 8 1 1 17 2 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 33
  34. VÍ DỤ t = 3 u = 1 v = 2 2 4 9 2 -1 8 14 2 -1 3 1 3 4 4 1 3 -1 8 1 1 17 2 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 34
  35. VÍ DỤ t = 3 u = 1 v = 4 2 4 9 2 -1 8 14 2 -1 3 1 3 4 4 1 3 -1 8 1 1 17 2 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 35
  36. VÍ DỤ t = 3 u = 2 v = 1, 4 2 4 2 16 9 13 3 8 14 2 3 3 1 3 4 4 1 3 -1 8 1 1 17 2 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 36
  37. VÍ DỤ t = 3 u = 4 v = 1, 2 2 4 2 16 9 13 3 8 14 2 3 3 1 3 4 4 1 3 6 3 8 1 1 17 2 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 37
  38. VÍ DỤ t = 4 u = 1 v = 2, 3 2 4 2 16 7 13 3 8 14 4 3 3 1 3 4 4 1 3 6 3 8 1 1 4 4 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 38
  39. VÍ DỤ t = 4 u = 2 v = 1, 3 2 4 2 16 7 13 3 8 14 4 3 3 1 3 4 4 1 3 6 3 8 1 1 4 4 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 39
  40. VÍ DỤ t = 4 u = 3 v = 1, 2 2 4 2 16 7 13 3 8 12 4 3 3 1 3 4 4 1 3 6 3 8 1 1 4 4 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 40
  41. ? 0 k s t  TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ CÓ CẠNH ÂM THUẬT TOÁN BELLMAN Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 41
  42. THUẬT TOÁN BELLMAN Input: N, L, u – số đỉnh, ma trận trọng lượng của G(X, E), đỉnh xuất phát Output: , Labels – (k, v): trọng lượng ĐĐNN u→v sau k bước lặp, Labels[v]: đỉnh ngay trước v trong ĐĐNN u→v 1. (0, u)=0; (0, v)= v X\{u}; Labels[v] = -1 v X; 2. Lặp với k = 1, 2, N-1 1.i X, chọn j X sao cho (k-1, j)+Lji đạt nhỏ nhất; nếu j i: 1. (k, i)= (k-1, j)+Lji 2.Labels[i] = j 2.Nếu (k) = (k-1): (k, v) là đường đi ngắn nhất u → v 3. Nếu vẫn còn thay đổi sau bước lặp N-1: từ u đã đi đến mạch âm Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 42
  43. VÍ DỤ Tìm đường 1 đi ngắn nhất 1 2 từ đỉnh 3 -2 đến các đỉnh 2 8 còn lại 3 5 4 4 -1 1 2 5 6 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 43
  44. VÍ DỤ k = 0 1 -1 1 2 -1 -2 2 8 0 3 5 -1 4 -1 4 -1 1 2 -1 5 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 44
  45. VÍ DỤ k = 1 1 -1 1 2 -1 -2 2 8 0 5 3 5 -1 4 -13 4 -1 1 -1 2 4 -31 5 6 -31 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 45
  46. VÍ DỤ k = 2 1 -1 1 2 -1 -2 2 8 0 3 5 5 -1 4 3 4 -1 1 -1 2 41 3 5 6 35 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 46
  47. VÍ DỤ k = 3 1 -1 1 2 -1 -2 2 8 0 -1 3 5 25 4 63 4 -1 1 -1 2 1 3 5 6 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 47
  48. VÍ DỤ k = 4 1 -1 1 2 -1 DỪNG -2 2 8 0 -1 3 5 2 4 6 4 -1 1 -1 2 1 3 5 6 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 48
  49. GIÁ TRỊ CÁC BIẾN , Labels Labels k/v 1 2 3 4 5 6 k/v 1 2 3 4 5 6 0 0 0 -1 -1 -1 -1 -1 -1 1 0 5 -1 4 1 -1 -1 -1 3 3 3 2 0 5 -1 1 2 -1 -1 -1 3 3 5 3 0 2 -1 1 3 -1 -1 -1 6 3 5 4 0 2 -1 1 4 -1 -1 -1 6 3 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 49
  50. VÍ DỤ Tìm đường 1 đi ngắn nhất 1 2 từ đỉnh 1 -2 đến các đỉnh 2 8 còn lại 3 5 4 4 -1 1 2 5 6 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 50
  51. VÍ DỤ k = 0 1 0 -1 1 2 -1 -2 2 8 3 5 -1 4 -1 4 -1 1 2 -1 5 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 51
  52. VÍ DỤ k = 1 1 0 1 -1 1 2 1 -2 2 8 2 3 5 1 4 -1 4 -1 1 2 -1 5 6 -1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 52
  53. VÍ DỤ k = 2 1 -1 1 2 1 2 1 -2 2 8 2 7 3 5 1 4 3 4 -1 1 1 2 6 3 5 6 3 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 53
  54. VÍ DỤ k = 3 1 -1 0 2 1 2 1 -2 2 8 1 7 3 5 1 4 3 4 -1 1 1 2 3 3 5 6 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 54
  55. VÍ DỤ k = 4 1 -2 0 2 1 2 1 -2 2 8 1 6 3 5 1 4 3 4 -1 1 0 2 3 3 5 6 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 55
  56. VÍ DỤ k = 5 1 -1 DỪNG – -2 2 1 2 1 CÓ MẠCH -2 ÂM 2 8 0 4 3 5 1 4 6 4 -1 1 0 2 2 3 5 6 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 56
  57. Konigsberg, Hmmm Leonhard Euler (1707 – 1783) ĐỒ THỊ EULER Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 57
  58. BÀI TOÁN 7 CHIẾC CẦU Thành phố Konigsberg (Đức) bị chia thành 4 vùng do 2 nhánh của 1 dòng sông. Có 7 chiếc cầu nối những vùng nầy với nhau. Bài toán: xuất phát từ một vùng đi dạo qua mỗi chiếc cầu đúng một lần và trở về nơi xuất phát. Năm 1736, nhà toán học Euler đã mô hình bài toán nầy bằng một đồ thị vô hướng với mỗi đỉnh ứng với một vùng, mỗi cạnh ứng với một chiếc cầu Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 58
  59. BÀI TOÁN 7 CHIẾC CẦU A C D B A C D B Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 59
  60. ĐỊNH NGHĨA  DÂY CHUYỀN EULER: dây chuyền đi qua tất cả các cạnh trong đồ thị, mỗi cạnh đúng một lần.  CHU TRÌNH EULER: dây chuyền Euler có đỉnh đầu trùng với đỉnh cuối.  ĐƯỜNG ĐI EULER: đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.  MẠCH EULER: đường đi Euler có đỉnh đầu trùng với đỉnh cuối.  ĐỒ THỊ EULER VÔ HƯỚNG: đồ thị vô hướng có chứa một chu trình Euler.  ĐỒ THỊ EULER CÓ HƯỚNG: đồ thị có hướng có chứa một mạch Euler. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 60
  61. ĐỊNH LÝ EULER Đồ thị vô hướng G=(X, E) 1. G là đồ thị Euler G liên thông và d(x) chẵn x X. 2. G có chứa dây chuyền Euler và không chứa chu trình chu trình Euler G liên thông có chứa đúng hai đỉnh bậc lẻ. Đồ thị có hướng G=(X, E) 1. G là đồ thị Euler G liên thông và d+(x)=d-(x) x X. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 61
  62. VÍ DỤ a e e a d b c a d d b c b c (G ) (G ) 1 2 (G3) Liên thông và có 2 Liên thông và các đỉnh bậc lẻ → có có đường đi đỉnh đều có bậc chẵn dây chuyền Euler: Euler: bacbd → có chu trình Euler: bacdaedbc bacdaedbcb Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 62
  63. GIẢI THUẬT FLEURY Cạnh e của đồ thị G được gọi là CẦU nếu xóa e khỏi đồ thị thì làm tăng số thành phần liên thông của G. Giải thuật Gọi chu trình cần tìm là C 1.Khởi tạo: Chọn một đỉnh bất kỳ cho vào C. 2.Lặp trong khi G vẫn còn cạnh 1. Chọn cạnh e nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cầu nếu không còn cạnh nào khác để chọn. 2. Bổ sung e và đỉnh cuối của nó vào C. 3. Xóa e khỏi G. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 63
  64. VÍ DỤ 1 2 3 4 5 3 1 2 4 3 1 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 64
  65. GiẢI THUẬT XÁC ĐỊNH CÁC CHU TRÌNH THÀNH PHẦN Input: đồ thị Euler G(X, E) Output: chu trình Euler C của G 1.Chọn đỉnh v X; C = {v} 2.Lặp trong khi G còn cạnh 1. Chọn đỉnh v C còn cạnh trong G 2. Tìm chu trình C’ xuất phát từ v. 3. Ghép C’ vào C 4. Loại bỏ các cạnh của C’ khỏi G Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 65
  66. VÍ DỤ 1 2 3 1 3 4 5 3 2 4 3 1 5 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 66
  67. Sir William Rowan Hamilton (1805-1865) ĐỒ THỊ HAMILTON Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 67
  68. BÀI TOÁN KHỞI ĐIỂM “Xuất phát từ một đỉnh của khối thập nhị diện đều, hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh khác, mỗi đỉnh qua đúng một lần, sau đó trở về đỉnh xuất phát”. Bài toán nầy được nhà toán học Hamilton đưa ra vào năm 1859 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 68
  69. ĐỊNH NGHĨA Đồ thị vô hướng G(X, E) DÂY CHUYỀN HAMILTON: dây chuyền đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần. CHU TRÌNH HAMILTON: dây chuyền Hamilton và một cạnh trong đồ thị nối đỉnh đầu của dây chuyền với đỉnh cuối của nó. ĐỒ THỊ HAMILTON: đồ thị có chứa một chu trình Hamilton. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 69
  70. MỘT SỐ KẾT QUẢ Đồ thị đủ luôn là đồ thị Hamilton. Với n lẻ 3 thì Kn có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung. Đồ thị lưỡng phân G với hai tập đỉnh X1, X2 và X1=X2=n. Nếu d(x) n/2 x của G thì G là đồ thị Hamilton. Đồ thị vô hướng đơn G gồm n đỉnh và m cạnh. Nếu m (n2-3n+6)/2 thì G là đồ thị Hamilton. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 70
  71. Đồ thị vô hướng đơn G gồm n đỉnh với n 3 Nếu d(x) n/2 x của G thì G là đồ thị Hamilton. Nếu d(x) (n-1)/2 x của G thì G có dây chuyền Hamilton. Nếu d(x)+d(y) n với mọi cặp đỉnh x, y không kề nhau của G thì G là đồ thị Hamilton. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 71
  72. QUI TẮC XÁC ĐỊNH 1. Nếu G có đỉnh bậc < 2 thì G không có chu trình Hamilton 2. Nếu đỉnh có bậc 2 thì 2 cạnh kề với nó phải nằm trong chu trình Hamilton 3. Các cạnh thừa (ngoài 2 cạnh đã chọn trong chu trình Hamilton) phải được bỏ đi trong quá trình xác định chu trình 4. Nếu quá trình xây dựng tạo nên một chu trình con thì đồ thị không có chu trình Hamilton Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 72
  73. VÍ DỤ 2 4 3 5 1 Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 73
  74. BÀI TẬP 1. Chứng minh nguyên lý Bellman 2. Chứng minh tính đúng đắn của các thuật toán Dijkstra, Floyd, Bellman 3. Cài đặt thuật toán xác định chu trình Euler 4. Xác định các “nét” của Đồ thị K nét. Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 74