›
›

Bài giảng Toán rời rạc - Bài 6: Lý thuyết đồ thị

pdf 46 trang Đức Chiến 03/01/2024 1340
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 - Bài 6: 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:

  • pdfbai_giang_ly_thuyet_do_thi.pdf

Nội dung text: Bài giảng Toán rời rạc - Bài 6: Lý thuyết đồ thị

  1. BÀI 6 LÝ THUYẾT ĐỒ THỊ Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
  2. Tổng quan về đồ thi Nội dung Nội dung 6.1. Giới thiệu 6.6. Đồ thị phân đôi 6.2. Định nghĩa 6.7. Đồ thị đẳng cấu 6.3. Thuật ngữ cơ sở 6.8. Tính liên thông 6.4. Định lý cơ sở về bậc 6.9. Đồ thi Euler 6.5. Đồ thị đơn đặc biệt 6.10. Đồ thị Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
  3. 6.1. Giới thiệu Lý thuyết đồ thị Ứng dụng  Xây dựng mật điện trên một  Nghành học lâu đời, nhưng bảng điện dùng nhiều trong ứng dụng hiện đại  Xác định hai máy tính có kết nối hay không  Xác định đường đi ngắn nhất  Leohard Euler giữa hai thành phố  Lập lịch thi  Phân chia kênh truyền cho đài truyền hình  Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
  4. 6.2. Định nghĩa Đơn đồ thị Ứng dụng G = (V, E)  Mạng gồm các máy tính và các kênh điện thoại.  V - tập đỉnh,  Giữa hai máy tính bất kì có nhiêu nhất 1 kênh điện thoại.  E - tập các cặp không có thứ  Kênh thoại cho phép liên lạc hai chiều tự, gọi là cạnh nối các đỉnh  Không có máy tính nào được nối với phân biệt. chính nó.  ∃! (u,v) ∈ ⟹ ∃! (푣, ) ∈  (u, u )∉ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
  5. 6.2. Định nghĩa Đơn đồ thị Ứng dụng G = (V, E)  Mạng điện thoại cố định  V - tập đỉnh,  Mạng giao thông  E - tập các cặp không có thứ tự, gọi là cạnh nối các đỉnh phân biệt.  Mạng xe buýt  ∃! (u,v) ∈ ⟹ ∃! (푣, ) ∈  (u, u )∉ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
  6. 6.2. Định nghĩa Đa đồ thị Ứng dụng G = (V, E)  Mạng gồm các máy tính và các kênh điện thoại.  V - tập đỉnh,  Cho phép hai máy tính nối nhiều kênh thoại (do truyền tài nhiều)  E : cho phép nhiều hơn hai cạnh nối 2 đỉnh phân biệt.  (u,v) ∈  (u, u )∉ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
  7. 6.2. Định nghĩa Giả đồ thị Ứng dụng  Mạng gồm các máy tính và các kênh G = (V, E) điện thoại.  Cho phép máy tính nối u kênh thoại  V - tập đỉnh, với chính nó  E : cho phép vòng (đỉnh đầu và cuối trùng nhau)  (u,u) ∈ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
  8. 6.2. Định nghĩa Chú ý Chú ý ĐỒ THI ĐƠN ĐỒ THỊ ≡ ⊂ ĐỒ THỊ VÔ HƯỚNG ĐA ĐỒ THỊ ⊂ GIẢ ĐỒ THỊ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
  9. 6.2. Định nghĩa Đơn đồ thị có hướng Ứng dụng G = (V, E)  V - tập đỉnh,  E - tập các cặp có thứ tự, gọi là cung nối các đỉnh phân biệt.  (u,v) ∈ ⇏ (푣, ) ∈  (u, u )∉ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
  10. 6.2. Định nghĩa Đa đồ thị có hướng Ứng dụng G = (V, E)  V - tập đỉnh,  E : cho phép nhiều hơn hai cung nối các đỉnh phân biệt.  (u,v) ∈ ⇏ (푣, ) ∈  (u, u )∉  Hai cung tương ứng với một cặp đỉnh được gọi là cung lặp Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
  11. 6.2. Định nghĩa Đồ thị tình yêu Ứng dụng    Hai người có ít nhất cùng 1 sở thích thì có thể ghép đôi  G = (V, E) ? Tìm cách ghép đôi sao cho số người  V = {A, B , C , D , E} cô đơn là ít nhất  E: (u,v) ∈ E nếu u và v có cùng một sở thích Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
  12. 6.2. Định nghĩa Hội thảo video Ứng dụng  Có n điểm tham gia hội thảo, mỗi  điểm phát tính hiệu cho các điểm còn lại  Tổng các điểm phát ra từ v phải nhỏ hơn băng thông của v.  Thời gian trể từ điểm v đến điểm u phải nhỏ hơn một thông số cho trước.  Đảm bảo băng thông được sử  dụng tốt nhất Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
  13. 6.2. Định nghĩa Hội thảo video Ứng dụng  G = (V, E)  V: tập các điểm tham gia hội thảo  E: tập tất cả các kết nối có thể có (đồ thị đầy đủ)  Tìm một cây phủ: cây thể hiện việc phát tính hiệu từ một điểm Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
  14. 6.3. Thuật ngữ cơ sở Đồ thị vô hướng G = (V, E) , e = (u,v) ∈ E  u và v – đỉnh liền kề 1 2  e - cạnh liên thuộc với u và v 0  u và v – đỉnh đầu của e  Bậc của u là số cạnh liên thuộc 3 6 với u.  Đỉnh có bậc 0 - đỉnh cô lập  Đỉnh có bậc 1 - đỉnh treo. 7 5 4  Khuyên được tính bậc 2 deg(0) = 3, deg(5) = 1, deg(2) = 0, deg(6) = 5, . Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
  15. 6.3. Thuật ngữ cơ sở Đồ thị có hướng G = (V, E) , e = (u,v) ∈ E  u – nối tới v u  v – nối từ u t v  u – đỉnh đầu cung e  v – đỉnh cuối cung e  deg + (u) – bậc ra của u s x -  deg (u) – bậc vào của u deg+(s) = 2, deg-(s) = 1, deg+(x) = 1, deg-(v) = 0, Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
  16. 6.4 Định lý cơ sở về bậc Đồ thị vô hướng G = (V, E) 1 2  2 |E| = ∑ deg (v) v€ V 0 Tổng số bậc lẽ của đồ 3 6 thị là một số chẳn. 7 5 4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
  17. 6.4 Định lý cơ sở về bậc Đồ thị có hướng G = (V, E) u +  ∑ v€ V deg (v) = ∑ u € V - deg (u) = | E | t v  Bỏ qua hướng của G ta có đồ thị vô hướng nền của G s x có số cạnh bằng số cung của G Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
  18. 6.5 Đồ thị đơn đặc biệt Đồ thị đầy đủ - K Minh họa n  Có n đỉnh  Hai đỉnh bất kỳ luôn có cạnh nối  Tất cả các đỉnh có bậc n-1  Số cạnh là n*(n-1)/2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
  19. 6.5 Đồ thị đơn đặc biệt Đồ thị vòng - C Minh họa n  Có n đỉnh  Các đỉnh nối với nhau theo vòng tròn  Mỗi đỉnh có bậc là 2 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
  20. 6.5 Đồ thị đơn đặc biệt Đồ thị bánh xe - W Minh họa n  n+1 đỉnh  2n cạnh  n đỉnh bậc 3 và 1 đỉnh bậc n  Hai đỉnh bất kỳ luôn kề nhau Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
  21. 6.5 Đồ thị đơn đặc biệt Đồ thị lập phương :- Q Minh họa n  2n đỉnh n-1  (n-1).2 cạnh  Các đỉnh đều có bậc n – 1  Các đỉnh biểu diễn cho các dãy n bit. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21
  22. 6.5 Đồ thị đơn đặc biệt Ứng dụng  Mạng LAN  Mạng cục bộ cấu trúc hình sao  Mạng cục bộ cấu trúc vòng  Mạng cục bộ cấu trúc hỗn hợp  Xử lý song song Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22
  23. 6.6 Đồ thị phân đôi G = (V, E) Minh họa  G – đồ thị phân đôi nếu  V = V1 ∪ V2 , V1 ≠ ⨀, V2 ≠ ⨀, V1 ∩ V2 ≠ ⨀  ∀ (u, v) ∈ E⇒ u ∈ Vi ,v ∈ Vj,i ≠ j  G – đồ thị phân đôi đầy đủ nếu  G là độ thị phân đôi  ∀ u ∈ V1 và ∀ u ∈ V2 ⇒ (u,v) ∈ E Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23
  24. 6.6 Đồ thị phân đôi G = (V, E) Minh họa  G – đồ thị phân đôi nếu  V = V1 ∪ V2 , V1 V V1 ≠ ⨀, V2 ≠ ⨀, V1 ∩ V2 ≠ ⨀ 2  ∀ (u, v) ∈ E⇒ u ∈ Vi ,v ∈ Vj,i ≠ j  G – đồ thị phân đôi đầy đủ nếu  G là độ thị phân đôi  ∀ u ∈ V1 và ∀ u ∈ V2 ⇒ (u,v) ∈ E K 3x4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24
  25. 6.6 Đồ thị phân đôi Đồ thị có phân đổi không? Đồ thị có phân đổi không? ?  Không là đồ thị phân đôi  Đồ thị phân đôi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2525
  26. 6.6 Đồ thị phân đôi Xác định đồ thị phân đôi Xác định đồ thị phân đôi  Dùng breadth first search  Đánh số đỉnh 0, 푛ế 푣 푡ℎ ộ 1 Lv thuộc V = 1, 푛ế 푣 푡ℎ ộ 2 2, ℎư ệ푡  Đồ thị nào sau là phân đôi?  C6  Cn  K3  Kn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2626
  27. 6.7 Đồ thị đẳng cấu Xác định đẳng cấu  Xác định 2 đồ thị có vẽ cùng một cách hay không.  Khó xác định, có n! khả năng  Công thức phân tử giống nhau nhưng cấu trúc khác nhau.  Sử dụng các đại lượng bất biến:  Số đỉnh bằng nhau  Hai đồ thị là đẳng cấu nếu có một  Số cạnh bằng nhau song ánh giữa tập đỉnh của hai đồ  Bậc của các đỉnh bằng nhau thị đảm bảo quan hệ liền kế. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2727
  28. 6.8. Tính liên thông G =  Đường đi có độ dài n từ u tới v – dãy các cạnh e1 , e2 , ,en : e1 = (x0 , x1), , e1 = (xn-1 , xn) , u = x0 và v = xn .  Chu trình: đường đi có u ≡ v  Đường đi đơn: đường đi không lặp cạnh  Chu trình đơn: chu trình không lặp cạnh  Đường đi sơ cấp: đường đi không lặp đỉnh  Chu trình sơ cấp: chu trình không lặp đỉnh. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2828
  29. 6.8 Tính liên thông G =  Đồ thị vô hướng gọi là liên thông nếu: ∀ , 푣 ∈ , 푣: ∃ đườ푛𝑔 đ𝑖 𝑔𝑖ữ 푣à 푣  Đô thị vô hướng liên thông ⟹ tồn tại đường đi đơn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2929
  30. 6.8. Tính liên thông G = (V, E) Ví dụ  = 1 ∩ 2 , 1 ≠⊕, 2 ≠ ⨂, 1 ∩ 2 = ⊕  Nếu G liên thông ⟹ G1 thành phần liên thông  G liên thông ⟹ ∃! một thành phần liên thông (chính là G)  Đỉnh khớp: đỉnh nếu loại bỏ sẽ thu được lớn hơn 1 thành phần liên thông.  Cạnh cắt: cạnh nếu loại bỏ sẽ được lớn hơn 1 thành phần liên thông. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3030
  31. 6.8. Tính liên thông G = (V, E) – đồ thị có hướng  Liên thông mạnh nếu có đường đi giữa mọi cặp đỉnh u, v (cả hai chiều)  Liên thông yếu nếu có đường đi giữa 2 đỉnh bất kỳ trong đồ thị nền Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3131
  32. 6.8. Tính liên thông 1 7 C D 0 10 B 5 2 A 8 3 4 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3232
  33. 6.8. Tính liên thông Chu trình đơn, đường đi đơn 1 6 7 0 10 9 2 3 5 4 8 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3333
  34. 6.8. Tính liên thông Chu trình - đẳng cấu Ví dụ  Chu trình đơn với chiều dài k (k≥ 2) là đại lượng bất biến.  Sử dụng để kiểm tra tính đẳng cấu.  Không đẳng cấu vì đồ thị bên phải có chu trình đơn với chiều dài 3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3434
  35. Bài tập Đồ thị có phân đôi không? Đồ thị có đẳng cấu không Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35
  36. 6.9 Đồ thi Euler B B A D A G D C C 7 cầu ở Konigsberg Mô hình đồ thị Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36
  37. 6.9 Đồ thi Euler G = (V, E) Ví dụ  Chu trình Euler trong G là chu trình đơn chứa mọi cạnh của G  Một đường đi Euler là đường đi đơn chứa mọi cạnh của G  Đồ thị Euler: -G – liên thông, G có chu trình Euler.  Đồ thi nữa Euler : G liên thông, G có đường Euler
  38. 6.9 Đồ thi Euler G = (V, E) – liên thông  Điều kiện cần và đủ G có chu trình Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẳn  Điều kiện cần và đủ G có đường đi Euler khi và chỉ khi trong G tồn tại duy nhất 2 đỉnh bậc lẽ
  39. 6.9 Đồ thi Euler Tìm chu trình Euler Ví dụ  Input: G đồ thị liên thông có các đỉnh là đỉnh bậc chẳn  Output: chu trình Euler  C = chọn 1 chu trình bất kỳ  H = G đã xóa đị cạnh của C  While(H còn cạnh) do  C’ = chu trình trong H nhưng có đi qua đỉnh trong C  H = H đã xóa đi cạnh của C’ và đỉnh treo;  C = C cộng thêm C’ được chèn phù hợp  end  Thuật toán FLEURY
  40. 6.9 Đồ thi Euler  VD Đồ thị sau có các đường đi Euler là: d1: 1 2 3 4 2 5 4 1 5 d2: 1 2 4 3 2 5 1 4 5 3 2 4 1 5 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 40
  41. 6.9 Đồ thi Euler 3 3 2 4 2 4 1 5 1 5 Đồ thị nửa Euler 6 Đồ thị Euler Nguyễn Văn Hiệu, 2012, Discrete Mathematics 41
  42. 6.10 Hamilton G=(V, E)  Chu trình Hamilton trong G là chu trình sơ cấp chứ tất cả các đỉnh  Một đường Hamilton trong G là đường sơ cấp chứ tất cả các đỉnh  Đồ thị Hamilton là đồ thị có  Không có điều kiện cần và chu trình Hamilton. đủ để đồ thị tồn tại đường đi và chu trình  Đồ thi nữa Hamiltonr là đồ thị có đường Hamilton
  43. 6.6 Đồ thi Hamilton • G – đơn đồ thị, |V|= n, mọi u thuộc V, deg(u) ĐL1 ≥ n/2 , thì G đồ thị Hamilton • G – đơn đồ thị, |V|= n,mọi u thuộc V, deg(u) ĐL2 ≥ (n-1)/2 , thì G đồ thị nữa Hamilton • G – đồ thị đầy đủ, thì G đồ thị nữa Hamilton ĐL 3 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 45
  44. 6.10 Hamilton G – vô hướng G – có hướng Chu trình (t.ư. đường) Hamilton:- chu Chu trình (t.ư. đường) Hamilton:- chu trình (t.ư. đường) sơ cấp chứ tất cả trình (t.ư. đường) sơ cấp chứ tất cả các đỉnh các đỉnh Đồ thị Hamilton: - G chứa chu trình Đồ thị Hamilton: - G chứa chu trình Hamilton Hamilton Đồ thi nữa Hamiltonr :- G chứa Đồ thi nữa Hamilton :- G chứa đường đường Hamilton Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 46
  45. Đồ thị có hướng Directed graph Đồ thị vô hướng Undirected graph Đơn đồ thị Simple graph Đa đồ thị Multi-graph Giả đồ thị Pseudo-graph Đỉnh Vertex / Vertices Cạnh Edge Cung Arc Cạnh song song Parallel Edges Cung song song Parallel Arcs Khuyên Loop Nguyễn Văn Hiệu, 2012, Discrete Mathematics 47
  46. THAT’S ALL; THANK YOU What NEXT? BIỂU DIỄN ĐỒ THỊ