Bài giảng chương 4: Định nghĩa đồ thị

* Chương 4: ĐỒ THỊ * 4.1 Định nghĩa và thí dụ Định nghĩa: Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp: tập hợp các đỉnh V (vertices) với VØ và tập hợp các cạnh E (edges). 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ề với nhau và e được gọi là cạnh tới các đỉnh v, w. Ký hiệu hay v w. e * 4.1 Định nghĩa và thí dụ Các đỉnh: A, B, C, D Các cạnh: AB, AC, AD, BD, BC 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. * 4.1 Định nghĩa và thí dụ Đị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. * 4.1 Định nghĩa và thí dụ 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). * 4.1 Định nghĩa và thí dụ Đồ 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). * 4.1 Định nghĩa và thí dụ Đồ 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. B’ C’ * 4.1 Định nghĩa và thí dụ Đồ 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). * 4.2 Bậc của đỉnh 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. Nếu d(v) = 1, v được gọi là đỉnh treo, cạnh tới đỉnh treo được gọi là cạnh treo. Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi là đồ thị rỗng (null graph). * 4.2 Bậc của đỉnh 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 G G’ * 4.3 Một số đơn đồ thị Đồ 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. * 4.3 Một số đơn đồ thị Đồ 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 * 4.3 Một số đơn đồ thị Định lý: Với mọi đồ thị G = (V, E), ta có: Hệ quả: Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ thị là 1 số chẵn Hệ quả: Mọi đồ thị đều có một số chẵn các đỉnh bậc lẻ. * 4.3 Một số đơn đồ thị Hệ quả: Đồ thị Kn có n(n-1) cạnh. * 4.4 Biểu diển đồ thị Danh sách kề A B B D E B A A C D E C C C B D D A B C E E A B D * 4.4 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 C 0 1 1 1 0 D 1 1 1 0 1 E 1 1 0 1 0 * 4.4 Biểu diển đồ thị Định lý: 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à: * 4.5 Đường đi và chu trình Đườ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 v1 ... 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. e1 e2 ek * 4.5 Đường đi và chu trình Đường đi P: EACB l(P) = 3 * 4.5 Đường đi và chu trình 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. * 4.5 Đường đi và chu trình 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. * 4.5 Đường đi và chu trình 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. * 4.5 Đường đi và chu trình Đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông, mỗi cặp của các đồ thị liên thông con này không có đỉnh chung. Mỗ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. * 4.5 Đường đi và chu trình Hai thành phần liên thông bất kỳ của G thì tách biệt. * 4.5 Đường đi và chu trình Định lý : Một đơn đồ thị G có n đỉnh và k thành phần thì có tối đa là (n – k)(n – k + 1) cạnh. * 4.5 Đường đi và chu trình Đẳ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’. * 4.5 Đường đi và chu trình A B C D E A’ B’ C’ D’ E’ * 4.5 Đường đi và chu trình Đồ 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). * 4.5 Đường đi và chu trình 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). * 4.5 Đường đi và chu trình 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 C D E * 4.5 Đường đi và chu trình Đồ 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. * 4.5 Đường đi và chu trình 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. * 4.5 Đường đi và chu trình 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 đủ. * 4.5 Đường đi và chu trình Định lý: 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à: và * 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. * 4.6 Đường đi và chu trình Euler Bài toán “Königsburg Bridges” (Leonhard Euler, 1707-1783) Xác định một chu trình đi qua tất cả 7 cây cầu, mỗi cái đúng 1 lần. * 4.6 Đường đi và chu trình Euler A B C D * 4.6 Đường đi và chu trình Euler Định nghĩa: Xét 1 đồ thị liên thông G. Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Khi này G còn được gọi là một đường đi Euler. Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Khi này G còn được gọi là một chu trình Euler. * 4.6 Đường đi và chu trình Euler Định lý 2.1 (Định lý Euler 1): Cho 1 đồ thị vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn. Chu trình Euler: DEABCEBD * 4.6 Đường đi và chu trình Euler Thuật toán tìm chu trình Euler của đồ thị G(V, E) Kết quả sẽ cho ra C là một chu trình Euler bao gồm thứ tự các cạnh của chu trình. * * 4.6 Đường đi và chu trình Euler C = Ø, v = 1 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,3 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,3,1 E  Ø * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,4, ,3,1 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,4,3, ,3,1 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,4,3,6, ,3,1 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,4,3,6,5, ,3,1 * 4.6 Đường đi và chu trình Euler 1 3 6 4 5 2 C = 1,2,4,3,6,5,2,3,1 E = Ø * 4.6 Đường đi và chu trình Euler Định lý 2.2 (Định lý Euler 2): Cho một đồ thi vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu G có đúng 2 đỉnh bậc lẻ. Đường đi Euler: DEABECBDC, DEABCEBDC * 4.6 Đường đi và chu trình Euler Thuật toán xác định đường đi Euler (bài tập) * 4.6 Đường đi và chu trình Euler Định lý 2.3 (Định lý Euler 3): Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu G cân bằng. Chu trình Euler: DEABCEBD * 4.6 Đường đi và chu trình Euler Định lý 2.4 (Định lý Euler 4): Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu trong G có 2 đỉnh a, b thỏa: dout(a) = din(a) + 1 din(b) = dout(b) + 1 mọi đỉnh còn lại đều cân bằng và đường Euler phải bắt đầu tại a và kết thúc tại b. * 4.6 Đường đi và chu trình Euler Đường đi Euler: DEABCEBDC, DEBCEABDC * 4.7 Đường đi và chu trình Hamilton (1805-1865) Định nghĩa: Xét 1 đồ thị liên thông G có hơn 1 đỉnh Một đường đi Hamilton của G là một đường đi sơ cấp qua tất cả các đỉnh của G. Một chu trình Hamilton của G là một chu trình sơ cấp qua tất cả các đỉnh của G. * 4.7 Đường đi và chu trình Hamilton Đường đi Hamilton: ABECD Đường đi Hamilton: BAECD * 4.7 Đường đi và chu trình Hamilton A B C D A B C D Chu trình Hamilton: ABCDA Chu trình Hamilton: ACBDA * 4.7 Đường đi và chu trình Hamilton Qui tắc tìm chu trình Hamilton Nếu tồn tại 1 đỉnh của G có bậc  1 thì G không có chu trình Hamilton. Nếu đỉnh x có bậc 2 thì cả 2 cạnh tới x đều phải thuộc chu trình Hamilton. Chu trình Hamilton không chứa bất kỳ chu trình con thực sự nào. Trong quá trình xây dựng chu trình Hamilton, sau khi đã lấy 2 cạnh tới 1 đỉnh x đặt vào chu trình rồi thì không thể lấy thêm cạnh nào tới x nữa. Do đó có thể xóa mọi cạnh còn lại tới x trong G. * 4.7 Đường đi và chu trình Hamilton Xét đỉnh 1, chọn 2 cạnh (1,2) và (1,6) * 4.7 Đường đi và chu trình Hamilton Xóa các cạnh (1,5), (1,4), (1,3), (1,7), (1,8), (1,9) (theo quy tắc 4). Các đỉnh 3, 4, 5 bậc 2, do đó các cạnh (2,3), (3,4), (4,5), (5,6) phải thuộc chu trình Hamilton (quy tắc 2). Chu trình con: 1,2,3,4,5,6,1 (không xóa được cạnh nào trong chu trình này). * 4.7 Đường đi và chu trình Hamilton Chọn cạnh (1,2), (1,3). Xóa các cạnh (1,4), (1,5), (1,6), (1,7), (1,8), (1,9) (quy tắc 4). Xóa cạnh (2,3) để không tạo chu trình (quy tắc 3). Các đỉnh 4, 5, 6, 7, 8, 9 có bậc 2 nên thuộc chu trình Hamilton (quy tắc 2). Chu trình nhận được: 1,3,4,5,6,7,8,9,2,1. * 4.7 Đường đi và chu trình Hamilton Định lý 2.5: Mọi đồ thị đầy đủ đều có chu trình Hamilton. * 4.7 Đường đi và chu trình Hamilton Định lý 2.6: Cho một đồ thị G. Giả sử có k đỉnh của G sao cho nếu xóa đi k đỉnh này cùng với các cạnh liên kết với chúng khỏi G thì đồ thị nhận được có hơn k thành phần. Khi đó, G không có chu trình Hamilton. * 4.7 Đường đi và chu trình Hamilton Định lý 2.7 (Định lý Dirac): Coi đồ thị G liên thông và có n đỉnh (n  3). Nếu mọi đỉnh của G đều có bậc  n/2 thì G có chu trình Hamilton. * 4.7 Đường đi và chu trình Hamilton Định lý 2.8 (tổng quát của định lý 2.7): Một đồ thị G có n đỉnh và 2 đỉnh bất kỳ nào cũng có tổng các bậc  n thì G có một chu trình Hamilton. * 4.7 Đường đi và chu trình Hamilton Định lý 2.9: Mọi đồ thị có hướng đầy đủ đều có đường đi Hamilton. Đường đi: CBDA hamilton Coi đồ thị G liên thông và có n đỉnh (n  3). Nếu mọi đỉnh của G đều có bậc  n/2 thì G có chu trình Hamilton Một đồ thị G có n đỉnh và 2 đỉnh bất kỳ nào cũng có tổng các bậc  n thì G có một chu trình Hamilton. Mọi đồ thị có hướng đầy đủ đều có đường đi Hamilton. * * Tóm tắt Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Khi này G còn được gọi là một đường đi Euler. Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Khi này G còn được gọi là một chu trình Euler. * Tóm tắt Cho 1 đồ thị vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn,Cân bằng Cho một đồ thi vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu G có đúng 2 đỉnh bậc lẻ và dout(a) = din(a) + 1 din(b) = dout(b) + 1 * Tóm tắt Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu G cân bằng. Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu trong G có 2 đỉnh a, b thỏa: dout(a) = din(a) + 1 din(b) = dout(b) + 1 mọi đỉnh còn lại đều cân bằng và đường Euler phải bắt đầu tại a và kết thúc tại b. * Tóm tắt Một đường đi Hamilton của G là một đường đi sơ cấp qua tất cả các đỉnh của G. Một chu trình Hamilton của G là một chu trình sơ cấp qua tất cả các đỉnh của G. Chưa có một điều kiện cần và đủ để xác định chu trình Hamilton.