Nội dung

Lý thuyết đồ thị Chương 1: Giới thiệu 1 Chương 1: Giới thiệu  Định nghĩa: Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp các đỉnh (vertices) V (VØ) và các cạnh (edges) E. Mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh liên kết hay kề (adjacent) với nhau và e được gọi là tới các đỉnh v, w. Ký hiệu hay v w. e vw e 2 Chương 1: Giới thiệu A   Các đỉnh: A, B, C, D Các cạnh: AB, AC, AD, BD, BC B D C Cạnh không phân biệt thứ tự của đỉnh được gọi là cạnh vô hướng. Đồ thị bao gồm các cạnh vô hướng được gọi là đồ thị vô hướng. 3 Chương 1: Giới thiệu  - Định nghĩa: Cạnh uv tương ứng với 2 đỉnh trùng nhau gọi là vòng (loop) hay khuyên. B A C 4 Chương 1: Giới thiệu - Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh gọi là 2 cạnh song song (parallel edge). B A C 5 Chương 1: Giới thiệu - Đồ thị không có cạnh song song và khuyên được gọi là đơn đồ thị (simple graph), ngược lại là đa đồ thị (multi graph). B A A B C C D 6 Chương 1: Giới thiệu - Đồ thị G’ = (V’, E’) gọi là 1 đồ thị con (sub graph) của đồ thị G = (V, E) nếu V’  V và E’  E. A A’ E B D C E’ B’ C’ 7 Chương 1: Giới thiệu - Đồ thị có số đỉnh và số cạnh hữu hạn gọi là đồ thị hữu hạn (finite graph), ngược lại là đồ thị vô hạn (infinite graph). 8 Chương 1: Giới thiệu  A D Biểu đồ A’ B C B’ A” C’ E’ D’ C” B” 9 Chương 1: Giới thiệu  - - - - Bậc của một đỉnh Bậc (degree) của một đỉnh v, ký hiệu là d(v), chính là số cạnh tới đỉnh đó. Mỗi vòng tại một đỉnh sẽ được xem như 2 cạnh tới đỉnh đó. Nếu d(v) = 0, v được gọi là đỉnh cô lập (isolated vertex). Nếu d(v) = 1, v được gọi là đỉnh treo (perdant vertex), cạnh tới đỉnh treo được gọi là cạnh treo (perdant edge). Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi là đồ thị rỗng (null graph). 10 Chương 1: Giới thiệu A B C G F D E Y X G’ Z Bậc của các đỉnh: A: 2 B: 5 C: 0 (đỉnh cô lập) D: 2 E: 1 (đỉnh treo) F: 4  T 11 Chương 1: Giới thiệu - Đồ thị mà mọi cặp đỉnh đều kề nhau được gọi là đồ thị đầy đủ (complete graph). Đồ thị đầy đủ có n đỉnh được ký hiệu là Kn. A E B D C 12 Chương 1: Giới thiệu - Đồ thị bù của một đồ thị G, ký hiệu là G, là một đồ thị có cùng đỉnh với G và có các cạnh là những cạnh mà ta phải bổ sung vàođể G trở thành đầy đủ. G G 13 Chương 1: Giới thiệu  Định lý 1.1: Với mọi đồ thị G = (V, E), ta có:  d (v )  2 E vV   Hệ quả 1.1: Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ thị là 1 số chẵn Hệ quả 1.2: Mọi đồ thị đều có một số chẵn các đỉnh bậc lẻ. 14 Chương 1: Giới thiệu  Hệ quả 1.3: 1 Đồ thị Kn có n(n-1) cạnh. 2 15 Chương 1: Giới thiệu Biểu diễn đồ thị - Danh sách kề C ABBDE BAACDE CCCBD B DABCE EABD  A D E 16 Chương 1: Giới thiệu Biểu diễn đồ thị - Ma trận kề: A B C D E A 0 2 0 1 1 B 2 0 1 1 1 B C 0 1 2 1 0 D 1 1 1 0 1 E 1 1 0 1 0  C D A E 17 Chương 1: Giới thiệu  Định lý 1.2: Tổng các phần tử trên hàng (hoặc cột) thứ i của ma trận kề của đồ thị G có n đỉnh bằng bậc của đỉnh vi của đồ thị ấy, nghĩa là: n n k 1 k 1 d (vi )  mik  mki 18 Chương 1: Giới thiệu  Đường đi và chu trình Cho một đồ thị G. Một đường đi P trong G là một dãy các cạnh nối tiếp có chung đầu mút v0v1, v1v2,..., vk-1vk. Ký hiệu: P = v0 e1 v1 e2 ... ek vk hay P = v0v1...vk k (số cạnh tạo thành P) được gọi là chiều dài của P. Ký hiệu l(P) = k. 19 Chương 1: Giới thiệu  A  Đường đi P: EACB l(P) = 3 B E D C 20 Chương 1: Giới thiệu  Một chu trình (cycle) trong G là một đường đi trong G có dạng c=v0v1...vk-1v0 với l(c)  1.  Một đường đi (hoặc chu trình) được gọi là sơ cấp nếu nó không đi qua đỉnh nào quá một lần. Một đường đi (hoặc chu trình) được gọi là đơn giản nếu nó không đi qua cạnh nào quá một lần. 21 Chương 1: Giới thiệu  A  B E  D C  ABCA là một chu trình đơn giản và sơ cấp. ACB là một đường đi đơn giản và sơ cấp. EABCAD là một đường đi đơn giản nhưng không sơ cấp. EACBADE là một chu trình đơn giản nhưng không sơ cấp. 22 Chương 1: Giới thiệu  Liên thông Một đồ thị được gọi là liên thông (connected) nếu mọi cặp đỉnh của nó đều được nối với nhau bởi một đường đi. A B E D C 23 Chương 1: Giới thiệu  Xét G = (V, E) là một đồ thị vô hướng. Trên tập hợp V, ta định nghĩa một quan hệ ~ như sau: v, w V, v ~ w  có 1 đường đi trong G giữa v và w. Khi đó: ~ là một quan hệ tương đương trên V và ~ phân hoạch V thành các lớp tương đương. Mỗi lớp tương đương này ứng với một đồ thị con liên thông của G và được gọi là một thành phần liên thông (connected component) của G. 24 Chương 1: Giới thiệu  Hai thành phần liên thông bất kỳ của G thì tách biệt. H F A B I G C D E 25 Chương 1: Giới thiệu  Định lý 1.3: Một đơn đồ thị G có n đỉnh và k thành phần thì có tối đa là 1 (n – k)(n – k + 1) cạnh. 2 26 Chương 1: Giới thiệu  Đẳng hình Hai đồ thị G = (V, E) và G’ = (V’, E’) gọi là đẳng hình (isomorphic) với nhau nếu có 1 song ánh giữa hai tập hợp V, V’ và 1 song ánh giữa 2 tập hợp E, E’ sao cho nếu cạnh e = vw  E tương ứng với cạnh e’ = v’w’  E’ thì cặp đỉnh v, w  V cũng là tương ứng của cặp đỉnh v’, w’  V’. 27 Chương 1: Giới thiệu A’ A E B E’ B’ D’ D C C’ 28 Ví dụ: Hai đơn đồ thị G1 và G2 sau là đẳng cấu qua phép đẳng cấu f: a x, bu, cz, dv, ey: 29 Ví dụ:  Hai đồ thị G1 và G2 sau đều có 5 đỉnh và 6 cạnh nhưng không đẳng cấu vì trong G1 có một đỉnh bậc 4 mà trong G2 không có đỉnh bậc 4 nào. 30 Ví dụ:  Hai đồ thị G1 và G2 đều có 7 đỉnh, 10 cạnh, cùng có một đỉnh bậc 4, bốn đỉnh bậc 3 và hai đỉnh bậc 2. Tuy nhiên G1 và G2 là không đẳng cấu vì hai đỉnh bậc 2 của G1 (a và d) là không kề nhau, trong khi hai đỉnh bậc 2 của G2 (y và z) là kề nhau. 31 Ví dụ:  Hãy xác định xem hai đồ thị sau có đẳng cấu hay không? 32 Chương 1: Giới thiệu  - Đồ thị có hướng Nếu mỗi cạnh e  E của G được xác định bởi một cặp có thứ tự (v, w) của 2 định v, w  V thì ta nói e là 1 cạnh có hướng từ v đến w, ký hiệu e = vw, và đồ thị G khi này được gọi là một đồ thị có hướng (directed graph). v được gọi là đỉnh đầu (initial vertex). w được gọi là đỉnh cuối (terminal vertex). 33 Chương 1: Giới thiệu - - e được gọi là tới ngoài (incident out) đỉnh v và tới trong (incident in) đỉnh w. Số cạnh tới ngoài đỉnh v gọi là bậc ngoài (out degree) của v, ký hiệu dout(v); số cạnh tới trong đỉnh w gọi là bậc trong (in degree) của w, ký hiệu din(w). A B C E D 34 Chương 1: Giới thiệu  Một đồ thị có hướng gọi là cân bằng (balanced) nếu mọi đỉnh của nó đều có bậc trong và bậc ngoài bằng nhau. A B D E C 35 Chương 1: Giới thiệu   Đồ thị có hướng G gọi là liên thông nếu đồ thị vô hướng tương ứng của nó là liên thông. Một đường đi P trong một đồ thị có hướng G là một dãy hữu hạn các cạnh nối tiếp v0v1, v1v2, ..., vk-1vk. P còn được viết là: v0v1...vk. A B C E D 36 Chương 1: Giới thiệu  Một đồ thị có hướng G gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt v, w luôn luôn tồn tại 1 đường đi nối v với w. A B C E D 37 Chương 1: Giới thiệu  Một chu trình trong đồ thị có hướng G là một đường đi trong G có dạng v0v1...vkv0.  Đồ thị có hướng G gọi là đầy đủ nếu đồ thị vô hướng tương ứng của nó là đầy đủ. A B C E D 38 Chương 1: Giới thiệu   Định lý 1.4: Trong một đồ thị có hướng G, tổng các bậc trong và tổng các bậc ngoài của các đỉnh thì bằng nhau và cùng bằng số cạnh của G. Định lý 1.5: Tổng số các phần tử trên hàng (cột) thứ i của ma trận liên kết của đồ thị có hướng G bằng bậc ngoài (trong) của đỉnh vi, nghĩa là: n d out (vi )  mik k 1 và n d in (vi )  mki k 1 39 NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT Đơn đồ thị: 40 Đồ thị vòng 41 Đồ thị bánh xe: 42 Đồ thị lập phương 43 Đồ thị phân đôi 44 Một vài ứng dụng của các đồ thị đặc biệt Các mạng cục bộ (LAN): 45 Xử lý song song: 46 Chương 1: Giới thiệu  - - - Tóm tắt Đồ thị, các loại đồ thị (có hướng, vô hướng, đơn, đa, đầy đủ). Bậc của đỉnh, đồ thị cân bằng. Biểu diễn một đồ thị (danh sách kề, ma trận kề). Đẳng hình. Đường đi, chu trình. Miền liên thông, liên thông mạnh. 47 Định nghĩa:  Cho đồ thị vô hướng G=(V,E), v1, v2, ..., vn là các đỉnh và e1, e2, ...,  em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận  mij bằng 1 nếu cạnh ej nối với đỉnh vi và bằng 0 nếu cạnh ej không nối với đỉnh vi. 48 Ví dụ:  Ma trận liên thuộc theo thứ tự các đỉnh v1, v2, v3, v4, v5 và các cạnh e1, e2, e3,e4, e5, e6 là: 49 Định nghĩa:   Một đỉnh trong đồ thị G mà khi xoá đi nó và tất cả các cạnh liên thuộc với nó ta nhận được đồ thị con mới có nhiều thành phần liên thông hơn đồ thị G được gọi là đỉnh cắt hay điểm khớp. Việc xoá đỉnh cắt khỏi một đồ thị liên thông sẽ tạo ra một đồ thị con không liên thông. Hoàn toàn tương tự, một cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị có nhiều thành phần liên thông hơn so với đồ thị xuất phát được gọi là cạnh cắt hay là cầu. 50 Ví dụ:  Tìm đỉnh cắt (đỉnh khớp), cạnh cắt (cạnh cầu) 51 Bài tập  Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau 52 Bài tập 1. Nêu ý nghĩa của tổng các phần tử trên một hàng (t.ư. cột) của một ma trận liền kề đối với một đồ thị vô hướng ? Đối với đồ thị có hướng ? 53 Các đồ thị G và G’ sau có đẳng cấu với nhau không? 54 Bài tập  Tìm ma trận liền kề cho các đồ thị sau:  Một đồ thị bánh xe Wn có 36 cạnh. Tìm số đỉnh của đồ thị? Cho đồ thị G= (V,E) có 10 đỉnh, mỗi đỉnh có bậc bằng 6. Tìm số cạnh của đồ thị? Đồ thị nào có kích thước ma trận liên kề bằng ma trận liên thuộc.(vẽ hình minh họa)   55 Bài tập  Đồ thị vòng có phải là đồ thị phân đôi không? Giải thích, vẽ hình minh họa? 56  Cho biết tên gọi của đồ thị? 57  Vẽ đồ thị với ma trận liền kề dưới đây. 58  Vẽ đồ thị bù của đồ thị sau: 59