›
›

Toán tin - Lí thuyết đồ thị

pdf 77 trang vanle 3990
Download
Bạn đang xem 20 trang mẫu của tài liệu "Toán tin - Lí thuyết đồ thị", để 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:

  • pdftoan_tin_li_thuyet_do_thi.pdf

Nội dung text: Toán tin - Lí thuyết đồ thị

  1. 1. Khái niệm cơ bản 2. Đồ thị cĩ hướng & vơ hướng 3. Đồ thị đặc biệt 4. Chu trình & Đường đi 5. Các bài tốn liên quan
  2. Đị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. 3
  3. Nếu uv là một cung (cạnh) 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. 5
  4. b c a d e b a h k g c d b a c d 6
  5. Đị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ị 7
  6. Đ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 8
  7. b b a a d c d c 9
  8. Đị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 10
  9. Cho hai đồ thị G1=(V1,E1) và G2=(V2,E2). Ta nĩi G2 là đồ thị con của G1 nếu V2  V1 và E2  E1. Trong trường hợp V1=V2 thì G2 gọi là con bao trùm của G1.
  10. G1, G2, G3 và G4 là các đồ thị con của G, trong đĩ G2 và G4 là đồ thị con bao trùm của G, cịn G5 khơng phải là đồ thị con của G.
  11. Đơn đồ thị G’=(V,E’) được gọi là đồ thị bù của đơn đồ thị G=(V,E) nếu G và G’ khơng cĩ cạnh chung nào (E  E’=) và G  G’là đồ thị đầy đủ.
  12. 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. 15
  13. a Bậc đỉnh a: deg(a) = 2 b c d Bậc đỉnh b: deg(b) = 5 Bậc đỉnh c: deg(c) = 3 Bậc đỉnh d: deg(d) = 2 16
  14. 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 17
  15. a b d c e f Bậc của các đỉnh? 18
  16. Bậc đỉnh a: deg-(a)= 1 ; deg+(a)=1 a b Bậc đỉnh b: deg-(b)= 1 ; deg+(b)=3 d c e f Bậc đỉnh c: deg-(c)= 1 ; deg+(c)=2 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 19
  17. Đị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ì: m deg ( v ) deg ( v ) v V v V 3) Số đỉnh bậc lẻ của đồ thị là số chẵn 20
  18. Biểu diễn ma trận của đồ thị. 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 21
  19. Tìm ma trận kề a a b c d b a 0 1 1 0 c b 1 0 1 1 c d 1 1 0 1 d 0 1 1 0 22
  20. Tìm ma trận kề a b c d e f a b a 0 2 1 0 0 0 b 2 0 1 0 1 1 c d e c 1 1 0 0 0 1 f d 000000 e 0 1 0 0 1 0 f 0 1 1 0 0 0 23
  21. Với mỗi đỉnh của đồ thị ta xây dựng một danh sách mĩc nối chứa các đỉnh kề với đỉnh này: Danh sách này được gọi là danh sách kề. Một đồ thị được biểu diễn bằng một mảng các danh sách kề
  22. b c a e d
  23. Đẳng cấu 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’ 26
  24. Đẳng cấu  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) 27
  25. Đẳng cấu 28
  26. 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 29
  27. b 2 a 1 3 d c 6 e 4 5 f Đẳng cấu 30
  28. a 2 b 1 4 5 d e 3 c Khơng đẳng cấu 31
  29. a b d c e 32
  30. Đồ thị đầy đủ Đồ thị phẳng Đồ thị thành phần, đồ thị con
  31. Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ thị mà hai đỉnh phân biệt bất kỳ của nĩ luơn liền kề. K cĩ n ( n 1 ) cạnh và mỗi đỉnh của K n 2 n cĩ bậc là n 1.
  32. Đơn đồ thị n đỉnh v1, v2, , vn (n 3) và n cạnh (v1,v2), (v2,v3), , (vn-1,vn), (vn,v1) được gọi là đồ thị vịng, ký hiệu là Cn. Như vậy, mỗi đỉnh của Cn cĩ bậc là 2.
  33. Từ đồ thị vịng Cn, thêm vào đỉnh vn+1 và các cạnh (vn+1,v1), (vn+1,v2), , (vn+1,vn), ta nhận được đơn đồ thị gọi là đồ thị bánh xe, ký hiệu là Wn. Như vậy, đồ thị Wn cĩ n+1 đỉnh, 2n cạnh, một đỉnh bậc n và n đỉnh bậc 3.
  34. Đơn đồ thị 2n đỉnh, tương ứng với 2n xâu nhị phân độ dài n và hai đỉnh kề nhau khi và chỉ khi 2 xâu nhị phân tương ứng với hai đỉnh này chỉ khác nhau đúng một bit được gọi là đồ thị lập phương, ký hiệu là Qn. n- Mỗi đỉnh của Qn cĩ bậc là n và số cạnh của Qn là n.2 1 (từ cơng thức 2|E| =  deg( v ) ). v V
  35. Đơn đồ thị G=(V,E) sao cho V=V1V2, V1V2=, V1 , V2  và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị phân đơi. Nếu đồ thị phân đơi G=(V1V2,E) sao cho với mọi v1 V1, v2 V2, (v1,v2) E thì G được gọi là đồ thị phân đơi đầy đủ. Nếu |V1|=m, |V2|=n thì đồ thị phân đơi đầy đủ G ký hiệu là Km,n. Như vậy Km,n cĩ m.n cạnh, các đỉnh của V1 cĩ bậc n và các đỉnh của V2 cĩ bậc m.
  36. Bài tốn : 3 nhà cĩ 3 cái giếng
  37. Một đồ thị được gọi là phẳng nếu nĩ cĩ thể vẽ được trên một mặt phẳng mà khơng cĩ các cạnh nào cắt nhau
  38. Định lý : Trong một đồ thị phẳng liên thơng tuỳ ý, luơn tồn tại ít nhất một đỉnh cĩ bậc khơng vượt quá 5.
  39. Định nghĩa. Cho 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) Một đồ thị (vơ hướng) được gọi là liên thơng nếu cĩ đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. 44
  40. Liên thơng Khơng liên thơng 45
  41. 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). 46
  42. Trong đồ thị trên, các đỉnh khớp là v, w, s và các cầu là (x,v), (w,s). Đỉnh khớp là v, w, s và các cầu là (x,v), (w,s).
  43. Mệnh đề 1 : Đơn đồ thị mà bậc của mỗi đỉnh của nĩ khơng nhỏ hơn một nửa số đỉnh là đồ thị liên thơng. Mệnh đề 2: Nếu một đồ thị cĩ đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên thơng, tức là cĩ một đường đi nối chúng. Mệnh đề 3 : Cho G=(V,E) là một đồ thị liên thơng. Khi đĩ một đỉnh của G là điểm khớp khi và chỉ khi trong G tồn tại hai đỉnh u và v sao cho mỗi đường đi nối u và v đều phải đi qua đỉnh này.
  44. (n k)(n k 1) n k m 2 Cho G là một đơn đồ thị cĩ n đỉnh, m cạnh và k thành phần liên thơng. Khi đĩ : (n k)(n k 1) n k m 2
  45. Đồ thị cĩ hướng G được gọi là liên thơng mạnh nếu với hai đỉnh phân biệt bất kỳ u và v của G đều cĩ đường đi từ u tới v và đường đi từ v tới u. Đồ thị cĩ hướng G được gọi là liên thơng yếu nếu đồ thị vơ hướng nền của nĩ là liên thơng. Đồ thị cĩ hướng G được gọi là liên thơng một chiều nếu với hai đỉnh phân biệt bất kỳ u và v của G đều cĩ đường đi từ u tới v hoặc đường đi từ v tới u.
  46. Đồ thị G là liên thơng mạnh nhưng đồ thị G’ là liên thơng yếu (khơng cĩ đường đi từ u tới x cũng như từ x tới u).
  47. 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 52
  48. 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 53
  49. • x, y, z, w, v, y là đường đi đơn (khơng sơ cấp) độ dài 5; • x, w, v, z, y khơng là đường đi vì (v, z) khơng là cạnh; • y, z, w, x, v, u, y là chu trình sơ cấp độ dài 6. 54
  50. Đườ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 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 55
  51. Đị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 57
  52. Đ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 chẵn thì ta cĩ thể vẽ đồ thị bằng k nét 58
  53. Chu trình Euler Khơng cĩ Euler Đường đi Euler Khơng cĩ Euler Chu trình Euler Đường đi Euler
  54. Ta cĩ thể vạch được một chu trình Euler trong đồ thị liên thơng G cĩ bậc của mọi đỉnh là chẵn theo thuật tốn Fleury. Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy 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. 60
  55. •Xuất phát từ u, ta cĩ thể đi theo cạnh (u,v) hoặc (u,x), giả sử là (u,v) (xố (u,v)). •Từ v cĩ thể đi qua một trong các cạnh (v,w), (v,x), (v,t), giả sử (v,w) (xố (v,w)). •Tiếp tục, cĩ thể đi theo một trong các cạnh (w,s), (w,y), (w,z), giả sử (w,s) (xố (w,s)).
  56. •Đi theo cạnh (s,y) (xố (s,y) và s). Vì (y,x) là cầu nên cĩ thể đi theo một trong hai cạnh (y,w), (y,z), giả sử (y,w) (xố (y,w)). • Đi theo (w,z) (xố (w,z) và w) và theo (z,y) (xố (z,y) và z). •Tiếp tục đi theo cạnh (y,x) (xố (y,x) và y). Vì (x,u) là cầu nên đi theo cạnh (x,v) hoặc (x,t), giả sử (x,v) (xố (x,v)). • Tiếp tục đi theo cạnh (v,t) (xố (v,t) và v), theo cạnh (t,x) (xố cạnh (t,x) và t), cuối cung đi theo cạnh (x,u) (xố (x,u), x và u).
  57. Nếu G là một đồ thị liên thơng cĩ q cạnh thì hành trình ngắn nhất trong G cĩ chiều dài : q + m(G) Với m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như sau: . Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V0(G). . Ta gọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u,v). Đối với mọi phân hoạch cặp Pi, ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng d(Pi). Số m(G) bằng cực tiểu của các d(Pi):
  58. Tập hợp các đỉnh bậc lẻ VO(G)={B, G, H, K} và tập hợp các phân hoạch cặp là P={P1, P2, P3}, trong đĩ : . P1 = {(B, G), (H, K)} d(P1) = d(B, G)+d(H, K) = 4+1 = 5, . P2 = {(B, H), (G, K)} d(P2) = d(B, H)+d(G, K) = 2+1 = 3, . P3 = {(B, K), (G, H)} d(P3) = d(B, K)+d(G, H) = 3+2 = 5. . m(G) = min(d(P1), d(P2), d(P3)) = 3. Do đĩ GT cĩ được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K) và GT là đồ thị Euler. Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong GT: A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A.
  59. Đường đi Hamilton là một đường đi trong đồ thị vơ hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Một Chu trình Hamilton là một đường đi Hamilton sau đi qua tất cả các đỉnh của đồ thị thì trở về đỉnh xuất phát.
  60. Đường đi Hamilton Khơng Hamilton Chu trình Hamilton
  61. Định lý Dirac : Nếu G là một đơn đồ thị cĩ n đỉnh và mọi đỉnh của G đều cĩ bậc khơng nhỏ hơn n/2 thì G là một đồ thị Hamilton. Hệ quả : Nếu G là đơn đồ thị cĩ n đỉnh và mọi đỉnh của G đều cĩ bậc khơng nhỏ hơn (n-1)/2 thì G là đồ thị nửa Hamilton. Định lý Ore : Nếu G là một đơn đồ thị cĩ n đỉnh và bất kỳ hai đỉnh nào khơng kề nhau cũng cĩ tổng số bậc khơng nhỏ hơn n thì G là một đồ thị Hamilton.
  62. Định lý: Nếu G là đồ thị 2 phe(phân đơi) với hai tập đỉnh là V1, V2 cĩ số đỉnh cùng bằng n (n 2) và bậc của mỗi đỉnh lớn hơn n/2 thì G là một đồ thị Hamilton Đồ thị đầy đủ Kn với n lẻ và n 3 cĩ đúng (n-1)/2 chu trình Hamilton phân biệt.
  63. Đồ thị G này cĩ 8 đỉnh, đỉnh nào cũng cĩ bậc 4, nên G là đồ thị Hamilton
  64. Đồ thị G này cĩ 5 đỉnh bậc 4 và 2 đỉnh bậc 2 kề nhau nên tổng số bậc của hai đỉnh khơng kề nhau bất kỳ bằng 7 hoặc 8, nên G là đồ thị Hamilton
  65. Đồ thị phân đơi này cĩ bậc của mỗi đỉnh bằng 2 hoặc 3 (> 3/2), nên nĩ là đồ thị Hamilton.
  66. Đồ thị Hamilton với chu trình Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A
  67. Cây là một đồ thị vơ hướng liên thơng, khơng chứa chu trình và cĩ ít nhất hai đỉnh. Một đồ thị vơ hướng khơng chứa chu trình và cĩ ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thơng là một cây.
  68. Trong đồ thị liên thơng G, nếu ta loại bỏ cạnh nằm trên chu trình nào đĩ thì ta sẽ được đồ thị vẫn là liên thơng. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị khơng cịn chu trình (vẫn liên thơng) thì ta thu được một cây nối các đỉnh của G. Cây đĩ gọi là cây khung hay cây bao trùm của đồ thị G.
  69. Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự khơng giảm của trọng số. : 1. Bắt đầu từ đồ thị rỗng T cĩ n đỉnh.Sắp xếp các cạnh của G theo thứ tự tăng dần về trọng số. 2. Bắt đầu từ cạnh đầu tiên của dãy này, ta cứ thêm dần các cạnh của dãy đã được xếp vào T theo nguyên tắc cạnh thêm vào khơng được tạo thành chu trình trong T. 3. Lặp lại Bước 3 cho đến khi nào số cạnh trong T bằng n 1, ta thu được cây khung nhỏ nhất cần tìm.
  70. Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần : {(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}.