›

Bài giảng môn Toán rời rạc - Chương 4: Các khái niệm về đồ thị

pdf 50 trang Đức Chiến 03/01/2024 1070
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Toán rời rạc - Chương 4: Các khái niệm 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_mon_toan_roi_rac_chuong_4_cac_khai_niem_ve_do_thi.pdf

Nội dung text: Bài giảng môn Toán rời rạc - Chương 4: Các khái niệm về đồ thị

  1. TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM MÔN TOÁN RỜI RẠC GV: Võ Tấn Dũng
  2. ĐƠN ĐỒ THỊ VÔ HƯỚNG  Đơn đồ thị vô hướng G = (V,E) là một bộ gồm hai tập hợp V và E.  V là tập các đỉnh (vertices).  E là tập các cạnh (edges), mỗi cạnh là một cặp không có thứ tự gồm 2 đỉnh khác nhau của tập V.
  3.  Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó V1={a, b, c, d, e, f, g, h}, E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}. a f b h e c g d Đồ thị G1 3
  4. ĐA ĐỒ THỊ VÔ HƯỚNG  Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.  Hai cạnh e1 và e2 được gọi là cạnh song song nếu chúng cùng tương ứng với một cặp đỉnh.
  5.  Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó V2={a, b, c, d, e, f, g, h}, E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e), (a,e), (a,e), (a, e), (d,b), (f,g)}. a b f e h Cạnh song song c g d Đồ thị G2
  6. Cạnh song song, cạnh vòng  Cạnh song song (cạnh bội)  Hai hay nhiều cạnh phân biệt cùng tương ứng với một cặp đỉnh  Cạnh vòng (cạnh loop): B  Một cạnh tương ứng với x hai đỉnh trùng nhau. A C  Đơn đồ thị y z  Đồ thị không có vòng và D cạnh song song  Đa đồ thị  Các đồ thị không phải là đơn đồ thị
  7. ĐỒ THỊ CÓ HƯỚNG  Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm hai đỉnh khác nhau của V gọi là các cạnh (cung).  G = (V, E)  Tập đỉnh V  Tập cạnh (cung) E = { (a, b) | a,b V }  e = (a, b) E  Ký hiệu: e = ab  e có hướng từ a đến b  a: đỉnh đầu; b: đỉnh cuối  e là cạnh vòng ab
  8. CÁC THUẬT NGỮ CƠ BẢN  Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G.  Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là cạnh liên thuộc với hai đỉnh u và v (hoặc cũng nói là nối đỉnh u và đỉnh v)  Đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u, v).
  9. BẬC CỦA ĐỈNH  Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3, deg(d) = 1, deg(e) = 3, deg(g) = 0  Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo.
  10.  Bậc của đỉnh  Đỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác.  Ký hiệu: deg(v) hay d(v) g f e  Mỗi vòng được kể là 2 cạnh tới một đỉnh  Đỉnh cô lập  deg(v)=0  Đỉnh treo  deg(v)=1 a b c d  Cạnh treo có đầu mút là một đỉnh treo  Đồ thị rỗng: deg(v)=0 v
  11. Tính chất bậc của đỉnh  Định lý 1. Giả sử G = (V, E) là đồ thị vô hướng với |E| cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng hai lần số cạnh.  Hệ quả. Trong đồ thị vô hướng thì:  Tổng bậc là một số chẵn.  Số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
  12. Ví dụ. Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 25 cạnh đều có bậc là 3 hoặc 5. Hỏi G có bao nhiêu đỉnh bậc 3? Giải. Giả sử G có x đỉnh bậc 3. Khi đó có 14-x đỉnh bậc 5. Do | E | = 25, nên tổng tất cả các bậc là 50. Từ đó, 3x + 5(14-x) = 50 Suy ra x = 10. 32
  13. Cạnh vào, cạnh ra  Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau.  Và nói cung (u, v) nối đỉnh u với đỉnh v  Hoặc cũng có thể nói là cung này là đi ra khỏi đỉnh u và vào đỉnh v.  Đỉnh u(hoặc v) sẽ được gọi là đỉnh đầu (cuối) của cung (u,v).
  14. Bậc vào, bậc ra  Ta gọi bậc ra của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó và ký hiệu là deg+(v)  Ta gọi bậc vào của đỉnh v trong đồ thị có hướng là số cung của đồ thị vào nó và ký hiệu là deg-(v) deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2. deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2.
  15. Định lý:  Giả sử G = (V, E) là đồ thị có hướng. Khi đó:
  16. Ví dụ b kề tới c và c kề từ b b c a f deg-(a) = 0 deg+(a)= 2 d e deg-(f) = 0 a- đỉnh nguồn deg+(f)= 0 deg-(d) = 2 deg-(e) = 2 deg+(d)= 1 deg+(e)= 0 e – đỉnh đích (target)
  17. ĐỒ THỊ ĐẲNG CẤU Ví dụ: hai đồ thị sau đẳng cấu 1  DN, 2  CT, 3  BD, 4  AG 17
  18. ĐỒ THỊ ĐẲNG CẤU Điều kiện cần nhưng không phải là đủ để G1=(V1, E1) là đẳng cấu với G2=(V2, E2):  Ta phải có |V1|=|V2|, và |E1|=|E2|.  Số lượng đỉnh bậc k ở hai đồ thị là như nhau. 18
  19. ĐỒ THỊ ĐẲNG CẤU •Tính chất trên chỉ có điều kiện cần •Ví dụ: hai đồ thị sau ? không đẳng cấu 19
  20. BÀI TẬP Xét sự đẳng cấu của các cặp đồ thị sau. Chỉ ra song ánh nếu chúng đẳng cấu 20
  21. Sự đẳng cấu giữa các đồ thị  Chứng minh 2 đồ thị đẳng cấu 21
  22. BÀI TẬP  Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt. b d a b a d c e e c f f
  23. Có đẳng cấu không?  Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt. • Cùng số a lượng đỉnh b • Cùng số lượng cạnh d • Khác số lượng c e đỉnh bậc 2 (1 3)
  24. CHU TRÌNH (vô hướng)  Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1, , xn-1, xn trong đó  Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:  (x0, x1), (x1, x2), , (xn-1, xn)  Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi.  Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình.  Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.
  25. CHU TRÌNH (có hướng)  Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị có hướng G = (V, E) là dãy x0, x1, , xn-1, xn trong đó  Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:  (x0, x1), (x1, x2), , (xn-1, xn)  Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi.  Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình.  Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.
  26.  Ví dụ: đường đi  Ví dụ: chu trình 26
  27. Đường đi (Path) 5 c d a b 1 2 3 e 4 Ví dụ: 5, 2, 3, 4 hoặc 5, c, 2, b, 3, e, 4. Không có đỉnh lặp nên là đường đi đơn 5 c d a b 1 2 3 e 4 Ví dụ: 1, 2, 5, 3, 4 hoặc 1, a, 2, c, 5, d, 3, e, 4 • Là đường đi đơn
  28. Ví dụ (tiếp)  P1=(1,b,2,h,3) là đường 1 đi đơn a b P1 d  P =(4,c,5,e,2,g,6,f,5,d,1) 4 2 3 2 P2 h là đường đi nhưng c e không là đường đi đơn 5 g f 6 28
  29. Ví dụ (tiếp)  P1=(1, b, 2, h, 3) là 1 đường đi đơn a b P1 d  P =(4,c,5,e,2,g,6,f,5,d,1) 4 2 3 2 P2 h là đường đi nhưng c e không là đường đi đơn 5 g f 6
  30. Chu trình (Cycle) 2 a b e Chu trình 1 3 1, 2, 3, 1. (hay 1, a, 2, b, 3, e) d c • Chu trình đơn 4 2 a b Chu trình: (1, 2, 3, 4, 1) hay e 1 3 1, a, 2, b, 3, c, 4, d, 1 d c • Chu trình đơn 4
  31. Ví dụ: Chu trình trên đồ thị vô hướng  C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn  C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không là chu trình đơn V a b d U C2 X Z h e c C1 W g f Y
  32. Ví dụ: Chu trình trên đồ thị vô hướng  C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn  C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không là chu trình đơn V a b U d X Z C2 h e c C1 W g f Y
  33. LIÊN THÔNG Đồ thị G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.  Ví dụ. Đồ thị gồm các đỉnh a,b,c,d,e,f,g là liên thông. Còn đồ thị H tạo ra từ H1,H2,H3 là không liên thông.
  34. Tính liên thông  Tính liên thông trong đồ thị vô hướng  Đỉnh cắt và cầu  u là một đỉnh cắt số thành phần liên thông tăng lên nếu bỏ u và các cạnh liên thuộc với nó  e là một cầu số thành phần liên thông tăng lên nếu bỏ cạnh e 34
  35. ĐỒ THỊ CON CÁC THÀNH PHẦN LIÊN THÔNG  Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó  Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị.  Ví dụ. Đồ thị H trong hình dưới gồm 3 thành phần liên thông H1, H2, H3.
  36. MỘT SỐ DẠNG ĐẶC BIỆT CỦA ĐỒ THỊ  Đồ thị đầy đủ.  Đồ thị hai phía  Đồ thị hai phía đầy đủ
  37. ĐỒ THỊ ĐẦY ĐỦ  Đồ thị đầy đủ Kn  Đơn đồ thị  Số đỉnh: |V| = n  Bậc: deg(v) = n – 1 v V  Số cạnh: |E| = n(n - 1) / 2 K1 K2 K3 K4 K5 K6 Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất. 37
  38. ĐỒ THỊ LƯỠNG PHÂN (HAI PHÍA)  Một đồ thị G được gọi là đồ thị lưỡng phân nếu tập các đỉnh của G có thể phân thành 2 tập hợp không rỗng, rời nhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập này đến một đỉnh thuộc tập kia.  Ký hiệu: Km,n 38
  39. ĐỒ THỊ LƯỠNG PHÂN ĐẦY ĐỦ  Đồ thị hai phía được gọi là đồ thị hai phía đầy đủ nếu mỗi đỉnh của phía này đều có một cạnh nối đến từng đỉnh của phía kia. Và ký hiệu là Km,n.  Ví dụ: K2,3, K3,3, K3,4 được cho trong hình dưới.
  40. ĐỒ THỊ PHẲNG  Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngọai trừ ở đỉnh.  Ví dụ đồ thị K4 là phẳng.
  41. CÔNG THỨC EUCLER  Euler đã chứng minh được rằng: các cách biểu diễn phẳng khác nhau của một đồ thị phẳng, đều chia mặt phẳng ra thành cùng một số miền. Euler đã tìm được mối liên hệ giữa số miền, số đỉnh và số cạnh của đồ thị phẳng như sau.  Giả sử G=(V,E) là đồ thị phẳng liên thông với |V| đỉnh, |E| cạnh. Gọi |R| là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó
  42.  Ví dụ: Cho G là đồ thị phẳng liên thông với 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi mặt phẳng bị chia làm bao nhiêu phần bởi biểu diễn phẳng của đồ thị G?  Giải. Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng bậc của các đỉnh là 3x20=60. Từ đó suy ra số cạnh của đồ thị |E|=60/2=30. Vì vậy, theo công thức Euler, số miền cần tìm là |R|=30-20+2=12.
  43. MA TRẬN KỀ  Xét đơn đồ thị vô hướng G=(V,E), với tập đỉnh V={ 1, 2,. . . ,n} , tập cạnh E={ e1, e2,. . .,em} . Ta gọi ma trận kề của đồ thị G là ma trận vuông.  A={ ai,j : i,j=1, 2,. . . ,n}  Với các phần tử được xác định theo qui tắc sau đây:
  44. Ví dụ ma trận kề
  45. Ví dụ ma trận kề Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng.
  46. TÍNH CHẤT MA TRẬN KỀ  Các tính chất của ma trận kề:  1) Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là  a[i,j]=a[j,i], i,j=1,2,. . .,n.  2) Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j).  Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự.
  47. MA TRẬN TRỌNG SỐ  Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị được gán với một con số a(e) [còn viết là a(u,v)] gọi là trọng số của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, thay vì mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số.
  48. MA TRẬN TRỌNG SỐ
  49. Hết chương