Bài giảng Lí thuyết đồ thị - Trần Quốc Việt

Nội dung text: Bài giảng Lí thuyết đồ thị - Trần Quốc Việt

1. 29/09/2014 Chương 1: Giới thiệu tổng quan Bài giảng Khái niệm đồ thị, một số lĩnh vực ứng dụng của đồ thị Định nghĩa LÝ THUYẾT ĐỒ THỊ Một số đồ thị đặc biệt (GRAPH THEORY) Biểu diễn đồ thị Đường đi và chu trình Trần Quốc Việt Liên thông và thành phần liên thông Một số vấn đề liên quan đến cài đặt đồ thị Tài liệu tham khảo: • Nguyễn Cam, Chu Đức Khánh, Lý thuyết Đồ thị, 1998. • Kenneth H. Rosen, Discrete Mathematics and Its Applications 1 2 Khái niệm Một số lĩnh vực ứng dụng . Một đồ thị hiểu đơn giản là một cấu trúc rời rạc gồm tập Trong thực tế, rất nhiều bài toán thuộc các lĩnh vực khác đỉnh, và tập cạnh nối các đỉnh nhau được giải bằng đồ thị: . Lĩnh vực mạng máy tính: Biểu diễn mạng máy tính Ví dụ: Đỉnh 2 3 a d 1 e 4 5 b c cạnh Xác định 2 máy có thể liên lạc vơi nhau trên một mạng, Đồ thị vô hướng Đồ thị có hướng 3 4 1
2. 29/09/2014 Một số lĩnh vực ứng dụng Một số lĩnh vực ứng dụng . Lĩnh vực giao thông: Tìm đường đi, đường đi ngắn nhất . Giải các bài toán về lập lịch, thời khóa biểu, và phân bố giữa hai thành phố trong mạng giao thông, tần số cho các trạm phát thanh và truyền hình Tỉnh C  . . e2 5 Tỉnh A e  e 12 3 4 1 8 e Tỉnh 4 Tỉnh D 6  Mỗi đỉnh: một tỉnh F  e7   Mỗi cạnh nối 2 đỉnh u,v: Có 2 đường đi trực tiếp giữa 2 tỉnh e9 20 3 e6 u,v e8 6 e5  Con số trên mỗi cạnh: Độ dài  đường đi trực tiếp giữa 2 tỉnh. Tỉnh E  . Yêu cầu: Tìm đường đi ngắn nhất từ một tỉnh nào đó đến một 5 6 tỉnh khác (chẳng hạn từ A đến F)? Ví dụ: Bài toán về các cây cầu ở Konigsberg: 2. Một số định nghĩa Đồ thị vô hướng (undirected graph ):  Đồ thị vô hướng G=(V,E) với: V  là tập các đỉnh E: Là đa tập hợp với các phần tử có dạng (u,v) với u,v V không có thứ tự, gọi là các cạnh của đồ thị  Biểu diễn bằng biểu đồ: Mỗi đỉnh  một điểm Mỗi cạnh (u,v)  một cạnh vô hướng nối giữa u và v 1 2 Tìm cách đi qua cả bảy cây cầu, sau đó về điểm xuất phát, mỗi cây Ví dụ: Cho đồ thị G với Tập đỉnh V ={1,2,3,4} cầu chỉ đi qua một lần ? Giải bằng đồ thị tập cạnh E ={(1,2), (2,3), (3,4), (2,4)} . Kí hiệu: G = (V,E) 3 4 7 2
3. 29/09/2014 2. Một số định nghĩa 2. Một số định nghĩa Cho đồ thị vô hướng G=(V,E) Cho đồ thị vô hướng G=(V,E):  Với cạnh e=(u,v) E, u,v gọi là 2 đỉnh kề nhau, e gọi là cạnh liên thuộc  G là đồ thị đơn (Simple graph) nếu G không có khuyên và không có với 2 đỉnh u,v cạnh song song  Hai cạnh e1, e2 liên kết cùng một cặp đỉnh khác nhau được gọi là 2  G gọi là đa đồ thị (multigraphs)nếu G không có khuyên và có thể cạnh song song (paralell edges). có các cạnh song song  Một cạnh trên cùng một đỉnh gọi khuyên (loop).  G gọi là giả đồ thị (pseudographs) nếu G có thể có cả khuyên và các Ví dụ: 2 Đỉnh 1 kề với đỉnh 2 e e2 cạnh song song. 1 Đỉnh 2 kề với đỉnh 3 e3 1 3 Đỉnh 5 kề với đỉnh 4 e Đỉnh 1 không kề với đỉnh 4 4 e  e5 6 e7 e3, e4: Các cạnh song song Đa đồ thị Giả đồ thị 5 4 e8: Khuyên Đơn đồ thị e9 e8 9 10 2. Một số định nghĩa 2. Một số định nghĩa Bậc của đỉnh trong đồ thị vô hướng: Bậc của đỉnh v Đồ thị có hướng (directed graph) Đồ thị có hướng G = (V,E), trong đồ thị vô hướng là số cạnh liên thuộc với v, kí hiệu V  là tập các đỉnh, E là tập các cặp (u,v) có thứ tự trong V gọi là deg(v). các cung. . Đỉnh có bậc 0 gọi là đỉnh cô lập (isolated vertex)  Với (u,v) E, u gọi là đỉnh đầu, v gọi là đỉnh cuối của cung (u,v) và v gọi là đỉnh kề của u. . Đỉnh có bậc 1 gọi là đỉnh treo (pendant vertex)  Hai cung e1, e2 liên kết cùng một cặp đỉnh được gọi là 2 cung song song (paralell edges). Ví dụ: deg(1)=deg(5)=2,deg(4)=3,  Cung từ một đỉnh đến chính nó gọi là khuyên (loop). 1 2 deg(3)=1, deg(6)=0 e 1 .A,B,C,D: Các đỉnh A B 5 3: Đỉnh treo, 6: Đỉnh cô lập .e ,e ,e ,e ,e ,e ,e ,e : Các cung 6 e2 1 2 3 4 5 6 7 8 .e1,e2: Song song ngược chiều e3 4 3 e7 e8 e4 .e7,e8: Song song cùng chiều .e : Khuyên 11 D C e6 6 12 e5 3
4. 29/09/2014 2. Một số định nghĩa 2. Một số định nghĩa Cho đồ thị có hướng G=(V, E) Tóm tắt một số thuật ngữ . G là đơn đồ thị có hướng (Simple directed Graphs) nếu G không có khuyên và không có cạnh song song cùng chiều. . G là đa đồ thị có hướng (Directed multigraphs) nếu G có thể có các khuyên, các cạnh song song cùng chiều Đồ thị hỗn hợp (Mixed Graph): là đồ thị mà có chứa cả cạnh vô hướng và cạnh có hướng Ví dụ 1 2 Đơn đồ thị có hướng 4 3 13 14 2. Một số định nghĩa 2. Một số định nghĩa Bậc của đỉnh trong đồ thị có hướng: Cho đồ thị có hướng G = (V,E) Đồ thị con (subgraph ): Cho 2 đồ thị (cùng có hướng hoặc cùng vô và v V. hướng) G=(V,E) và H=(X,U). H được gọi là đồ thị con của G nếu  Nửa bậc trong của v, kí hiệu deg-(v) là số cung đến đỉnh v. XV và U  E. Kí hiệu H G  Nửa bậc ngoài của v, kí hiệu deg+(v) là số cung xuất phát từ v. Ví dụ: Ví dụ: Cho đồ thị e1 b b deg+(1)=? a d d 1 2 deg-(1)=? a e 2 deg+(2)=? deg-(2)=? + e e3 deg (4)=? c c e7 e8 - e4 deg (4)=? deg(1)? G H deg(2)? e6 H là đồ thị con của G 3 4 15 16 e5 4
5. 29/09/2014 2. Một số định nghĩa 3. Một số đồ thị đặc biệt Đồ thị khung (spanning subgraph): Cho 2 đồ thị G=(V,E) và Đồ thị đủ (Complete Graph): Một đơn đồ thị vô hướng H=(X,U), H G. Nếu X=V thì H gọi là đồ thị khung của G G=(V,E) với |V|=n, được gọi là đồ thị đủ cấp n(kí hiệu Kn) Ví dụ: nếu với mỗi cặp đỉnh khác nhau đều kề nhau. b b Ví dụ: d a d a e c e c G K H K1 2 K3 K4 K5 H là đồ thị khung của G Một số đồ thị Kn (n=1,2, ,5)  Một đồ thị đủ cấp n thì có số cạnh là n(n-1)/2 17 18 Một số đồ thị đặc biệt Một số đồ thị đặc biệt Đồ thị vòng (Cycles): Đơn đồ thị n đỉnh v1, v2, , vn (n 3) với n Đồ thị lưỡng phân (Bipartite Graphs): Đơn đồ thị G=(V,E) gọi là cạnh (v1,v2), (v2,v3), , (vn-1,vn), (vn,v1) được gọi là đồ thị vòng, lưỡng phân nếu V=V V , với V V =, V , V  và mỗi cạnh ký hiệu là C . 1 2 1 2 1 2 n trong E đều nối một đỉnh trong V1 với một đỉnh trong V2. V1 V Như vậy, mỗi đỉnh của Cn có bậc là 2. 2 19 20 5
6. 29/09/2014 a c b Kiểm tra G là lưỡng d phân? e Một số đồ thị đặc biệt f G Định lý: Một đơn đồ thị là lưõng phân nếu và chỉ nếu có thể g V dùng 1 trong 2 màu khác nhau cho trước để gán cho mỗi 1 V2 đỉnh sao cho không có 2 đỉnh kề nhau có chung một màu a a a Ví dụ: Đồ thị nào sau đây là lưỡng phân? c c c 7 b b b d d d 1 A B 6 e e e f f f 2 5 F C g g g E V1 V V 3 D V2 1 V2 1 V2 4 G H R={a}, W= R={a}, W={c} R={a,b}, 21 W={c} 22 a c a c b b d d e e f f g g V V1 V 1 V2 2 R={a,b}, R={a,b,g}, W={c,d} W={c,d} a c a c b b d d e e f f g g V V 1 V2 1 V2 R={a,b,g,e}, R={a,b,g,e}, 23 24 W={c,d} W={c,d,f} 6
7. 29/09/2014 Một số đồ thị đặc biệt Một số đồ thị đặc biệt Đồ thị lưỡng phân đủ (Complete Bipartite Graphs): Đồ thị lưỡng Đồ thị bánh xe (Wheels): Kí hiệu Wn , nhận được từ phân G=(X1X2,E) với |V1|=m, |V2|=n là lưỡng phân đủ, kí hiệu Km,n đồ thị Cn (n≥3) bằng cách thêm một đỉnh mới và bổ nếu mọi đỉnh trong V1 đều kề với mọi đỉnh trong V2 sung các cạnh nối đỉnh vừa thêm với các đỉnh trong Cn. Ví dụ: V 1 V2 Một số đồ thị Wn, (3≤n ≤6) 25 26 4. Định lý bắt tay Một số đồ thị đặc biệt (The handshaking Theorem) Đồ thị lập phương (n-Cubes): Đồ thị lập phương n Định lý: Cho đồ thị vô hướng G=(V,E) với m cạnh, Ta có: n đỉnh (kí hiệu Qn)là đồ thị với các đỉnh biểu diễn 2 xâu 2m deg(v) nhị phân độ dài n. Hai đỉnh của nó gọi là kề nhau nếu v V như hai xâu nhị phân tương ứng chỉ khác nhau 1 bit. C/m:???? Ví dụ: Ví dụ: Đồ thị G có 6 đỉnh và tất cả các đỉnh có bậc là 6. Tính số cạnh của G? 27 28 7
8. 29/09/2014 4. Định lý 1: Định lý bắt tay Định lý 2 Hệ quả: Định lý: G=(V,E) là đồ thị vô hướng có m cung, ta có: i) Tổng bậc của các đỉnh bậc lẻ trong một đồ thị vô hướng G là m deg (v) deg (v) một số chẵn v V v V Ví dụ: ii) Mọi đồ thị vô hướng đều có một số chẵn các đỉnh bậc lẻ 1 e1 m=|E|=8 iii) Đồ thị K có n ( n 1 ) cạnh n 1 2 deg (v) deg (1) deg (2) deg (3) deg (4) 2 e2  v V 3 2 1 2 8 C/m:??? e3 e7 e8 e4 3 e6 deg (v) deg (1) deg (2) deg (3) deg (4) 4 v V e5 2 1 2 3 8 29 30 6. Biểu diễn đồ thị bằng ma trận kề 5. Biểu diễn đồ thị bằng danh sách kề (Adjacency Matrix) G=(V,E) không có cạnh song song (G không có cạnh song song cùng Cho đồ thị G=(V,E), tập đỉnh V={v1, v2, , vn} và tập chiều nếu G có hướng). G có thể được biểu diễn bằng cách liệt kê tất cạnh/cung E={e1, e2, , em}. Ma trận kề của G ứng với thứ tự cả các đỉnh của G, mỗi đỉnh liệt kê các đỉnh kề với nó các đỉnh v1, v2, , vn là ma trận vuông cấp n được định nghĩa Ví dụ: như sau: b Đỉnh Các đỉnh kề a d a b,d,e,c b a,c,d A (aij )1 i, j n Với aij=số cạnh/cung nối từ đỉnh vi đến c a,b,d đỉnh vj e c d a,b,c e a  Nếu G là đồ thị vô hướng thì A đối xứng Biểu diễn bằng danh sách kề khá cồng kềnh, đặc biệt khi G có nhiều cạnh ít được dùng trong các thuật toán về đồ thị 31 32 8
9. 29/09/2014 Biểu diễn đồ thị bằng ma trận kề (tt) Biểu diễn đồ thị bằng ma trận kề (tt) Ví dụ: Ma trận kề 2 1 5 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 Ví dụ: Cho G=(V,E) với ma trận kề như sau: 0 1 0 0 1 3 4 0 0 1 1 0 A B C D E A 0 0 1 0 0 - Đỉnh A có bậc 1 B A B C D E F B 0 0 2 1 0 - Đỉnh B có bậc 3 A M= 0 1 0 0 0 0 C 1 2 0 0 1 - Đỉnh C có bậc 4 A 0 0 0 0 0 0 - Đỉnh D có bậc 2 C B D 0 1 0 0 1 C 0 1 0 0 0 0 E 0 0 1 1 0 - Đỉnh E có bậc 2 F D D 1 0 1 0 1 0 E 0 0 0 0 0 1 E F 0 0 0 0 0 0 33 34 7. Biểu diễn đồ thị bằng ma trận liên thuộc Biểu diễn đồ thị bằng ma trận kề (tt) (Incidence Matrix) Cho đồ thị vô hướng G=(V,E),V={v1,v2, ,vn},E={e1,e2, ,em}. Ma trận liên thuộc của G là ma trận cấp n m được định nghĩa như Sau: 1 nếu ej liên thuộc với vi . mij= M (mij )1 i n,1 j m 0 nếu ej không liên thuộc với vi Ví dụ: e1 e2 e3 e4 e5 e6 e7 e1 2 e2 3 1 1 0 1 0 0 0 0 1 2 1 1 0 1 0 0 0 e e 3 0 1 0 0 1 0 0 e3 4 5 4 0 0 0 0 1 1 0 5 0 0 1 1 0 1 1 6 e7 5 e6 4 6 0 0 0 0 0 0 1 35 36 9
10. 29/09/2014 Biểu diễn đồ thị bằng ma trận liên thuộc (tt) Biểu diễn đồ thị bằng ma trận liên thuộc (tt)  Cho đồ thị có hướng G=(V,E),V={v1,v2, ,vn}, E={e1, e2, , Đồ thi Ma trận liên thuộc em}. Ma trận liên thuộc của G là ma trận cấp n m được xác định như sau: 1 nếu ej rời khỏi đỉnh i M (m ) ij 1 i n,1 j m mij= 0 nếu ej không liên thuộc với vi Ví dụ: -1 nếu ej đến đỉnh i 1 e1 e2 e3 e4 e5 e 2 1 1 1 0 1 1 0 1 1 0 0 0 e e 2 4 3 e2 0 1 1 0 1 3 0 0 0 1 1 4 3 4 e5 37 38 8. Đồ thị đẳng cấu Bài tập (Graph Isomorphism) Biểu diễn các đồ thị sau bằng ma trận kề, ma trận liên Định nghĩa: Hai đồ thị G1=(V1,E1) và G2=(V2,E2) gọi là đẳng cấu với nhau nếu tồn tại song ánh f:V1  V2 sao cho: 1 thuộc A B i,j V , (i,j) E (f(i), f(j)) E e3 1 1 2 2 Nghĩa là: f bảo toàn tính chất kề của các đỉnh. Hơn nữa, cũng bảo toàn E e F e e2 e7 5 bậc của đỉnh. 1 e e e e e 1 6 3 1 2 6 4 e7 H 1 2 e e3 e e Ví dụ: f được xác định 5 4 C 8 D C D e9 f:{1,2,3,4}{A,B,C,D} 5 4 G1 G2 2 Với: A e1 B e1 e4 f(1)=C; f(2)=B; 4 3 1 e3 A B 3 f(3)=D; f(4)=A G1 e e7 G2 e3 7 C e e2 e2 5 f bảo toàn tính chất kề của các đỉnh G1, G2 đẳng cấu e5 e6 e8 G3 D E 4 e6 5 G e4 4 H 39 40 10
11. 29/09/2014 Đồ thị đẳng cấu (tt) 9. Đường đi và chu trình Ví dụ: Các cặp đồ thị sau đây có phải đẳng cấu không? . Đường đi (Path) có độ dài k từ đỉnh u đến đỉnh v của đồ thị 1 2 A B 4 2 G=(V,E) là dãy các đỉnh x0,x1,x2, ,xk, x0=u, xk=v và (xi, xi+1) là a) b) một cạnh/cung của G. Có thể biểu diễn đường đi bởi dãy các đỉnh 2 4 5 3 E F 5 6 cạnh/cung liên tiếp: 8 G H 7 P=(x0, e1, x1, e2, ,xk-1, ek, xk) 3 5 1 4 C D 3 1 Với: x =u, x =v, e =(x ,x ) E G2 G 0 k i i-1 i G1 G1 2 d) 5 A •(A,e1,B,e4,C,e6,D) là một đường c) 2 2 C A B e3 đi có độ dài 3 từ đỉnh A và đỉnh D 2 6 e8 1 1 3 3 3 4 e1 C e6 E •(E,e7,D,e6,C,e4,B,e1,A) là đường 7 e2 đi từ E đến A có độ dài 4 e4 D E 9 e7 4 5 4 5 1 8 B e5 D H G 41 42 G G1 2 Đường đi và chu trình (tt) Đường đi và chu trình (tt) . Đường đi không có lặp lại các cạnh/cung gọi là đường đi đơn.  Chu trình Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là . Đường đi không có lặp lại đỉnh gọi là đường sơ cấp chu trình. • Chu trình gọi là đơn nếu không có sự lặp lại các cạnh (hay Ví dụ: cung)  (A,e1,B,e4,C,e6,D) là một đường đi sơ cấp có độ dài 3 từ đỉnh A và • Chu trình gọi là sơ cấp nếu không có sự lặp lại các đỉnh đỉnh D (A,e1,B,e5,D,e5,B,e4,C) không phải là đường đi đơn  (A,e1,B,e4,C,e3,B,e5,D) là đường đi đơn từ A đến D nhưng không phải là là đường đi sơ cấp  Định lý: Cho đồ thị G=(V,E) có ma trận kề là A. Số đường đi khác nhau có độ dài r từ đỉnh i đến đỉnh j của đơn đồ thị G . Mọi đường đi sơ cấp đều là đường đi đơn r là giá trị của phần tử aij trong ma trận A 43 44 11
12. 29/09/2014 10. Sự liên thông – thành phần liên Đường đi và chu trình (tt) thông Ví dụ: Cho đồ thị G như hình dưới. Số đường đi có độ dài 3 từ A đến  Định nghĩa: Đồ thị vô hướng G=(V,E) gọi là liên thông nếu D? luôn tồn tại đường đi giữa 2 đỉnh u, v bất kỳ trong V. A C 0 1 0 1 0 e3 e 1 0 2 1 0 8 e1 e E A 0 2 0 1 1 e 6 2 1 1 1 0 1 e4 e7 0 0 1 1 0 B e5 D G1: Liên thông G2: Không liên thông 45 46 Sự liên thông–thành phần liên thông (tt) Sự liên thông–thành phần liên thông (tt)  Định nghĩa: Cho đồ thi vô hướng G=(V,E). Trên V ta định nghĩa quan Đồ thi có hướng G gọi là liên thông yếu (Weakly connected) nếu hệ  như sau: đồ thị vô hướng tương ứng của nó là liên thông x,y V, xy  có một đường đi giữa x và y Đồ thi có hướng G gọi là liên thông mạnh (strongly connected) Ta có:  là quan hệ tương đương trên V và mỗi lớp tương đương là gọi là một thành phần liên thông của G nếu với mọi cặp đỉnh khác nhau u,v luôn có đường đi từ đỉnh x đến đỉnh y và ngược lại. Ví dụ: Ví dụ: u v w u v w x x y s t y s t G1: có 1 thành phần G2: có 2 thành phần G3: có 4 thành phần liên thông liên thông liên thông G:liên thông mạnh G’ là liên thông yếu (không lt mạnh) 47 48 12
13. 29/09/2014 Sự liên thông–thành phần liên thông (tt) Sự liên thông–thành phần liên thông (tt) Một thành phần liên thông mạnh của đồ thi có hướng Định nghĩa: Cho G liên thông G là một đồ thị con liên thông mạnh của G và không là . Cạnh e của G gọi là cầu nếu sau khi loại bỏ e, G không đồ thị con của bất kỳ đồ thi con liên thông mạnh nào còn liên thông khác của G. . Đỉnh v trong G gọi là đỉnh nối (đỉnh cắt/vertex cut) nếu sau khi loại bỏ v cùng với các cạnh liên thuộc với nó thì G Ví dụ: Tìm các thành phần liên thông mạnh của các đồ thị không còn liên thông. có hướng sau: Ví dụ: e 1 2 2 e 6 5 e7 5 7 Các đỉnh 4,5 là đỉnh nối e1 e4 Cạnh e là cầu e6 e8 4 3 e3 4 8 49 50 Sự liên thông–thành phần liên thông (tt) 11. Duyệt đồ thi Mệnh đề: Giữa mọi cặp đỉnh phân biệt của một đồ thị vô hướng là thăm qua tất cả các đỉnh của đồ thị liên thông luôn có đường đi sơ cấp. Thường dùng một trong 2 cách để duyệt một đồ thị liên Mệnh đề: Mọi đơn đồ thị vô hướng n đỉnh (n 2) có tổng bậc thông: của hai đỉnh tuỳ ý không nhỏ hơn n đều là đồ thị liên thông.  Duyệt theo chiều sâu (DFS) Hệ quả: Đơn đồ thị mà bậc của mỗi đỉnh của nó không nhỏ hơn  Duyệt theo chiều rộng (BFS) 2 một nửa số đỉnh là đồ thị liên thông. Ví dụ: Duyệt đồ thi sau 3 6 Mệnh đề: Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh 1 này phải liên thông, tức là có một đường đi nối chúng. bắt đầu từ đỉnh 1 4 Mệnh đề: Cho G=(V,E) là một đồ thị liên thông. Khi đó một đỉnh của G là điểm khớp khi và chỉ khi trong G tồn tại hai đỉnh u 7 5 và v sao cho mỗi đường đi nối u và v đều phải đi qua đỉnh này. 51 52 13
14. 29/09/2014 Duyệt đồ thị theo chiều sâu Duyệt đồ thị theo chiều sâu (DFS: Depth First Search) (DFS: Depth First Search) Duyệt theo chiều sâu 2 2 2 2 3 6 3 3 3 1 6 4 1 4 1 1 6 4 4 7 5 5 7 7 5 7 5 53 54 Duyệt đồ thị theo chiều sâu Duyệt đồ thị theo chiều sâu (DFS: Depth First Search) (DFS: Depth First Search) 2 2 2 3 6 3 3 6 1 4 1 1 4 4 7 5 5 7 5 7 55 56 14
15. 29/09/2014 Duyệt đồ thị theo chiều rộng Thuật toán duyệt đồ thị theo chiều (BFS: Breadth First Search) Procedure visited(u) Duyệt theo chiều rộng Begin visited[u]:=True; 2 for each vertex v adjacent to u do 2 if not vistited[v] then DFS(v); 3 3 End 6 1 4 1 Procedure DFS 6 4 begin for each vertex u in V do visited[u]=false; for each vertex u in V do 5 7 7 5 If not visited[u] then DFS(u); End 57 58 Duyệt đồ thị theo chiều rộng Thuật toán duyệt đồ thị theo chiều rộng (BFS: Breadth First Search) Procedure visit(u) Begin Queue:=; Duyệt theo chiều sâu Queue.push(u); visited[u]:=True; 2 While Queue<> do Begin v=Queue.pop(); 3 6 visit(v); 1 4 for each vertex w adjacent to v do If not visited[w] then 7 5 Begin Queue.push(w); visited[w]=true; End; End; 59 60 End; 15
16. 29/09/2014 Bài tập chương 01 Procedure BFS 1) Viết ma trận kề và mà trận liên thuộc của các đồ thị Begin sau: for each vertex u in V do visited[u]=false; for each vertex u in V do If not visited[u] then BFS(u); End H1 H2 H3 H4 61 62 Bài tập chương 01 Bài tập chương 01 2) Tìm số đỉnh của đồ thị vô hướng G. Biết: 5. Với các đồ thị vô hướng sau đây, tính bậc của từng a) G có 12 cạnh và mọi đỉnh đều có bậc là 2 đỉnh, chỉ ra các đỉnh treo, các đỉnh cô lập, sau đó tính b) G có 15 cạnh, 3 đỉnh bậc 4 và các đỉnh còn lại bậc 3. tổng bậc của tất cả các đỉnh, áp dụng định lý bắt tay tính số cạnh của từng đồ thị: c) G có 6 cạnh và mọi đỉnh đều có bậc bằng nhau. 3) Một đồ thị vô hướng G có 19 cạnh và mọi đỉnh đều có bậc >=3. G có tối đa bao nhiêu đỉnh? 4) Biết rằng mọi đỉnh của một đồ thị vô hướng G đều có bậc là một số lẻ p. Cmr, số cạnh của G là bội số của p 63 64 16
17. 29/09/2014 Bài tập chương 01 Bài tập chương 01 6. Với các đồ thị có hướng sau đây, tính nữa bậc trong, 6. Với các đồ thị có hướng sau đây, tính nữa bậc trong, nữa bậc ngoài của từng đỉnh, tính số cung của từng đồ nữa bậc ngoài của từng đỉnh, tính số cung của từng đồ thị: thị: 65 66 Bài tập chương 01 Bài tập chương 01 7. Các đồ thi sau đây, đồ thị nào là lưỡng phân 5) Cho G={V,E} đơn với V={v1,v2, ,vn} (n≥2) Và E = {(i,j), 1≤i,j≤n, i≠j, i+j chẵn} CMR: G không liên thông? xác định số thành phần liên thông 6) Có thể có 1 nhóm 9 người trong đó mỗi người chỉ quen biết đúng 5 người khác trong nhom hay không 7) CMR, một đồ thị liên thông có n đỉnh sẽ có ít nhất n-1 cạnh 8) CMR, trong mọi đồ thị đơn luôn tồn tại đường đi từ một đỉnh bậc lẻ tới một đỉnh bậc lẻ khác 67 68 17
18. 29/09/2014 Thực hành chương 1 Cài đặt đồ thị (vô hướng/ có hướng):  Sử dụng ma trận kề, ma trận liện thuộc để biểu diễn đồ thị  Các phương thức: Thêm một đỉnh Thêm một cạnh In ma trận kề/ma trận liện thuộc Duyệt đồ thị (theo DFS và BFS) Tính bậc của đỉnh Tìm một đường đi từ đỉnh x đến đỉnh y Kiểm tra tính liên thông của đồ thị Tìm các thành phần liên thông Kiểm tra đồ thị có phải là đồ thị con của một đồ thị khác 69 18