›
›

Bài giảng Lý thuyết đồ thị - Chương 1: Đại cương về đồ thị

ppt 47 trang ngocly 2830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 1: Đại cương về đồ 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:

  • pptbai_giang_ly_thuyet_do_thi_chuong_1_dai_cuong_ve_do_thi.ppt

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 1: Đại cương về đồ thị

  1. LÝ THUYẾT ĐỒ THỊ ntsonptnk@gmail.com
  2. NỘI DUNG 1. Đại cương về đồ thị 2. Cây 3. Các bài tốn đường đi 4. Đồ thị phẳng và bài tốn tơ màu đồ thị 5. Mạng và bài tốn luồng trên mạng, bài tốn cặp ghép GV: Dương Anh Đức 2
  3. TÀI LIỆU THAM KHẢO 1. Giáo trình Lý Thuyết Đồ Thị - Dương Anh Đức, Trần Đan Thư 2. Tốn rời rạc – Nguyễn Tơ Thành, Nguyễn Đức Nghĩa 3. GV: Dương Anh Đức 3
  4. ĐẠI CƯƠNG VỀ ĐỒ THỊ
  5. ĐỊNH NGHĨA Một đồ thị cĩ hướng G=(X, U) được định nghĩa bởi: Tập hợp X  được gọi là tập các đỉnh của đồ thị; Tập hợp U là tập các cạnh của đồ thị; Mỗi cạnh u U được liên kết với một cặp đỉnh (i, j) X2. GV: Dương Anh Đức 5
  6. ĐỊNH NGHĨA Một đồ thị vơ hướng G=(X, E) được định nghĩa bởi: Tập hợp X  được gọi là tập các đỉnh của đồ thị; Tập hợp E là tập các cạnh của đồ thị; Mỗi cạnh e E được liên kết với một cặp đỉnh {i, j} X2, khơng phân biệt thứ tự GV: Dương Anh Đức 6
  7. ĐỒ THỊ HỮU HẠN Đồ thị cĩ tập đỉnh và tập cạnh hữu hạn được gọi là ĐỒ THỊ HỮU HẠN Học phần này chỉ làm việc các ĐỒ THỊ HỮU HẠN, tuy nhiên để ngắn gọn chúng ta chỉ dùng thuật ngữ ĐỒ THỊ và hiểu ngầm đĩ là đồ thị hữu hạn. GV: Dương Anh Đức 7
  8. ĐỈNH KỀ Trên đồ thị cĩ hướng, xét cạnh u được liên kết với cặp đỉnh (i, j): Cạnh u kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh u); cĩ thể viết tắt u=(i, j). Cạnh u đi ra khỏi đỉnh i và đi vào đỉnh j Đỉnh j được gọi là đỉnh kề của đỉnh i GV: Dương Anh Đức 8
  9. ĐỈNH KỀ Trên đồ thị vơ hướng, xét cạnh e được liên kết với cặp đỉnh (i, j): Cạnh e kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề với cạnh e); cĩ thể viết tắt e=(i, j). Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau (hay đỉnh i kề với đỉnh j và ngược lại, đỉnh j kề với đỉnh i) GV: Dương Anh Đức 9
  10. MỘT SỐ KHÁI NIỆM Cạnh song song Khuyên Đỉnh treo Đỉnh cơ lập GV: Dương Anh Đức 10
  11. CÁC DẠNG ĐỒ THỊ Đồ thị RỖNG: tập cạnh là tập rỗng Đồ thị ĐƠN: khơng cĩ khuyên A B và cạnh song song Đồ thị ĐỦ: đồ thị vơ hướng, đơn, giữa hai đỉnh bất kỳ đều cĩ C đúng một cạnh. Đồ thị đủ N đỉnh ký hiệu là KN. KN cĩ N(N-1)/2 cạnh. GV: Dương Anh Đức 11
  12. CÁC DẠNG ĐỒ THỊ Đồ thị LƯỠNG PHÂN: đồ thị G=(X, E) được gọi là đồ thị lưỡng phân nếu tập X được A chia thành hai tập X và X thỏa: 1 2 D X1 và X2 phân hoạch X; B Cạnh chỉ nối giữa X1 và X2. Đồ thị LƯỠNG PHÂN ĐỦ: là đồ E thị lưỡng phân đơn, vơ hướng C thỏa với (i, j)/i X1 và j X2 cĩ đúng một cạnh i và j. X1=N và X2=M, ký hiệu KM, N. GV: Dương Anh Đức 12
  13. VÍ DỤ: ĐỒ THỊ ĐỦ K4 K4 K3 K2  K1, 1 K3, 3 K2, 3 GV: Dương Anh Đức 13
  14. BẬC CỦA ĐỈNH Xét đồ thị vơ hướng G Bậc của đỉnh x trong đồ thị G là số các cạnh kề với đỉnh x, mỗi khuyên được tính hai lần, ký hiệu là dG(x) (hay d(x) nếu đang xét một đồ thị nào đĩ). GV: Dương Anh Đức 14
  15. BẬC CỦA ĐỒ THỊ Xét đồ thị cĩ hướng G Nửa bậc ngồi của đỉnh x là số các cạnh đi ra khỏi đỉnh x, ký hiệu d+(x). Nửa bậc trong của đỉnh x là số các cạnh đi vào đỉnh x, ký hiệu d-(x). Bậc của đỉnh x: d(x)=d+(x)+d-(x) GV: Dương Anh Đức 15
  16. BẬC CỦA ĐỈNH Đỉnh TREO là đỉnh cĩ bậc bằng 1. A B Đỉnh CƠ LẬP là đỉnh cĩ bậc bằng 0. D C GV: Dương Anh Đức 16
  17. MỐI LIÊN HỆ BẬC - SỐ CẠNH Định lý: Xét đồ thị cĩ hướng G=(X, U). Ta cĩ: d+ (x) = d− (x) và d(x) = 2 U x X x X x X Xét đồ thị vơ hướng G=(X, E). Ta cĩ: d(x) = 2 E x X Hệ quả: số lượng các đỉnh cĩ bậc lẻ trong một đồ thị là một số chẳn. GV: Dương Anh Đức 17
  18. ĐẲNG CẤU ĐỒ THỊ 1 u1 2 Hai đồ thị vơ hướng G =(X , 1 1 u5 u4 E1) và G2=(X2, E2) được gọi là u2 đẳng cấu với nhau nếu tồn tại G1 hai song ánh  và  thỏa mãn u3 4 điều kiện: 3 u6 : X1 → X2 và : E1 → E2 a Nếu cạnh e E1 kề với cặp đỉnh {x, y}  X1 trong G1 thì e e cạnh (e) sẽ kề với cặp đỉnh G e1 4 2 {(x), (y)} trong G (sự 2 2 e6 tương ứng cạnh). d e5 b e3 c GV: Dương Anh Đức 18
  19. ĐẲNG CẤU ĐỒ THỊ Hai đồ thị cĩ hướng G1=(X1, 1 U1) và G2=(X2, U2) được gọi là G3 đẳng cấu với nhau nếu tồn tại hai song ánh  và  thỏa mãn 2 3 điều kiện: 1 : X1 → X2 và : U1 → U2 G4 Nếu cạnh u U1 liên kết với cặp đỉnh (x, y) X1 trong G1 thì 3 cạnh (u) sẽ liên kết với cặp đỉnh ((x), (y)) trong G2 (sự tương ứng cạnh). 2 GV: Dương Anh Đức 19
  20. ĐỒ THỊ CON Xét hai đồ thị G=(X, U) và G1=(X1, U1). G1 được gọi là đồ thị con của G và ký hiệu G1 G nếu: X1  X; U1  U u=(i, j) U của G, nếu u U1 thì i, j X1 1 1 u1 2 u1 2 u5 u u2 u u2 4 3 G G1 u 3 4 4 3 u6 GV: Dương Anh Đức 20
  21. ĐỒ THỊ BỘ PHẬN Đồ thị con G1=(X1, U1) của đồ thị G=(X, U) được gọi là đồ thị bộ phận của G nếu X=X1. 1 1 u1 2 u1 2 u 5 u u u2 4 u2 4 G G1 u u 3 4 3 4 3 3 u6 GV: Dương Anh Đức 21
  22. ĐỒ THỊ CON SINH BỞI TẬP ĐỈNH Cho đồ thị G=(X, U) và A  X. Đồ thị con sinh bởi tập đỉnh A, ký hiệu (A, V), trong đĩ: (i) tập cạnh V  U (ii) Gọi u=(i, j) U là một cạnh của G, nếu i, j A thì u V 1 1 u1 2 u1 2 u5 u u2 u u2 4 3 G u 3 4 4 3 A={1, 2, 4} u6 GV: Dương Anh Đức 22
  23. DÂY CHUYỀN, CHU TRÌNH Một dây chuyền trong G=(X, U) là một đồ thị con C=(V, E) của G với: V = {x1, x2, , xM} E = {u1, u2, , uM-1} với u1=x1x2, u2=x2x3, , uM-1=xM- 1xM; liên kết xixi+1 khơng phân biệt thứ tự. Khi đĩ, x1 và xM được nối với nhau bằng dây chuyền C. x1 là đỉnh đầu và xM là đỉnh cuối của C. Số cạnh của C được gọi là độ dài của C. Khi các cạnh hồn tồn xác định bởi cặp đỉnh kề, dây chuyền cĩ thể viết gọn (x1, x2, , xM) GV: Dương Anh Đức 23
  24. DÂY CHUYỀN, CHU TRÌNH Dây chuyền SƠ CẤP: dây chuyền khơng cĩ đỉnh lặp lại. CHU TRÌNH: là một dây chuyền cĩ đỉnh đầu và đỉnh cuối trùng nhau. GV: Dương Anh Đức 24
  25. ĐƯỜNG ĐI, MẠCH Một ĐƯỜNG ĐI trong G=(X, U) là một đồ thị con P=(V, E) của G với: V = {x1, x2, , xM} E = {u1, u2, , uM-1} với u1=x1x2, u2=x2x3, , uM-1=xM- 1xM; liên kết xixi+1 theo đúng thứ tự. Khi đĩ, cĩ đường đi P nối từ x1 đến xM. x1 là đỉnh đầu và xM là đỉnh cuối của P. Số cạnh của P được gọi là độ dài của P. Khi các cạnh hồn tồn xác định bởi cặp đỉnh kề, đường đi cĩ thể viết gọn (x1, x2, , xM) GV: Dương Anh Đức 25
  26. ĐƯỜNG ĐI, MẠCH Đường đi SƠ CẤP: đường đi khơng cĩ đỉnh lặp lại. MẠCH: là một đường đi cĩ đỉnh đầu trùng với đỉnh cuối Với đồ thị vơ hướng: Dây chuyền  đường đi, chu trình  mạch. Do đĩ, thuật ngữ đường đi cũng được dùng cho đồ thị vơ hướng. Mạch trong đồ thị cĩ hướng cịn được gọi là “chu trình cĩ hướng”. Đường đi trong đồ thị cĩ hướng cũng được gọi là “đường đi cĩ hướng” để nhấn mạnh. GV: Dương Anh Đức 26
  27. THÀNH PHẦN LIÊN THƠNG Cho đồ thị G=(X, U). Ta định nghĩa một quan hệ LIÊN KẾT  như sau trên tập đỉnh X: i, j X, i  j (ij hoặc cĩ dây chuyền nối i với j). Quan hệ nầy cĩ ba tính chất: phản xạ, đối xứng và bắc cầu nên nĩ là một quan hệ tương đương. Do đĩ tập X được phân hoạch thành các lớp tương đương. GV: Dương Anh Đức 27
  28. THÀNH PHẦN LIÊN THƠNG Định nghĩa: Một thành phần liên thơng của đồ thị là một lớp tương đương được xác định bởi quan hệ LIÊN KẾT ; Số thành phần liên thơng của đồ thị là số lượng các lớp tương đương; Đồ thị liên thơng là đồ thị chỉ cĩ một thành phần liên thơng. Khi một đồ G gồm p thành phần liên thơng G1, G2, , Gp thì các đồ thị Gi cũng là các đồ thị con của G và dG(x) = dGi(x), x của Gi. Lý thuyết đồ thị - Nguyễn Thanh Sơn 28
  29. THÀNH PHẦN LIÊN THƠNG G gồm 2 thành phần liên thơng, H là đồ thị liên thơng G H GV: Dương Anh Đức 29
  30. THÀNH PHẦN LIÊN THƠNG Thuật tốn xác định các thành phần liên thơng Input: đồ thị G=(X, E), tập X gồm N đỉnh 1, 2, , N Output: các đỉnh của G được gán nhãn là số hiệu của thành phần liên thơng tương ứng 1.Khởi tạo biến label=0 và gắn nhãn 0 cho tất cả các đỉnh 2.Duyệt qua tất cả các đỉnh i X Nếu nhãn của i là 0 1. label = label + 1 2. Gán nhãn cho tất cả các đỉnh cùng thuộc thành phần liên thơng với i là label GV: Dương Anh Đức 30
  31. THÀNH PHẦN LIÊN THƠNG Thuật tốn gán nhãn các đỉnh cùng thuộc thành phần liên thơng với đỉnh i – Visit(i, label) Input: đồ thị G=(X, E), đỉnh i, nhãn label Output: các đỉnh cùng thuộc thành phần liên thơng với i được gắn nhãn label 1. Gắn nhãn label cho đỉnh i 2. Duyệt qua tất cả các đỉnh j X và cĩ cạnh nối với i Nếu nhãn của j là 0 Visit(j, label) GV: Dương Anh Đức 31
  32. BIỂU DIỄN ĐỒ THỊ BẰNG HÌNH VẼ A A e u e1 4 u1 4 e2 u2 e D u D B 3 B 3 e u e 6 u 6 5 5 C C G H Lý thuyết đồ thị - Nguyễn Thanh Sơn 32
  33. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ma trận KỀ: Xét đồ thị G=(X, U), giả sử tập X gồm N đỉnh và được sắp thứ tự X={x1, x2, , xN}, tập U gồm M cạnh và được sắp thứ tự U={u1, u2, , uM}. Ma trận kề của đồ thị G, ký hiệu B(G), là một ma trận nhị phân cấp NxN B=(Bij) với Bij được định nghĩa: Bij=1 nếu cĩ cạnh nối xi tới xj, Bij=0 trong trường hợp ngược lại. Lý thuyết đồ thị - Nguyễn Thanh Sơn 33
  34. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ 1 0 0 1 0 1 0 0 0 4 B = 2 0 1 0 1 3 1 0 0 0 G Lý thuyết đồ thị - Nguyễn Thanh Sơn 34
  35. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ 1 0 1 1 1 1 0 1 0 4 B = 2 1 1 0 1 3 1 0 1 0 G Lý thuyết đồ thị - Nguyễn Thanh Sơn 35
  36. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ma trận LIÊN THUỘC của đồ thị vơ hướng: Xét đồ thị G=(X, U) vơ hướng, giả sử tập X gồm N đỉnh và được sắp thứ tự X={x1, x2, , xN}, tập U gồm M cạnh và được sắp thứ tự U={u1, u2, , uM}. Ma trận liên thuộc (hay liên kết đỉnh cạnh) của G, ký hiệu A(G), là ma trận nhị phân cấp NxM A=(Aij) với Aij được định nghĩa: Aij=1 nếu đỉnh xi kề với cạnh uj, Aij=0 nếu ngược lại. Lý thuyết đồ thị - Nguyễn Thanh Sơn 36
  37. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN LIÊN THUỘC 1 1 1 1 1 0 0 e e4 1 1 1 0 0 1 0 e2 e 4 A = 2 3 0 0 1 0 1 1 e6 e5 3 0 0 0 1 0 1 G Lý thuyết đồ thị - Nguyễn Thanh Sơn 37
  38. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN Ma trận LIÊN THUỘC của đồ thị cĩ hướng: Xét đồ thị G=(X, U) cĩ hướng, giả sử tập X gồm N đỉnh và được sắp thứ tự X={x1, x2, , xN}, tập U gồm M cạnh và được sắp thứ tự U={u1, u2, , uM}. Ma trận liên thuộc (hay liên kết đỉnh cạnh) của G, ký hiệu A(G), là ma trận nhị phân cấp NxM A=(Aij) với Aij được định nghĩa: Aij=1 nếu cạnh uj đi ra khỏi đỉnh xi, Aij=-1 nếu cạnh uj đi vào đỉnh xi, Aij=0 trong các trường hợp khác. Lý thuyết đồ thị - Nguyễn Thanh Sơn 38
  39. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN LIÊN THUỘC 1 u u4 −1 −1 1 −1 0 0 1 u2 1 1 0 0 −1 0 u3 4 A = 2 0 0 −1 0 1 1 u u 6 5 0 0 0 1 0 −1 3 G Lý thuyết đồ thị - Nguyễn Thanh Sơn 39
  40. BIỂU DIỄN ĐỒ THỊ BẰNG NNLT C++ #define MAX 100 class Graph { protected: int nVertex; //số đỉnh của đồ thị, các đỉnh được //đánh số từ 0 int labels[MAX]; //nhãn của các đỉnh int degrees[MAX]; //bậc các đỉnh unsigned char B[MAX][MAX]; //ma trận kề void Visit(int i, int label); public: void GetData(const char *filename); int FindConnected(); } Lý thuyết đồ thị - Nguyễn Thanh Sơn 40
  41. Source code: nhập dữ liệu từ textfile void Graph::GetData(const char *filename) { //nhập dữ liệu từ tập tin văn bản ifstream fin; fin.open(filename); fin >> nVertex; for (int i = 0; i > B[i][j]; fin.close(); } Lý thuyết đồ thị - Nguyễn Thanh Sơn 41
  42. Source code: xác định bậc của đỉnh void Graph::CountDegree() { //xác định bậc của các đỉnh, đồ thị vơ hướng for(int i=0;i<nVertex; i++) for(degrees[i]=0, int j=0; j<nVertex; j++) degrees[i] += B[i][j]; } Lý thuyết đồ thị - Nguyễn Thanh Sơn 42
  43. Source code: gán nhãn 1 TPLT void Graph::Visit(int i, int label) { labels[i] = label; for (int j=0; j<N; j++) if((labels[j]==0)&&(B[i][j]||B[j][i]) Visit(j, label); } Lý thuyết đồ thị - Nguyễn Thanh Sơn 43
  44. Source code: gán nhãn tất cả TPLT int Graph::FindConnected() { int i, label; for (int i=0; i<N; i++) labels[i] = 0; label = 0; for (int i=0; i<N; i++) if (labels[i]==0) { label ++; Visit(j, label) } return label; //số thành phần liên thơng } Lý thuyết đồ thị - Nguyễn Thanh Sơn 44
  45. BÀI TẬP 1. G là một đồ thị đơn, vơ hướng cĩ số đỉnh N>3. Chứng minh G cĩ chứa 2 đỉnh cùng bậc. 2. Đồ thị G cĩ đúng 2 đỉnh bậc lẻ. Chứng minh tồn tại một dây chuyền nối hai đỉnh đĩ với nhau. 3. Xét đồ thị G đơn, vơ hướng gồm N đỉnh, M cạnh và P thành phần liên thơng. a. Chứng minh: M (N-P)(N-P+1)/2, suy ra nếu M > (N-1)(N-2)/2 thì G liên thơng. a. Một đồ thị đơn cĩ 10 đỉnh, 37 cạnh thì cĩ chắc liên thơng hay khơng? GV: Dương Anh Đức 45
  46. BÀI TẬP 4. Đồ thị G đơn, vơ hướng gồm N đỉnh và d(x) (N-1)/2 với mọi đỉnh x. Chứng minh G liên thơng. 5. Đồ thị vơ hướng G liên thơng gồm N đỉnh. Chứng minh số cạnh của G N-1. 6. Xét đồ thị G vơ hướng đơn. Gọi x là đỉnh cĩ bậc nhỏ nhất của G. Giả sử d(x) k 2 với k nguyên dương. Chứng minh G chứa một chu trình sơ cấp cĩ chiều dài lớn hơn hay bằng k+1. GV: Dương Anh Đức 46
  47. BÀI TẬP 7. Cho G là đồ thị vơ hướng liên thơng. Giả sử C1 và C2 là 2 dây chuyền sơ cấp trong G cĩ số cạnh nhiều nhất. Chứng minh C1 và C2 cĩ đỉnh chung. 8. G là đồ thị vơ hướng khơng khuyên và d(x) 3 với mọi đỉnh x. Chứng minh G cĩ chứa chu trình với số cạnh chẵn. GV: Dương Anh Đức 47