›
›

Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 4: Đại cương về đồ thị

pdf 67 trang ngocly 3160
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 4: Đại cương về đồ 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:

  • pdfbai_giang_toan_hoc_to_hop_va_cau_truc_roi_rac_chuong_4_dai_c.pdf

Nội dung text: Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 4: Đại cương về đồ thị

  1. Chương 4. ĐẠI CƯƠNG VỀ ĐỒ THỊ
  2. Nội dung 1. Giới thiệu 2. Các khái niệm cơ bản 3. Biểu diễn đồ thị 4. Đẳng cấu đồ thị 5. Đường đi, chu trình 2
  3. 1. Giới thiệu Bài tốn. Thành phố Kưnigsberg, Đức nằm trên một con sơng, cĩ hai hịn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Bài tốn đặt ra là cĩ thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay khơng? 3
  4. Năm 1736, nhà tốn học Leonhard Euler đã chứng minh rằng điều đĩ là khơng thể được. 4
  5. Bài tốn 1. Cĩ thể vẽ hình phong bì thư bởi một nét bút hay khơng? Nếu cĩ hãy chỉ ra tuần tự các nét vẽ 1 2 3 4 5 5
  6. Bài tốn 2. Một đồn kiểm tra chất lượng các con đường. Để tiết kiệm thời gian, đồn kiểm tra muốn đi qua mỗi con đường đúng 1 lần. Kiểm tra xem cĩ cách đi như vậy khơng? 4 7 5 1 8 6 2 3 6
  7. Bài tốn 3. Một sinh viên muốn đi từ nhà đến trường thì phải đi như thế nào? Cách đi nào là ngắn nhất? 7
  8. 2. Các khái niệm cơ bản Định nghĩa. Một đồ thị vơ hướng (undirected graph) G=(V, E) được định nghĩa bởi: • Tập hợp V  được gọi là tập các đỉnh (vertex) và n = |V| gọi là cấp của đồ thị; • Tập hợp E là tập các cạnh (edge) của đồ thị; Mỗi cạnh e E được liên kết với một cặp đỉnh {i, j}, khơng phân biệt thứ tự 8
  9. Đỉnh kề Định nghĩa. Trên đồ thị vơ hướng, xét cạnh e được liên kết với cặp đỉnh {i, j}: . Cạnh e kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh e); cĩ thể viết tắt e=ij . Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau (hay đỉnh i kề với đỉnh j và ngược lại, đỉnh j kề với đỉnh i) . Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song song. . Cạnh cĩ hai đỉnh trùng nhau gọi là một khuyên 9
  10. Đỉnh kề Tập các đỉnh kề với đỉnh v được viết là (){:(,)}v u V v u E Nhận xét. Đồ thị G hồn tồn được xác định nếu chúng ta biết (v),v V nên đồ thị G cũng cĩ thể định nghĩa như sau: GV (,) 10
  11. Đỉnh kề . Cạnh song song: e1, e7 . Khuyên: e9 . Đỉnh treo: 5 . Đỉnh cơ lập: 6 .  (2) {1, 3, 4} 11
  12. Một số loại đồ thị vơ hướng Định nghĩa. Cho G là đồ thị vơ hướng. Khi đĩ G được gọi là: a) đơn đồ thị (hay đồ thị đơn) nếu G khơng cĩ khuyên và khơng cĩ cạnh song song b) đa đồ thị nếu G khơng cĩ khuyên, cho phép cĩ cạnh song song c) giả đồ thị nếu G cho phép cĩ cạnh song song và cĩ khuyên 12
  13. b c a b a d e h c k g d b a d c 13
  14. Các dạng đồ thị . Đồ thị rỗng: tập cạnh là tập rỗng . Đồ thị đủ: đồ thị vơ hướng, đơn, giữa hai đỉnh bất kỳ đều cĩ đúng A B một cạnh. . Đồ thị đủ n đỉnh ký hiệu là Kn. 푛 n−1 C . K cĩ cạnh. n 2 . Đồ thị k-đều: là đồ thị mà mọi đỉnh đều cĩ bậc bằng nhau và bằng k. 14
  15. . Đồ thị lưỡng phân: đồ thị vơ hướng G=(V, E) được gọi là đồ thị lưỡng phân nếu tập V được chia A thành hai tập V1 và V2 thỏa: D . V1 và V2 phân hoạch V; B . Cạnh chỉ nối giữa V1 và V2. . Đồ thị lưỡng phân đủ: là đồ thị E lưỡng phân thỏa điều kiện mỗi đỉnh C trong V1 kề với mọi đỉnh trong V2. • V1=n và V2=m, ký hiệu Kn,m 15
  16. K4 K K3 4 K2  K1, 1 K3, 3 K2, 3 GV: Dương Anh Đức 16 16
  17. Đồ thị cĩ hướng Định nghĩa. Một đồ thị cĩ hướng G=(V, U) được định nghĩa bởi: • Tập hợp V  được gọi là tập các đỉnh. • Tập hợp U là tập các cạnh (cung) của đồ thị; Mỗi cạnh u U được liên kết với một cặp đỉnh (i, j) V2. Ký hiệu u=(i,j) hoặc u=ij. 17
  18. Đỉnh kề Trên đồ thị cĩ hướng, xét cạnh u được liên kết với cặp đỉnh (i, j): . i được gọi là đỉnh đầu, j được gọi là đỉnh cuối . Cạnh u kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh u); cĩ thể viết tắt u=(i, j). Cạnh u đi ra khỏi đỉnh i và đi vào đỉnh j. 18
  19. Đỉnh kề Định nghĩa. Cho đồ thị cĩ hướng G=(V, E) và e=(u, v) E • v là đỉnh sau của u • u là đỉnh trước của v • Tập hợp các đỉnh sau và đỉnh trước của v lần lượt là (vv ), ( ) Nhận xét. Đồ thị G hồn tồn được xác định nếu chúng ta biết (v),v V nên đồ thị G cũng cĩ thể được định nghĩa như sau: G (V,) 19
  20. Đỉnh kề h 2 g 4 Ví dụ. a l f 6 1 c e k j b i d 3 5 v (v)  (v) 1 2 3 5 6 20
  21. . Cạnh song song - u1, u7 cùng chiều - u5, u8 ngược chiều . Khuyên: u2 . Đỉnh treo: 6 . Đỉnh cơ lập: 5 21
  22. Đồ thị hữu hạn . Đồ thị cĩ tập đỉnh và tập cạnh hữu hạn được gọi là đồ thị hữu hạn . Trong học phần này ta chỉ làm việc với các đồ thị hữu hạn. Để ngắn gọn chúng ta chỉ dùng thuật ngữ ĐỒ THỊ và hiểu ngầm đĩ là đồ thị hữu hạn. 22
  23. Đồ thị con Định nghĩa. Cho hai đồ thị G = (V,E) và G’ = (V’,E’) (cùng vơ hướng hoặc cùng cĩ hướng). . G’ được gọi là đồ thị con của G, ký hiệu G’ G, nếu V’ V và E’  E . Nếu V’= V và E’  E thì G’ được gọi là đồ thị con khung của G. G H 23
  24. Bậc của đỉnh Định nghĩa. Xét đồ thị vơ hướng G. Bậc của đỉnh x trong đồ thị G là số các cạnh kề với đỉnh x, mỗi khuyên được tính hai lần, ký hiệu là degG(x) (hay deg(x) nếu đang xét một đồ thị nào đĩ). 24
  25. Bậc của đỉnh Ví dụ. 1 7 5 3 6 2 4 8 i 1 2 3 4 5 6 7 8 deg(i) 25
  26. Bậc của đỉnh Ví dụ. H là đơn đồ thị vơ hướng cĩ n đỉnh (n 2). a) Mỗi đỉnh của H cĩ bậc tối đa là bao nhiêu ? H cĩ tối đa bao nhiêu cạnh ? b) Chứng minh rằng H cĩ ít nhất 2 đỉnh cùng bậc. Giải. a) Vì H là đơn đồ thị vơ hướng nên mỗi đỉnh của H khơng cĩ khuyên và chỉ cĩ thể nối với các đỉnh khác khơng quá một cạnh, nghĩa là mỗi đỉnh của H cĩ bậc tối đa là (n 1). Suy ra H cĩ tối đa là n(n 1) / 2 cạnh 26
  27. Bậc của đỉnh b) Giả sử bậc của các đỉnh của H đều khác nhau. Khi đĩ bậc của n đỉnh của H lần lượt là 0, 1, , (n - 1), nghĩa là H phải cĩ đỉnh cơ 0. Do H cĩ đỉnh bậc 0 nên các đỉnh khác của H cĩ bậc tối đa là (n 2) : mâu thuẫn. Vậy cĩ ít nhất 2 đỉnh của H cĩ cùng bậc. Ví dụ. Hãy vẽ một đồ thị đơn vơ hướng gồm 6 đỉnh với bậc các đỉnh lần lượt là: 2,2,3,3,3,3 27
  28. Bậc của đỉnh Định nghĩa. Xét đồ thị cĩ hướng G .Nửa bậc ngồi của đỉnh x là số các cạnh đi ra khỏi đỉnh x, ký hiệu deg+(x). .Nửa bậc trong của đỉnh x là số các cạnh đi vào đỉnh x, ký hiệu deg-(x). .Bậc của đỉnh x: deg(x)=deg+(x)+deg-(x) 28
  29. Bậc của đỉnh Chú ý. 1 khuyên được tính 1 lần bậc vào và 1 lần bậc ra b d Ví dụ. f a v deg (v) deg (v) deg(v) a c e b c d e f 29
  30. Bậc của đỉnh . Đỉnh TREO là đỉnh cĩ bậc bằng 1. A B . Đỉnh CƠ LẬP là đỉnh cĩ bậc bằng 0. D C 30
  31. Mối liên hệ giữa bậc và số cạnh Định lý. . Xét đồ thị cĩ hướng G=(X, U). Ta cĩ: degx  degx và  degx 2U x X x X x X . Xét đồ thị vơ hướng G=(X, E). Ta cĩ: deg x 2 E  xX Hệ quả. Số đỉnh cĩ bậc lẻ trong một đồ thị là một số chẵn. 31
  32. Ví dụ. Trong một bữa tiệc, mọi người bắt tay nhau. Chứng minh rằng số người bắt tay mới một số lẻ người khác là số chẵn. Giải. Lập đồ thị hướng G như sau: . Mỗi đỉnh là đại diện cho một người . Hai đỉnh nối với nhau bằng một cạnh nếu hai người đĩ bắt tay nhau Một người bắt tay với một số lẻ người khác, cĩ nghĩa đỉnh tương ứng cĩ bậc là lẻ. Theo hệ quả trên ta cĩ điều chứng minh. 32
  33. Bậc của đỉnh Ví dụ. Cho G là đồ thị vơ hướng liên thơng cĩ 6 đỉnh với các bậc lần lượt là 1, 2, 2, 2, 3 và 4. Tính số cạnh của G. Hãy vẽ phác họa đồ thị G. (một trường hợp là đơn đồ thị và một trường hợp là đồ thị cĩ cả khuyên và các cạnh song song). Ví dụ. Cho H là đồ thị vơ hướng cĩ 34 cạnh, 3 đỉnh bậc 6, một số đỉnh bậc 5 và các đỉnh cịn lại cĩ bậc 8. Hãy xác định số đỉnh của H. Ví dụ. Vẽ đồ thị đơn vơ hướng gồm 6 đỉnh với bậc 2 ,2,3,3,3,5 33
  34. 3. Biểu diễn đồ thị A A e4 e1 u4 u1 e2 u2 e D u D B 3 B 3 e u e 6 u 6 5 5 C C H G 34
  35. Ma trận liên kết Định nghĩa. Cho G=(V,E) với V ={1, ,n} và E ={e1, em}. Ma trận liên kết của G là ma trận A=(aij) cấp nXm được định nghĩa như sau: a) Nếu G vơ hướng thì aij {0,1} xác định bởi 1 nếu i kềvới e j a ij 0 nếu i không kềvới e j b) Nếu G cĩ hướng thì aij {-1,0,1} xác định bởi 1 nếu ej rời khỏi i aij 1nếueđivàoi j 0 nếu e khôngkềvớii j 35
  36. Ma trận liên kết 1 e1 e 2 e 3 e 4 e 5 e 6 e e4 1 1 1 1 1 1 0 0 e2 e3 4 2 1 1 0 0 1 0 2 A e 3 0 0 1 0 1 1 e 6 5 3 4 0 0 0 1 0 1 G 36
  37. Ma trận liên kết 1 u1 u 2 u 3 u 4 u 5 u 6 u u4 1 1 1 1 1 1 0 0 u2 u3 4 2 1 1 0 0 1 0 2 A 3 0 0 1 0 1 1 u6 u5 3 4 0 0 0 1 0 1 G 37
  38. Ma trận liên kết Ví dụ. Cho G là đồ thị cĩ ma trận liên kết Hãy vẽ đồ thị G Đáp án. 38
  39. Ma trận kề Định nghĩa. Cho G=(V,E) với V ={1, ,n}. Ma trận kề (adjacency matrix) của G là ma trận vuơng A=(aij) cấp n xác định bởi aij= số cạnh từ đỉnh i đến j a a b c d a 0 1 0 0 b b 1 0 0 2 c c 1111 d d 0000 39
  40. Ma trận kề a b c d e f a 0 2 1 0 0 0 a b b 2 0 1 0 1 1 c 1 1 0 0 0 1 d e c d 000000 e 0 1 0 02 0 f 0 1 1 0 0 0 Lưu ý. Với đồ thị vơ hướng, nếu đỉnh i cĩ 1 khuyên thì aii được tính thêm 2 40
  41. Tính chất 1. Ma trận kề của đồ thị vơ hướng là đối xứng aij = aji. Ngược lại, ma trận (0,1) bậc n sẽ tương ứng với đơn đồ thị vơ hướng n đỉnh 2. Nếu đồ thị vơ hướng: Tổng dịng thứ i = Tổng cột thứ i = bậc của đỉnh 3. Nếu đồ thị cĩ hướng: Tổng dịng i = nửa bậc ngồi của i Tổng cột i =nửa bậc trong của i 41
  42. Ma trận kề Ví dụ. Lập ma trận kề của đồ thị sau: 42
  43. Ma trận kề Ví dụ. Cho đồ thị vơ hướng G với ma trận kề sau: Hãy vẽ đồ thị G Đáp án 43
  44. 4. Đẳng cấu đồ thị Xét hai đồ thị sau: chúng giống nhau hay khác nhau? 1 2 3 3 1 4 2 4 2 3 (2’) 2 3 (3’) 1 4 (4’) 1 4 (1’) 44
  45. 4. Đẳng cấu đồ thị Định nghĩa. Cho hai đồ thị đơn 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: ij là cạnh của G f(i)f(j) là cạnh của G’ 45
  46. Chú ý. Nếu G và G’ là các đồ thị đơn 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  deg i = deg f(i)  . 46
  47. Ví dụ. 47
  48. b b c a a c d e d e deg(e) = 1 Khơng đẳng cấu 48
  49. b 2 a 1 3 d c 6 e 4 5 f a 2 b 1 4 5 d e c 3 49
  50. Ví dụ. Hãy tìm các đồ thị đẳng cấu trong các đồ thị sau: (G1) (G2) (G3) (G4) (G5) (G6) (G7) GG16 GG35 GG47 50
  51. Ví dụ. Các đồ thị sau cĩ đẳng cấu khơng? Tại sao? g – B – 2 f – D – 4 i – A – 1 j – E – 5 h – C - 3 51
  52. Ví dụ. Hai đồ thị sau cĩ đẳng cấu khơng? Tại sao? 52
  53. 5. Đường đi, chu trình Định nghĩa. 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: v0=u, vk = v và e i=vi-1vi , i=1,2, ,k Đường đi đơn nếu khơng cĩ cạnh nào xuất hiện quá một lần và gọi là sơ cấp nếu khơng cĩ đỉnh nào xuất hiện quá một lần b) Nếu x trùng với y thì đường đi sẽ được chu trình Khái niệm chu trình đơn, sơ cấp tương tự như đường đi 53
  54. 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. Vì đồ thị đơn, nên ta cĩ thể viết ngắn gọn là: (a,b,c,d,b)  Chu trình sơ cấp: (b,c,d,b) (b,f,e,b) 54
  55. Liên thơng Đị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) Nếu G chỉ cĩ một thành phần liên thơng thì G gọi là liên thơng 55
  56. Liên thơng Ví dụ. Đồ thị nào sau đây liên thơng? a b a b e e d d c c G G1 2 b a a b e e d c d f c G3 G4 56
  57. Liên thơng Ví dụ. Cho đồ thị đơn vơ hướng G cĩ 7 đỉnh trong đĩ cĩ một đỉnh bậc 6. Hỏi G cĩ liên thơng khơng? Giải. Đỉnh bậc 6 nối với 6 đỉnh cịn lại. Do đĩ hai đỉnh bất kỳ đều cĩ một đường đi qua đỉnh bậc 6. Suy ra G liên thơng Ví dụ. Cho đồ thị vơ hướng G liên thơng mà mỗi đỉnh đều cĩ bậc bằng 10. Chứng minh rằng nếu xố đi một cạnh bất kỳ thì đồ thị thu được vẫn cịn liên thơng 57
  58. Liên thơng Giải. Giả sử ta xĩa cạnh uv. Ta chỉ cần chứngminh vẫn cĩ đường đi từ u đến v. Phản chứng. Giả sử khơng cĩ đường đi từ u đến v. Khi đĩ thành phần liên thơng G’ chứa u mà khơng chứa v. Trong G’, u cĩ bậc 9, mọi đỉnh khác đều cĩ bậc 10. Tổng các bậc trong G’ là số lẻ .Vơ lý. 58
  59. Liên thơng Ví dụ. Xét đồ thị đơn vơ hướng G với 6 đỉnh, trong đĩ cĩ một đỉnh bậc 1 và 5 đỉnh bậc 3. Chứng minh rằng G liên thơng. Giải. Giả sử G khơng liên thơng. Gọi G1, G2, ,Gk là các thành phần liên thơng của G (k 2). Vì G khơng cĩ đỉnh cơ lập nên mỗi thành phần liên thơng đều phải cĩ ít nhất hai đỉnh. Như vậy mỗi thành phần liên thơng đều phải cĩ ít nhất một đỉnh bậc 3. Suy ra mỗi thành phần liên thơng phải cĩ ít nhất 4 đỉnh. Vậy G phải cĩ ít nhất 4k 8 đỉnh . Trái giả thiết 59
  60. 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). 60
  61. Ví dụ. Tìm đỉnh khớp và cầu của đồ thị sau Đáp án: Đỉnh khớp: w,s Cầu : ws, xv 61
  62. Định nghĩa. Cho G = (V,E) vơ hướng liên thơng, khơng phải Kn, n>2. a) Số liên thơng cạnh của G, ký hiệu e(G) là số cạnh ít nhất mà khi xố đi G khơng cịn liên thơng nữa. b) Số liên thơng đỉnh của G, ký hiệu v(G) là số đỉnh ít nhất mà khi xố đi G khơng cịn liên thơng nữa. 62
  63. Ví dụ. Tìm số liên thơng cạnh và liên thơng đỉnh của các đồ thị sau 63
  64. Liên thơng mạnh Định nghĩa. Cho G =(V,E) là đồ thị cĩ hướng u,v V a) Đường đi cĩ chiều dài k nối hai đỉnh u,v là dãy đỉnh và cung liên tiếp nhau v0e1v1e2 .vk-1ekvk sao cho: v0 = u, vk = v ei = vi-1vi , i = 1,2,, ,k. b) Đường đi khơng cĩ cạnh nào xuất hiện quá một lần gọi là đường đi đơn. 64
  65. c) Đườ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. d) Đường đi được gọi là mạch (chu trình) nếu nĩ bắt đầu và kết thúc tại cùng một đỉnh. Ví dụ. Đường đi cĩ độ dài 4 từ đỉnh 1 tới đỉnh 2 là : (1,2,3,4,2) 65
  66. Liên thơng mạnh Định nghĩa. Cho đồ thị cĩ 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 và đường đi từ v đến u . a) Nếu u~v thì ta nĩi hai đỉnh u và v liên thơng mạnh 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 mạnh của G . c) Nếu G chỉ cĩ một thành phần liên thơng mạnh thì G gọi là liên thơng mạnh. 66