Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm về đồ thị - Nguyễn Tuấn Anh

Đồ thị hữu hạn có hướngabedc1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ631452Hình 3: Đa đồ thịĐa đố thị là G = (V, E), tập đỉnh V, E là tập các cặp không có thứ tự gồm 2 phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1, e2 được gọi là cạnh lặp nếu chúng cùng tương ứng một cặp đỉnhĐịnh nghĩa 2.1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ71.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊĐơn đồ thị có thể là đa đồ thị ngược lại có thể không.Đồ thị có đỉnh có khuyên -> Giả đồ thị vô hướngCDFEAHình 4: Giả đồ thị vô hướng81.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊGiả đồ thị vô hướngG(V,E); E là tập các cặp không có thứ tự gồm 2 phần tử(không nhất thiết phải khác nhau) của V gọi là cạnh.Cạnh e được gọi là khuyên nếu e = (u,u);CDFEAHình 4: Giả đồ thị vô hướng91.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊCDFEAHình 4: Đồ thị có hướngĐồ thị có hướng:G(V,E); E là tập các cặp có thứ tự gồm 2 phần khác nhau của V, được gọi là các cung.10ĐƠN VÀ ĐA ĐỒ THỊ 	- Đồ thị G = (V, E) mà mỗi cặp đỉnh được nối với nhau không quá một cạnh được gọi là đơn đồ thị (gọi tắt là đồ thị). 	- Đồ thị có những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được gọi là đa đồ thị.1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ111.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊCác phần sau sẽ nghiên cứu:Đồ thị vô hướngĐồ thị có hướng121.2. CÁC THUẬT NGỮ CƠ BẢNĐỉnh kề:Nếu hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu tồn tại cạnh (u,v) của đồ thị. Ta nói cạnh (u,v) là liên thuộc với 2 đỉnh u, v.u là đỉnh đầu, v là đỉnh cuối.31452Hình 5. Đồ thị vô hướng13Danh sách liền kề - Adjacency ListsMột bảng với mỗi hàng cho một đỉnh và liệt kê các đỉnh kề với nó.abdcfe1.2. CÁC THUẬT NGỮ CƠ BẢN141.2. CÁC THUẬT NGỮ CƠ BẢNBậc của đỉnh : deg(v);Bậc của đỉnh v là số đỉnh liền kề với nó (số cạnh liên thuộc với v)Deg(1)=3Deg(3)=2,Bậc 0 là đỉnh cô lập, bậc 1 là đỉnh treo.31452Hình 5. Đồ thị vô hướng151.2. CÁC THUẬT NGỮ CƠ BẢNĐịnh lý 1.Giả sử G=(V,E) vô hướng có m cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng 2 lần số cung.Chứng minh: Với mỗi cạnh ta tính bậc của đỉnh đầu u và đỉnh cuối vDo đó tổng số bậc của 1 cạnh là deg(u)+deg(v) suy ra tổng số bậc của cả đồ thị là m *2.Hệ quả:Trong đồ thị vô hướng, số đỉnh có bậc là 1 số lẻ( đỉnh bậc lẻ) là số chẵn.31452Hình 5. Đồ thị vô hướng16Bán bậc ra và bán bậc vào của đỉnh vBán bậc ra là số cung đi ra từ v : deg+(v)Bán bậc vào là số cung đi vào đỉnh v : deg-(v)1.2. CÁC THUẬT NGỮ CƠ BẢNCDFEAHình 5. Đồ thị có hướng171.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGĐịnh nghĩa 1. Cho G = (V, E) là một đồ thị vô hướng:Đường đi độ dài n từ đỉnh u đến đỉnh v (với n>0) là: 	x0, x1,, xi, xi+1,, xn-1, xnTrong đó u= x0 , v=xn, (xi, xi+1)  E, i=0,1,2..n-1	Ta có : x0, x1,, xi, xi+1,, xn-1, xn 	có thể được viết như sau:	(x0, x1), (x1, x2),,, (xn-1, xn)	Đỉnh u được gọi là đỉnh đầu, v đỉnh cuối.18 Độ dài của đường đi: là số cạnh của đường đi đó.Đường đi đơn: Các đỉnh trên nó khác nhau từng đôi một.1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG19Chu trình là một đường đi khép kín (đỉnh cuối 	 trùng với đỉnh đầu của đường). [x1, x2,, xi, xi+1,, xk-1, xk] 	 	trong đó x1 = xk.	- Ký hiệu: n là số đỉnh, m là số cạnh của một đồ thị.	Chu trình đơn: là chu trình mà các đỉnh trên nó khác nhau từng đôi(không có cạnh nào lặp lại).1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGa, d, c, f, e cdabefa, d, c, f, e, a d, e, c, a20 1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGĐồ thị liên thông:	Đồ thị G là liên thông nếu tìm được đường đi giữa 2 đỉnh bất kỳ.abdcefgĐồ thị G liên thông12345Đồ thị Không liên thông211.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGĐồ thị con Giả sử G = (V, E) là một đồ thị. - Đồ thị H = (W, F) được gọi là đồ thị con của đồ thị G nếu:	 W  V và F  EcdabefG=({a,b,c,d,e,f}, {	(a,b),(a,d),(a,e),(b,c),	(b,e),(b,f), (c,d),(c,f) } )H=({a,d,e}, {	(a,d),(a,e)(d,e) } )221.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG Thành phần liên thông của đồ thị- Khi đồ thị không liên thông thì nó sẽ có các đồ thị con liên thông thì ta gọi các đồ thị con này là các thành phần liên thông của đồ thị12645Đồ thị Không liên thông3231.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGĐỉnh rẽ nhánhNếu ta loại bỏ đỉnh v và các cung đi từ v thì sẽ làm tăng số thành phần liên thông, đỉnh v đó gọi là đỉnh rẽ nhánh. abdcefgĐỉnh d và e là đỉnh rẽ nhánh241.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGĐỉnh rẽ nhánhNếu ta loại bỏ đỉnh v và các cung đi từ v thì sẽ làm tăng số thành phần liên thông, đỉnh v đó gọi là đỉnh rẽ nhánh. abcfgĐỉnh d và e là đỉnh rẽ nhánh251.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGCạnh cầuNếu cạnh e mà bị loại bỏ khỏi đồ thị mà làm tăng số thành phần liên thông thì e được gọi là cạnh cầuabdcefgCạnh (d,f) và (e,g) là các cạnh cầu261.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGĐồ thị liên thông mạnh:Đồ thị có hướng G=(V,A) được gọi là liên thông mạnh nếu luôn luôn tìm được đường đi giữa hai đỉnh bất kỳ.cabdeĐồ thị G liên thông mạnhcabdeĐồ thị H liên thông yếu27Đồ thị định hướng:Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh của nó nằm trên ít nhất một chu trình1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNGa) Đồ thị định hướng 	 b) Đồ thị không định hướng5432154321281.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTĐồ thị đầy đủ:	Đồ thị đầy đủ có n đỉnh(ký hiệu là Kn) là đồ thị vô hướng mà 2 đỉnh bất kỳ của nó có cạnh nối.K3K4K5Đồ thị đầy đủ có n đỉnh thì có n(n-1) / 2 cạnh291.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTĐồ thị vòng:	Đồ thị vòng Cn, n3, gồm n đỉnh V1, V2,..,Vn và các cạnh (V1,V2).(V2,V3),,(Vn-1,Vn), (Vn,V1). C3C4C5Các đồ thị vòngV3V2V1V2V3V4V1V4V5V3V2V1301.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTĐồ thị bánh xe:	Đồ thị bánh xe Wn thu được từ Cn bằng cách bổ sung vào một số đỉnh nối với tất cả các đỉnh của Cn.W4W5Các đồ thị bánh xeV3V2V1V2V3V4V1V4V5311.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTĐồ thị lập phương:	Đồ thị lập phương có n đỉnh Qn là đồ thị với các đỉnh biểu diễn 2n xâu nhị phân đọ dài n. 	Hai đỉnh của nó gọi là kề nhau nếu như hai xâu nhị phân tương ứng chỉ khác nhau 1 bit.Q1Q2Các đồ thị lập phương0101101001010011001000100110111101Q3321.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTĐồ thị hai phía:	Đồ thị G = (V,E) được gọi là đồ thị 2 phía nếu tập V phân hoạch thành X và Y sao cho mỗi cạnh của đồ thị chỉ nối được 1 đỉnh nào đó trong X với 1 đỉnh nào đó trong Y. 	G= (XY, E).Đơn đồ thị là đồ thị hai phía(định lý)	Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ.Đồ thị hai phía K2,312345331.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆTĐồ thị phẳng:	Đồ thị G = (V,E) được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các canhjh của nó không cắt nhau ngoài ở đỉnh. (Biểu diễn phẳng của đồ thị)Đồ thị phẳngV3V2V1V4V3V4V1V2341.5. BIỂU DIỄN ĐỒ THỊ TRONG MÁY TÍNHĐồ thị có trọng số (weighted graph). DECAB100Km98Km250km60km170km55km54321Đồ thị không có trọng số: 35Biểu diễn bằng ma trận kề Biểu diễn bằng danh sách kềDanh sách cạnh1.5. BIỂU DIỄN ĐỒ THỊ TRONG MÁY TÍNH361.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)Xét một đồ thị G (V, E) định hướng với V gồm có n đỉnh (n >= 1) mà giả sử các đỉnh đã được đánh số theo một quy định nào đó. Ma trận kề A biểu diễn G là một ma trận vuông kích thước n×n. Các phần tử của ma trận có giá trị 0 hoặc 1. Nếu phần tử aịj=1 thì điều đó có nghĩa là tồn tại mọt cung định hướng (vi, vj) trong E; còn aij=0 thì không tồn tại cung như vậy.371.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)A=0 1 2 3 4 5 6 7 0123456738Rõ ràng với đồ thị không định hướng thì ma trận kề biểu diễn nó có các phần tử đối xứng qua đường chéo chính, nghĩa là có phần tử bằng 1 ở hàng i cột j thì cũng có phần tử 1 ở hàng j cột i. Còn đồ thị định hướng thì không phải như vậy.1.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)391.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)401.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)41012111000022101110100210out-degree =in-degree = dj1.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)421.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)431.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)54312100Km98Km250km60km170km55kmA= 234511234501006010009855170980250550601702500441.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)45Đối với đồ thị có trọng số thì ma trận kề có thể lập bằng cách thay giá trị 1 bởi trọng số tương ứng của các cung.Ta cũng thấy ngay không gian nhớ cần cho cách biểu diễn này là các bit (với đồ thị không định hướng thì có thể giảm bớt một nửa bằng cách chỉ lưu trữ phần trên (hoặc dưới), đường chéo chính bằng một ma trận tam giác). Trong trường hợp mà đồ thị có ít cung (ma trận kề chứa nhiều phần tử 0), thì ta thấy ngay nhược điểm của cách biểu diễn này. Điều đó sẽ khắc phục trong cách biểu diễn tiếp theo.Nhận xét461.5.2. Biểu diễn bằng danh sách kề[0][1][2][3]1230230130120123471.5.2. Biểu diễn bằng danh sách kềTrong cách biểu diễn này, n hàng của ma trận kề được thay bởi n danh sách móc nối.Với mỗi đỉnh của G có một danh sách tương ứng. Các nút trong danh sách thứ i biểu diễn các đỉnh lân cận của nút i. Mỗi nút có hai trường tên đỉnh và trường liên kết.[0][1][2][3]12023013120123481.5.2. Biểu diễn bằng danh sách kề491.5.2. Biểu diễn bằng danh sách kề// Định nghĩa một đỉnh (Node)typedef struct Node{	Data info; //Mô tả đỉnh : số thứ tự 	đỉnh,hoặc tên đỉnh	Node * Next ;};// Khai báo mảng các danh sách liên kết	G	Node *G[MAX]; 	Đây là mảng cong trỏ các đỉnh, mỗi đỉnh là một nút con trỏ.502.3.Danh sách cạnh(đồ thị không có trọng số)1234	Đầu Cuối cạnh 1:	 1	 2 cạnh 2: 1 3 cạnh 3: 2 4 cạnh 2: 3 4Dùng một mảng các cạnh để lưu trữMỗi cạnh là 1 bản ghi gồm có đỉnh đầu và đỉnh cuối512.3.Danh sách cạnh(đồ thị không có trọng số)typedef struct Canh{int dau, cuoi;};Canh DC[MAX]; // mảng DC để lưu danh sách cạnhChúng ta cũng có thể sử dụng ds liên kết để lưu các cạnh của đồ thịNếu đồ thị có trọng số thì ta thêm vào Canh thành phần trọng số.522.3.Danh sách cạnh(đồ thị có trọng số)	 Đầu Cuối trọng sốcạnh 1: 1	 2	1cạnh 2: 1 3	3cạnh 3: 1 6	2cạnh 4: 2 3	5 cạnh 5: 2 4	1 cạnh 6: 3 4	2 cạnh 7: 3 5	1 cạnh 8: 4 5	4 cạnh 9: 5 6	5532.3.Danh sách cạnh(đồ thị có trọng số)typedef struct Canh{	int d,c; // d: dinh dau , c: dinh cuoi	int trongso;};Canh DC[100]; // danh sách cạnh có trọng số54