Toán học - Bài 6: Lý thuyết đồ thị

BÀI 6 LÝ THUYẾT ĐỒ THỊ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1 Giáo viên: TS. Nguyễn Văn Hiệu Email: [email protected] Tổng quan về đồ thi Nội dung 6.1. Giới thiệu 6.2. Định nghĩa 6.3. Thuật ngữ cơ sở 6.4. Định lý cơ sở về bậc 6.5. Đồ thị đơn đặc biệt Nội dung 6.6. Đồ thị phân đôi 6.7. Đồ thị đẳng cấu 6.8. Tính liên thông 6.9. Đồ thi Euler 6.10. Đồ thị Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2 6.1. Giới thiệu Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3 Lý thuyết đồ thị  Nghành học lâu đời, nhưng dùng nhiều trong ứng dụng hiện đại  Leohard Euler Ứng dụng Xây dựng mật điện trên một bảng điện 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 giữa hai thành phố Lập lịch thi Phân chia kênh truyền cho đài truyền hình  6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4 Đơn đồ thị G = (V, E)  V - tập đỉnh,  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.  ∃! (u,v) ∈ 𝐸 ⟹ ∃! (𝑣, 𝑢) ∈ 𝐸  (u, u )∉ 𝐸 Ứng dụng  Mạng gồm các máy tính và các kênh điện thoại.  Giữa hai máy tính bất kì có nhiêu nhất 1 kênh điện thoại.  Kênh thoại cho phép liên lạc hai chiều  Không có máy tính nào được nối với chính nó. 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5 Đơn đồ thị G = (V, E)  V - tập đỉnh,  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.  ∃! (u,v) ∈ 𝐸 ⟹ ∃! (𝑣, 𝑢) ∈ 𝐸  (u, u )∉ 𝐸 Ứng dụng  Mạng điện thoại cố định  Mạng giao thông  Mạng xe buýt 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6 Đa đồ thị G = (V, E)  V - tập đỉnh,  E : cho phép nhiều hơn hai cạnh nối 2 đỉnh phân biệt.  (u,v) ∈ 𝐸  (u, u )∉ 𝐸 Ứng dụng  Mạng gồm các máy tính và các kênh điện thoại.  Cho phép hai máy tính nối nhiều kênh thoại (do truyền tài nhiều) 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7 Giả đồ thị G = (V, E)  V - tập đỉnh,  E : cho phép vòng (đỉnh đầu và cuối trùng nhau)  (u,u) ∈ 𝐸 Ứng dụng  Mạng gồm các máy tính và các kênh điện thoại.  Cho phép máy tính nối u kênh thoại với chính nó 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8 Chú ý ĐỒ THI ≡ ĐỒ THỊ VÔ HƯỚNG Chú ý ĐƠN ĐỒ THỊ ⊂ ĐA ĐỒ THỊ ⊂ GIẢ ĐỒ THỊ 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9 Đơn đồ thị có hướ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 )∉ 𝐸 Ứng dụng 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10 Đa đồ thị có hướ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 )∉ 𝐸 Ứng dụng  Hai cung tương ứng với một cặp đỉnh được gọi là cung lặp 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11 Đồ thị tình yêu   Hai người có ít nhất cùng 1 sở thích thì có thể ghép đôi ? Tìm cách ghép đôi sao cho số người cô đơn là ít nhất Ứng dụng  G = (V, E) V = {A, B , C , D , E} E: (u,v) ∈ E nếu u và v có cùng một sở thích 6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12 Hội thảo video  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 Ứng dụng   6.2. Định nghĩa Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13 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 6.3. Thuật ngữ cơ sở Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14 Đồ thị vô hướng  u và v – đỉnh liền kề  e - cạnh liên thuộc với u và v  u và v – đỉnh đầu của e  Bậc của u là số cạnh liên thuộc với u.  Đỉnh có bậc 0 - đỉnh cô lập  Đỉnh có bậc 1 - đỉnh treo.  Khuyên được tính bậc 2 G = (V, E) , e = (u,v) ∈ E deg(0) = 3, deg(5) = 1, deg(2) = 0, deg(6) = 5,. 1 2 0 3 6 4 5 7 6.3. Thuật ngữ cơ sở Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15 Đồ thị có hướng  u – nối tới v  v – nối từ u  u – đỉnh đầu cung e  v – đỉnh cuối cung e  deg + (u) – bậc ra của u  deg - (u) – bậc vào của u G = (V, E) , e = (u,v) ∈ E deg+(s) = 2, deg-(s) = 1, deg+(x) = 1, deg-(v) = 0, u v t s x 6.4 Định lý cơ sở về bậc Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16 Đồ thị vô hướng  2 |E| = ∑ v€ V deg (v) Tổng số bậc lẽ của đồ thị là một số chẳn. G = (V, E) 1 2 0 3 6 4 5 7 6.4 Định lý cơ sở về bậc Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17 Đồ thị có hướng  ∑ v€ V deg + (v) = ∑ u € V deg - (u) = | E |  Bỏ qua hướng của G ta có đồ thị vô hướng nền của G có số cạnh bằng số cung của G G = (V, E) u v t s x 6.5 Đồ thị đơn đặc biệt Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18 Đồ thị đầy đủ - Kn  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 Minh họa 6.5 Đồ thị đơn đặc biệt Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19 Đồ thị vòng - Cn  Có n đỉnh  Các đỉnh nối với nhau theo vòng tròn  Mỗi đỉnh có bậc là 2 Minh họa 6.5 Đồ thị đơn đặc biệt Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20 Đồ thị bánh xe - Wn  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 Minh họa 6.5 Đồ thị đơn đặc biệt Nguyễn Văn Hiệu, 2012, Discrete Mathematics 21 Đồ thị lập phương :- Qn  2n đỉnh  (n-1).2n-1 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. Minh họa 6.5 Đồ thị đơn đặc biệt Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22 Ứ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 6.6 Đồ thị phân đôi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23 G = (V, E)  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 Minh họa 6.6 Đồ thị phân đôi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24 G = (V, E)  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 Minh họa V1 V2 K3x4 6.6 Đồ thị phân đôi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 25 Đồ 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 6.6 Đồ thị phân đôi Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26 Xác định đồ thị phân đôi  Dùng breadth first search  Đánh số đỉnh Lv thuộc V = 0, 𝑛ế𝑢 𝑣 𝑡ℎ𝑢ộ𝑐 𝑉1 1, 𝑛ế𝑢 𝑣 𝑡ℎ𝑢ộ𝑐 𝑉2 2, 𝑐ℎư𝑎 𝑑𝑢𝑦ệ𝑡  Đồ thị nào sau là phân đôi?  C6  Cn  K3  Kn Xác định đồ thị phân đôi 6.7 Đồ thị đẳng cấu Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27  Xác định 2 đồ thị có vẽ cùng một cách hay không.  Công thức phân tử giống nhau nhưng cấu trúc khác nhau.  Hai đồ thị là đẳng cấu nếu có một song ánh giữa tập đỉnh của hai đồ thị đảm bảo quan hệ liền kế. Xác định đẳng cấu  Khó xác định, có n! khả năng  Sử dụng các đại lượng bất biến:  Số đỉnh bằng nhau  Số cạnh bằng nhau  Bậc của các đỉnh bằng nhau 6.8. Tính liên thông Nguyễn Văn Hiệu, 2012, Discrete Mathematics 28 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. 6.8 Tính liên thông Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29 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 6.8. Tính liên thông Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30 G = (V, E)  𝐺 = 𝐺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. Ví dụ 6.8. Tính liên thông Nguyễn Văn Hiệu, 2012, Discrete Mathematics 31 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 6.8. Tính liên thông Nguyễn Văn Hiệu, 2012, Discrete Mathematics 32 1 0 5 2 3 4 C B 8 10 7 A D 6.8. Tính liên thông Nguyễn Văn Hiệu, 2012, Discrete Mathematics 33 Chu trình đơn, đường đi đơn 1 6 0 9 2 3 4 5 8 10 7 6.8. Tính liên thông Chu trình - đẳng cấu  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. Ví dụ  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 34 Bài tập Nguyễn Văn Hiệu, 2012, Discrete Mathematics Đồ thị có phân đôi không? Đồ thị có đẳng cấu không 35 6.9 Đồ thi Euler Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36 A D B C B D A C 7 cầu ở Konigsberg Mô hình đồ thị G 6.9 Đồ thi Euler G = (V, E)  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 Ví dụ 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ẽ 6.9 Đồ thi Euler Tìm chu trình Euler  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 Ví dụ  Thuật toán FLEURY  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 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 40 3 4 5 1 2 6.9 Đồ thi Euler Nguyễn Văn Hiệu, 2012, Discrete Mathematics 41 Đồ thị nửa Euler Đồ thị Euler 3 4 5 1 2 3 4 5 1 2 6 6.9 Đồ thi Euler 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ó chu trình Hamilton.  Đồ thi nữa Hamiltonr là đồ thị có đường Hamilton  Không có điều kiện cần và đủ để đồ thị tồn tại đường đi và chu trình 6.6 Đồ thi Hamilton ĐL1 • G – đơn đồ thị, |V|= n, mọi u thuộc V, deg(u) ≥ n/2 , thì G đồ thị Hamilton ĐL2 • G – đơn đồ thị, |V|= n,mọi u thuộc V, deg(u) ≥ (n-1)/2 , thì G đồ thị nữa Hamilton ĐL 3 • G – đồ thị đầy đủ, thì G đồ thị nữa Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 45 6.10 Hamilton G – vô hướng Chu trình (t.ư. đường) Hamilton:- chu trình (t.ư. đường) sơ cấp chứ tất cả các đỉnh Đồ thị Hamilton: - G chứa chu trình Hamilton Đồ thi nữa Hamiltonr :- G chứa đường Hamilton G – có hướng Chu trình (t.ư. đường) Hamilton:- chu trình (t.ư. đường) sơ cấp chứ tất cả các đỉnh Đồ thị Hamilton: - G chứa chu trình Hamilton Đồ thi nữa Hamilton :- G chứa đường Hamilton Nguyễn Văn Hiệu, 2012, Discrete Mathematics 46 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 47 Đồ 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 THAT’S ALL; THANK YOU What NEXT? BIỂU DIỄN ĐỒ THỊ