Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 4: Các khái niệm về Đồ Thị - Võ Tấn Dũng

GV: Võ Tấn Dũng TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM MÔN TOÁN RỜI RẠC ĐƠ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)}. Đồ thị G1 a b e d c g f h Đ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.  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)}. Đồ thị G2 d Cạnh song song e a b c f g h 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):  Một cạnh tương ứng với hai đỉnh trùng nhau.  Đơn đồ thị  Đồ thị không có vòng và cạnh song song  Đa đồ thị  Các đồ thị không phải là đơn đồ thị x y z A B C D ĐỒ 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 =  e có hướng từ a đến b  a: đỉnh đầu; b: đỉnh cuối  e là cạnh vòng  ab ab 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). 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.  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)  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  Cạnh treo có đầu mút là một đỉnh treo  Đồ thị rỗng: deg(v)=0 v a b c d efg 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. 32 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. 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). 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. Định lý:  Giả sử G = (V, E) là đồ thị có hướng. Khi đó: Ví dụ f a b c ed deg-(d) = 2 deg+(d)= 1 deg-(f) = 0 deg+(f)= 0 b kề tới c và c kề từ b deg-(a) = 0 deg+(a)= 2 a- đỉnh nguồn deg-(e) = 2 deg+(e)= 0 e – đỉnh đích (target) Ví dụ: hai đồ thị sau đẳng cấu 1  DN, 2  CT, 3  BD, 4  AG 17 ĐỒ THỊ ĐẲNG CẤU 18 Đ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. ĐỒ 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 ĐỒ THỊ ĐẲNG CẤU 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 BÀI TẬP 21 Sự đẳng cấu giữa các đồ thị  Chứng minh 2 đồ thị đẳng cấu  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. a b cd e f b d a e fc BÀI TẬP 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. a b c d e • Cùng số lượng đỉnh • Cùng số lượng cạnh • Khác số lượng đỉnh bậc 2 (1 3) 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. 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 Ví dụ: 1, 2, 5, 3, 4 hoặc 1, a, 2, c, 5, d, 3, e, 4 • Là đường đi đơn 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 2 3 4 a b c 1 5 d e 2 3 4 a b c 1 5 d e Đường đi (Path) 28 P1 Ví dụ (tiếp) P1=(1,b,2,h,3) là đường đi đơn P2=(4,c,5,e,2,g,6,f,5,d,1) là đường đi nhưng không là đường đi đơn 24 1 5 3 6 a c b e d f g hP2 P1 Ví dụ (tiếp) P1=(1, b, 2, h, 3) là đường đi đơn P2=(4,c,5,e,2,g,6,f,5,d,1) là đường đi nhưng không là đường đi đơn 24 1 5 3 6 a c b e d f g hP2 Chu trình 1, 2, 3, 1. (hay 1, a, 2, b, 3, e) • Chu trình đơn Chu trình: (1, 2, 3, 4, 1) hay 1, a, 2, b, 3, c, 4, d, 1 • Chu trình đơn 2 3 4 a b cd 1 e 2 3 4 a b cd 1 e Chu trình (Cycle) 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 C1 XU V W Z Y a c b e d f g h C2  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 C1 XU V W Z Y a c b e d f g hC2 Ví dụ: Chu trình trên đồ thị vô hướng 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 ĐỒ 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. 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 đủ Kn  Đơn đồ thị  Số đỉnh: |V| = n  Bậc: deg(v) = n – 1 v V  Số cạnh: |E| = n(n - 1) / 2 K5K4 K1 K2 K3 K6 ĐỒ THỊ ĐẦY ĐỦ Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất. 38  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 ĐỒ THỊ LƯỠNG PHÂN (HAI PHÍA) ĐỒ 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. ĐỒ 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. 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 đó  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. 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: 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. Ví dụ ma trận kề 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ự. 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ố. MA TRẬN TRỌNG SỐ Hết chương