›
›

Bài giảng Toán rời rạc - Lê Văn Luyện

pdf 88 trang huongle 11760
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Lê Văn Luyện", để 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:

  • pdfbai_giang_toan_roi_rac_le_van_luyen.pdf

Nội dung text: Bài giảng Toán rời rạc - Lê Văn Luyện

  1. LOGOChương V Lê Văn Luyện email: lvluyen@yahoo.com TỐN RỜI RẠC
  2. Đồ thị Đồ thị b c a d e h k g
  3. Đồ thị Nội dung - Những khái niệm và tính chất cơ bản - Biểu diễn đồ thị bằng ma trận - Đẳng cấu - Đường đi, chu trình, đồ thị liên thơng - Bài tốn đường đi ngắn nhất
  4. 1. Những khái niệm và tính chất cơ bản Định nghĩa đồ thị Định nghĩa 1. Đồ thị vơ hướng G = (V, E) gồm: i) V là tập hợp khác rỗng mà các phần tử của nĩ gọi là đỉnh (vertex) của G. ii) E là đa tập hợp gồm các cặp khơng sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cạnh (edge) của G. Ký hiệu uv. 4
  5. 1. Những khái niệm và tính chất cơ bản b c a d e h k g 5
  6. 1. Những khái niệm và tính chất cơ bản Chú ý  Ta nĩi cạnh uv nối u với v, cạnh uv kề với u,v.  Nếu uv∈E thì ta nĩi đỉnh u kề đỉnh v.  Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song song.  Cạnh uu cĩ hai đầu mút trùng nhau gọi là một khuyên. 6
  7. 1. Những khái niệm và tính chất cơ bản  Định nghĩa 2. Đồ thị vơ hướng khơng cĩ cạnh song song và khơng cĩ khuyên gọi là đơn đồ thị vơ hướng.  Định nghĩa 3. Đồ thị vơ hướng cho phép cĩ cạnh song song nhưng khơng cĩ khuyên gọi là đa đồ thị vơ hướng.  Định nghĩa 4. Đồ thị vơ hướng cho phép cĩ cạnh song song và cĩ khuyên gọi là giả đồ thị 8
  8. b c a d e h k b g a b c d a d c 9
  9. 10 1. Những khái niệm và tính chất cơ bản Detroit New York San Francisco Chicago Denver Washington Los Angeles
  10. 11 1. Những khái niệm và tính chất cơ bản Detroit New York San Francisco Chicago Denver Washington Los Angeles
  11. 12 1. Những khái niệm và tính chất cơ bản Detroit New York San Francisco Chicago Denver Washington Los Angeles
  12. 1. Những khái niệm và tính chất cơ bản Định nghĩa 5 Đa đồ thị cĩ hướng G =(V,E) gồm: i) V là tập hợp khác rỗng mà các phần tử của nĩ gọi là đỉnh của G. ii) E là đa tập hợp gồm các cặp cĩ sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cung (cạnh) của G. Ký hiệu uv. Ta nĩi cung uv đi từ u đến v, cung uv kề với u,v 13
  13. b b a a d c d c 14
  14. 1. Những khái niệm và tính chất cơ bản Chú ý  Nếu uv là một cung thì ta nĩi: . Đỉnh u và v kề nhau. . Đỉnh u gọi là đỉnh đầu (gốc), đỉnh v là đỉnh cuối (ngọn) của cung uv. Đỉnh v là đỉnh sau của đỉnh u.  Hai cung cĩ cùng gốc và ngọn gọi là cung song song.  Cung cĩ điểm gốc và ngọn trùng nhau gọi là khuyên. 15
  15. 1. Những khái niệm và tính chất cơ bản Định nghĩa 6. Đa đồ thị cĩ hướng khơng chứa các cạnh song song gọi là đồ thị cĩ hướng 17
  16. Detroit New York Chicago San Francisco Denver Washington Los Angeles
  17. Detroit New York Chicago San Francisco Denver Washington Los Angeles
  18. 1. Những khái niệm và tính chất cơ bản Bậc của đỉnh  Cho đồ thị vơ hướng G = (V,E). Bậc của đỉnh v, ký hiệu deg(v), là số cạnh kề với v, trong đĩ một khuyên tại một đỉnh được đếm hai lần cho bậc của đỉnh ấy. 20
  19. Bậc đỉnh a: deg(a) = 2 a Bậc đỉnh b: deg(b) = 5 b c d Bậc đỉnh c: deg(c) = 3 Bậc đỉnh d: deg(d) = 2 21
  20. a b c d e f Bậc của các đỉnh? 22
  21. 1. Những khái niệm và tính chất cơ bản Cho đồ thị cĩ hướng G = (V, E), v∈V 1) deg-(v):= số cung cĩ đỉnh cuối là v, gọi là bậc vào của v. 2) deg +(v):= số cung cĩ đỉnh đầu là v,gọi là bậc ra của v 3) deg(v):= deg- (v) + deg+(v)  Đỉnh bậc 0 gọi là đỉnh cơ lập. Đỉnh bậc 1 gọi là đỉnh treo 23
  22. a b Bậc đỉnh a: deg-(a)= 1 ; deg+(a)=1 Bậc đỉnh b: deg-(b)= 1 ; deg+(b)=3 c d e Bậc đỉnh c: deg-(c)= 1 ; deg+(c)=2 f Bậc đỉnh d: deg-(d)= 0 ; deg+(d)=0 Bậc đỉnh e: deg-(e)= 1 ; deg+(e)=0 Bậc đỉnh f: deg-(f)= 2 ; deg+(f)=0 25
  23. 1. Những khái niệm và tính chất cơ bản Định lí Cho đồ thị G = (V,E), m là số cạnh (cung) 1) 2mv= ∑ deg( ) vV∈ 2) Nếu G cĩ hướng thì: mv=∑∑deg−+ ( ) = deg ( v ) vV∈∈ vV 3) Số đỉnh bậc lẻ của đồ thị là số chẵn 26
  24. 2. Biểu diễn đồ thị bằng ma trận Ta sử dụng ma trận kề. Cho G = (V,E) với V={1,2, ,n}. Ma trận kề của G là ma trận A = (aij)n xác định như sau: aij = số cạnh (số cung) đi từ đỉnh i đến đỉnh j 27
  25. 2. Biểu diễn đồ thị bằng ma trận Tìm ma trận kề a b c d a a 0110 b  b 1011 c  c 1101 d d  0110 28
  26. 2. Biểu diễn đồ thị bằng ma trận Tìm ma trận kề abcde f b a 021000 a  b 201011 c 110001 c d e  d 000000 e 010020 f  f 011000 29
  27. 3. Đẳng cấu Định nghĩa Cho hai đơn đồ thị G = (V,E) và G’= (V’,E’). Ta nĩi rằng G đẳng cấu G’, ký hiệu G ≅ G’, nếu tồn tại song ánh f :V→ V’sao cho: uv là cạnh của G ⇔ f(u)f(v) là cạnh của G’ 30
  28. 3. Đẳng cấu Chú ý  Nếu G và G’ là các đơn đồ thị vơ hướng đẳng cấu qua ánh xạ f thì chúng cĩ:  Cùng số đỉnh  Cùng số cạnh  Cùng số đỉnh với bậc cho sẵn (vd: số đỉnh bậc 2 của G và G’ bằng nhau)  deg v = deg f(v) 31
  29. 3. Đẳng cấu 32
  30. Ví dụ Khơng cĩ đỉnh bậc 1 b deg(e) = 1 b a c a c d e e d Khơng đẳng cấu 33
  31. b 2 a 1 3 d c 6 e 4 5 f Đẳng cấu 34
  32. a 2 b 1 4 5 d e 3 c Khơng đẳng cấu 35
  33. Đẳng cấu khơng? a b d c e 36
  34. 4. Đường đi, chu trình, đồ thị liên thơng: Định nghĩa. Cho đồ thị vơ hướng G = (V,E). Trên V ta định nghĩa quan hệ tương đương như sau: u~v ⇔ u ≡ v hay cĩ một đường đi từ u đến v a) Nếu u~v thì ta nĩi hai đỉnh u và v liên thơng với nhau b) Mỗi lớp tương đương được gọi là một thành phần liên thơng của G c) Nếu G chỉ cĩ một thành phần liên thơng thì G gọi là liên thơng 37
  35. 4. Đường đi, chu trình, đồ thị liên thơng: Định nghĩa. Cho G = (V,E) là đồ thị vơ hướng liên thơng a) Đỉnh v được gọi là đỉnh khớp nếu G – v khơng liên thơng (G – v là đồ thị con của G cĩ được bằng cách xố v và các cạnh kề với v) b) Cạnh e được gọi là cầu nếu G- e khơng liên thơng (G-e là đồ thị con của G cĩ được bằng cách xố cạnh e). 39
  36. 4. Đường đi, chu trình, đồ thị liên thơng: Cho G = (V,E) là đồ thị vơ hướng u,v∈V a) Đường đi (dây chuyền) cĩ chiều dài k nối hai đỉnh u,v là dãy đỉnh và cạnh liên tiếp nhau v0e1v1e2 vk-1ekvk sao cho: v 0=u ,v k = v, e i=v i-1v i , i=1,2, ,k 41
  37. 4. Đường đi, chu trình, đồ thị liên thơng: a) Đường đi khơng cĩ cạnh nào xuất hiện quá một lần gọi là đường đi đơn b) Đường đi khơng cĩ đỉnh nào xuất hiện quá một lần gọi là đường đi sơ cấp c) Đường đi được gọi là chu trình nếu nĩ bắt đầu và kết thúc tại cùng một đỉnh d) Đường đi được gọi là chu trình sơ cấp nếu nĩ bắt đầu và kết thúc tại cùng một đỉnh và khơng cĩ đỉnh nào xuất hiện quá một lần 42
  38. Chu trình sơ cấp nào khơng? (a,e1,b,e2,c,e3,d,e4,b ) là đường đi từ đỉnh a tới đỉnh b cĩ chiều dài là 4. Tuy nhiên, trong trường hợp này, đồ thị của chúng ta là đơn đồ thị, do vậy cĩ thể gọi đường đi này bằng 1 cách ngắn gọn như sau: (a,b,c,d,b) Chu trình sơ cấp: (b,c,d,b) (b,f,e,b) 43
  39. Đường đi Euler Euler 44
  40. Đường đi Euler Bài tốn. Thị trấn Kưnigsberg chia thành 4 phần bởi các nhánh của dịng sơng Pregel Bốn phần này được nối kết bởi 7 cây cầu 45
  41. Đường đi Euler 46
  42. Đường đi Euler Câu hỏi. Cĩ thể đi qua bảy cây cầu mà khơng cĩ cây cầu nào đi quá 1 lần 47
  43. C A D B C A D B 48
  44. Đường đi Euler Đường đi Euler Định nghĩa. 1. Đường đi Euler là đường đi qua tất cả các cạnh mỗi cạnh (cung) đúng một lần. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần. 2. Đồ thị được gọi là đồ thị Euler nếu nĩ cĩ chu trình Euler 49
  45. Đường đi Euler Điều kiện cần và đủ. Cho G = (V,E) là đồ thị vơ hướng liên thơng. G là đồ thị Euler ⇔ Mọi đỉnh của G đều cĩ bậc chẵn. Nếu G cĩ hai đỉnh bậc lẻ cịn mọi đỉnh khác đều cĩ bậc chẵn thì G cĩ đường đi Euler Nhận xét. - Nếu đồ thị G cĩ 2 đỉnh bậc lẻ thì G cĩ 1 đường đi Euler - Nếu đồ thị G cĩ 2k đỉnh bậc lẻ thì ta cĩ thể vẽ đồ thị bằng k nét 50
  46. Đường đi Euler Thuật tốn Fleury để tìm chu trình Euler. Bắt đầu từ một đỉnh bất kỳ của G và tuân theo qui tắc sau: 1. Mỗi khi đi qua một cạnh nào đĩ thì xố nĩ đi, sau đĩ xố đỉnh cơ lập nếu cĩ. 2. Khơng bao giờ đi qua một cầu trừ phi khơng cịn cách đi nào khác. 51
  47. Đường đi Euler a b c d e h g f abcfdcefghbga 52
  48. 5. Bài tốn đường đi ngắn nhất Đồ thị cĩ trọng số 1. Đồ thị G = (V,E) gọi là đồ thị cĩ trọng số (hay chiều dài, trọng lượng) nếu mỗi cạnh(cung) e được gán với một số thực w(e).Ta gọi w(e) là trọng lượng của e. 2. Độ dài của đường đi từ u đến v bằng tổng độ dài các cạnh mà đường đi qua 3. Khoảng cách giữa 2 đỉnh u,v là độ dài ngắn nhất của các đường đi từ u đến v. 53
  49. 5. Bài tốn đường đi ngắn nhất Ma trận khoảng cách (trọng số) Cho G = (V, E), V = {v1,v2, ,vn} là đơn đồ thị cĩ trọng số. Ma trận khoảng cách của G là ma trận D= (dij) xác định như sau: 0 khi i= j  dij =  w() vi v j khi v i v j ∈ E  ∞∉  khi vij v E 54
  50. 5. Bài tốn đường đi ngắn nhất 0 5 31 40 ∞∞∞  ∞0 27 ∞ 73 ∞∞ ∞ 26 0 8 49 25 38  D = ∞∞ ∞0 ∞ 16 ∞ ∞70 ∞∞0 ∞ 9  ∞∞∞∞23 0 12  ∞∞∞∞10 ∞ 0 55
  51. Company Logo 5. Bài tốn đường đi ngắn nhất Các thuật tốn tìm đường đi ngắn nhất - Vét cạn - Dijkstra - Ford – Bellman - Floyd
  52. 5. Bài tốn đường đi ngắn nhất Thuật tốn Dijkstra Bài tốn. Cho G = (V, E) đơn, liên thơng, cĩ trọng số dương (w(uv) > 0 với mọi u khác v). Tìm đường đi ngắn nhất từ u0 đến v và tính khoảng cách d(u 0,v). 57
  53. 5. Bài tốn đường đi ngắn nhất Phương pháp Xác định tuần tự các đỉnh cĩ khoảng cách đến u0 từ nhỏ đến lớn. 1. Trước tiên đỉnh cĩ khoảng cách nhỏ nhất đến u0 là u0. 2. Trong V\{u0} tìm đỉnh cĩ khoảng cách đến u0 nhỏ nhất (đỉnh này phải là một trong các đỉnh kề với u0) giả sử đĩ là u1 58
  54. 3. Trong V\{u0,u1} tìm đỉnh cĩ khoảng cách đến u0 nhỏ nhất (đỉnh này phải là một trong các đỉnh kề với u0 hoặc u1 ) giả sử đĩ là u2 4. Tiếp tục như trên cho đến bao giờ tìm được khoảng cách từ u0 đến mọi đỉnh . Nếu G cĩ n đỉnh thì: 0 = d(u0,u0) < d(u0,u1) ≤ d(u0,u2) ≤ ≤ d(u0,un-1) 59
  55. Thuật tốn Dijkstra Bước1. i:=0, S:=V\{u0}, L(u0):=0, L(v):= ∞ với mọi v ∈S và đánh dấu đỉnh v bởi (∞,-). Nếu n=1 thì xuất d(u0,u0)=0=L(u0) Bước 2. Với mọi v ∈S và kề với ui (nếu đồ thị cĩ hướng thì v là đỉnh sau của ui), đặt L(v):=min{L(v),L(ui)+w(ui v)}. Xác định k =minL(v) ,v∈S. Nếu k=L(vj) thì xuất d(u0,vj)=k và đánh dấu vj bởi (L(vj);ui). ui+1:=vj S:=S\{ui+1} Bước3. i:=i+1 Nếu i = n-1 thì kết thúc Nếu khơng thì quay lại Bước 2 60
  56. 5. Bài tốn đường đi ngắn nhất Bài tập 1. Tìm đường đi ngắn nhất từ u đến các đỉnh cịn lại s r 7 1 4 3 3 x u 1 2 3 t 1 4 w y 3 z 5 61
  57. 7 s r 1 4 3 3 x u 1 2 3 t 1 4 w y 3 z 5 u r s t x y z w 0* (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 62
  58. 7 s r 1 4 3 3 x u 1 2 3 t 1 4 w y 3 z 5 u0 r s t x y z w 0* (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) - (4,u0) (∞,-) (∞,-) (∞,-) (1,u0)* (∞,-) (∞,-) 63
  59. r 7 s 1 4 3 3 x u 1 2 3 t 1 4 w y 3 z 5 u0 r s t x y z w 0* (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) - (4,u0) (∞,-) (∞,-) (∞,-) (1u0)* (∞,-) (∞,-) - (3,y)* (∞,-) (∞,-) (∞,-) - (4,y) (∞,-) 64
  60. 7 r 1 4 3 3 x u 1 2 3 t 1 4 w z y 3 5 u0 r s t x y z w 0* (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) - (4,u0) (∞,-) (∞,-) (∞,-) (1u0)* (∞,-) (∞,-) - (3,y)* (∞,-) (∞,-) (∞,-) - (4,y) (∞,-) - - (10,r) (6,r) (∞,-) - (4,y)* (∞,-) - - (10,r) (6,r)* (∞,-) - - (9,z) - - (9,t) - (7,t)* - - (9,z) - - (8,x)* - - - - (9,z) - - - - - - - (9,z)* 65
  61. 5. Bài tốn đường đi ngắn nhất Cây đường đi s r 3 1 t 1 u x 2 1 y 3 z 5 w 66
  62. Cho đồ thị cĩ trọng số G = (V, E) , V = { v1, v2, v3, v4, v5, v6 , v7} xác định bởi ma trận trọng số D. Dùng thuật tốn Dijkstra tìm đường đi ngắn nhất từ v1 đến các đỉnh v2,v3,v 4, v5, v6,v7 67
  63. 5. Bài tốn đường đi ngắn nhất 0 5 31 40 ∞∞∞  ∞0 27 ∞ 73 ∞∞ ∞ 26 0 8 49 25 38  D = ∞∞ ∞0 ∞ 16 ∞ ∞70 ∞∞0 ∞ 9  ∞∞∞∞23 0 12  ∞∞∞∞10 ∞ 0 68
  64. 5. Bài tốn đường đi ngắn nhất 69
  65. v1 v2 v3 v4 v5 v6 v7 0* (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) - (5,v1)* (31,v1) (40,v1) (∞,-) (∞,-) (∞,-) (31,v )* - - 1 (40,v1) (78,v2) (∞,-) (∞,-) (39,v )* - - - 3 (78,v2) (56,v3) (69,v3) - - - - (78,v2) (55,v4)* (69,v3) (67,v )* - - - - (78,v2) - 6 - - - - (77,v7) - - 70
  66. Dùng thuật tốn Dijsktra để tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z và chiều dài của nĩ trong đồ thị vơ hướng cĩ trọng lượng sau: b 5 d 5 f 4 7 3 2 1 2 z a 3 4 c 6 e 5 g 72
  67. a b c d e f g z 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 0 (4.a) (3.a)* (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 0 (4.a)* - (6.c) (9.c) (∞,-) (∞,-) (∞,-) 0 - - (6.c)* (9.c) (∞,-) (∞,-) (∞,-) 0 - - - (7.d)* (11.d) (∞,-) (∞,-) 0 - - - - (11.d)* (12,e ) (∞,-) 0 - - - - - (12,e )* (18,f ) 0 - - - - - - (16,g ) 73
  68. 5. Bài tốn đường đi ngắn nhất Thuật tốn Ford – Bellman Tìm đường đi ngắn nhất từ u0 đến các đỉnh hoặc chỉ ra đồ thị cĩ mạch âm. Bước 1. L0(u0) =0 và L0(v) = ∞ ∀v ≠u0. Đánh dấu đỉnh v bằng (∞ ,-) ; k=1. Bước 2. Lk(u0) = 0 và Lk(v) =min{Lk-1(u)+w(uv)/u là đỉnh trước của v} Nếu Lk(v)=Lk-1(y)+w(yv)thì đánh dấu đỉnh v bởi (Lk(v),y) 74
  69. Bước 3. Nếu Lk(v) =Lk-1(v) với mọi v, tức Lk(v) ổn định thì dừng. Ngược lại đến bước 4. Bước 4. Nếu k = n thì dừng. G cĩ mạch âm. Nếu k ≤ n-1 thì trở về bước 2 với k:=k+1 75
  70. BT1. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 76
  71. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 77
  72. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 78
  73. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 79
  74. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 80
  75. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 81
  76. 4 2 3 2 7 1 6 1 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 5 0 (4,4) (8,2) (2,6) (4,4) (5,2) 82
  77. 4 2 3 2 7 1 1 6 2 2 -6 8 3 4 5 2 k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 5 0 (4,4) (8,2) (2,6) (4,4) (5,2) 6 0 (4,4) (7,6) (-1,6) (4,4) (5,2) 83
  78. k = n = 6 . Lk(i) chưa ổn định nên đồ thị cĩ mạch âm. Chẳng hạn: 4→2→6→4 cĩ độ dài -3 84
  79. k = n = 6 . Lk(i) chưa ổn định nên đồ thị cĩ mạch âm. Chẳng hạn: 4→2→6→4 cĩ độ dài -3 85
  80. 5. Bài tốn đường đi ngắn nhất BT2. 4 2 3 2 7 1 6 1 2 2 -2 8 3 4 5 2 86
  81. k 1 2 3 4 5 6 0 0 (∞,-) (∞,-) (∞,-) (∞,-) (∞,-) 1 0 (7,1) (∞,-) (8,1) (∞,-) (∞,-) 2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 3 0 (7,1) (10,6) (6,6) (9,2) (8,2) 4 0 (7,1) (10,6) (6,6) (8,4) (8,2) 5 0 (7,1) (10,6) (6,6) (8,4) (8,2) 87
  82. 2 3 2 7 1 6 1 -2 4 5 2 88