chương 1 sẽ trình bày những khái niệm tổng quan cơ bản về lý thuyết đồ thị, cách biểu diễn đồ thị trên máy tính như: định nghĩa một đồ thị, các loại đồ thị, bậc của đồ thị, tính liên thông của đồ thị, đường đi, chu trình của đồ thị… Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Đồ thị và các khái niệm liên quan 1. Định nghĩa đồ thị Chúng ta thường xuyên nhìn thấy hoặc đã sử dụng bản đồ giao thông của một thành phố, sơ đồ tổ chức một cơ quan, sơ đồ khối tính toán của một thuật toán, sơ đồ mạng máy tính., đó chính là những thí dụ cụ thể về đồ thị. Thí dụ: Một số dạng của đồ thị trong thực tế Mạng máy tính Sơ đồ giao thông Mạng nơron Hình 1.
Các mô hình đồ thị Đồ thị (Graph, ký hiệu G): Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả: G = (V, E) trong đó: V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V [4] Hình 1. Đồ thị hữu hạn Đồ thị G cho ở hình 1.2 với tập ác đỉnh V = {a, b, c, d, e} và tập các cạnh E ={(a, b), (b, c), (b, e), (c, e), (c, d)}.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Trong đồ thị ở hình 1.2 thì hai đỉnh a và c kề với đỉnh b, ba đỉnh a, c và e kề với đỉnh b. Do vậy, ta có thể định nghĩa đồ thị bằng ánh xạ kề như sau: Về bản chất, đồ thị là một tập hợp các đối tượng được biểu diễn bằng các đỉnh và giữa các đối tượng này có một quan hệ nhị nguyên biểu diễn bằng các cạnh. Cặp đỉnh (x, y) ∈ E không sắp thứ tự được gọi là cạnh vô hướng, còn nếu nó có sắp thứ tự thì được gọi là cạnh có hướng.
Đồ thị vô hướng Đồ thị G = (V, E) được gọi là đồ thị vô hướng nếu tất cả các cạnh u E mà cặp đỉnh thuộc nó u = (x, y) (trong đó x, y V) không phân biệt thứ tự [8]. Đơn đồ thị vô hướng 8 đỉnh 7 cạnh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Đồ thị có hướng Đồ thị G = (V, E) được gọi là đồ thị có hướng nếu tất cả các cạnh u E mà cặp đỉnh thuộc nó u = (x, y) (trong đó x, y V) có phân biệt thứ tự. Đồ thị có hướng là đồ thị mà mọi u = (x, y) V đều là cung [8].
Đơn đồ thị có hướng 8 đỉnh 7 cạnh 1. Đồ thị hỗn hợp Đồ thị G = (V, E) được gọi là đồ thị hỗn hợp nếu tất cả các cạnh u E mà cặp đỉnh thuộc nó u = (x, y) có nhiều hơn một đường đi [3]. Đồ thị hỗn hợp Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Một số dạng đồ thị đặc biệt 1.1 Đồ thị đầy đủ Đồ thị đầy đủ n đỉnh, ký hiệu bởi Kn, là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối [3].
Thí dụ: Các đồ thị đầy đủ K1, K2, K3 cho trong hình 1. Đồ thị đầy đủ Đồ thị đầy đủ Kn có tất cả n*(n - 1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhấ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). Thí dụ: Đồ thị vòng C1, C2, C3 như hình 1.7 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.3 Đồ thị bánh xe Đồ thị bánh xe Wn thu được từ Cn bằng cách bổ sung vào một đỉnh mới nối với tất cả các đỉnh của Cn [4].
Thí dụ: Đồ thị bánh xe W1, W2, W3 như hình 1. Đồ thị bánh xe W1, W2, W3 1.4 Đồ thị lập phương Đồ thị lập phương 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 [4]. Thí dụ: Đồ thị vòng Q1, Q2, Q3 như hình 1.
Đồ thị lập phương Q1, Q2, Q3 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Đồ thị hai phía Đơn đồ thị G = (V, E) được gọi là đồ thị hai phía nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối một đỉnh nào đó trong X với một đỉnh nào đó trong Y. Khi đó ta sẽ sử dụng ký hiệu G = (X ∪ Y, E) để chỉ đồ thị hai phía với tập đỉnh X ∪ Y [4]. Định lý: Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ.
Để kiểm tra xem một đồ thị liên thông có phải là hai phía hay không ta có thể áp dụng thủ tục sau: - Cho v là một đỉnh bất kỳ của đồ thị. - Đặt X={v}, còn Y là tập các đỉnh kề của v. Khi đó các đỉnh kề của các đỉnh trong Y phải thuộc vào X. Ký hiệu tập các đỉnh như vậy là T.
- Vì thế nếu phát hiện T ∩ Y # ∅ thì đồ thị không phải là hai phía, kết thúc. - Ngược lại, đặt X=X ∩ T. - Tiếp tục xét như vậy đối với T’ là tập các đỉnh kề của T,. Đồ thị hai phía G=(X ∪ Y, E) với |X|= m, |Y| = n được gọi là đồ thị hai phía đầy đủ và ký hiệu là K2, 3, K3, 3, K3, 4.
Thí dụ: Các đồ thị 2 phía K2, 3, K3, 3, K3, 4 như hình 1. Đồ thị 2 phía K2,3, K3,3, K3,4 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Đồ thị phẳng Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị .z Thí dụ: Đồ thị K như hình 1.11 bên dưới là đồ thị phẳng, vì ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh.
Bậc của đồ thị 1. Bậc của đồ thị vô hướng Hình 1. Đồ thị vô hướng Hình 1.12 là một đồ thị đơn với tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)} Bậc của đỉnh v trong đồ thị G, ký hiệu deg(v), là số cạnh liên thuộc với v, trong đó, khuyên được tính hai lần. Một đỉnh có bậc 0 là đỉnh cô lập.
Đỉnh có bậc 1 là một đỉnh treo hay lá. Trong thí dụ 1. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 13 Nếu tập cạnh E là hữu hạn thì tổng giá trị bậc của các đỉnh gọi là bậc của đồ thị. Bậc của đồ thị bằng hai lần số cạnh.
Số các đỉnh bậc lẻ luôn là số chẵn. Bậc cực đại của đồ thị G, ký hiệu Δ(G), là bậc lớn nhất của các đỉnh trong đồ thị; bậc cực tiểu, δ(G), là bậc nhỏ nhất của các đỉnh trong đồ thị. Bậc của đồ thị có hướng Hình 1. Đồ thị có hướng Xét đồ thị cho trong hình 1.
Bậc của một đỉnh v là số cạnh liên thuộc với v (trong đó, khuyên được tính hai lần). Bậc của v được ký hiệu là deg(v). Trong một đồ thị có hướng, bậc trong của đỉnh v là số cung kết thúc tại v, còn bậc ngoài là số cung xuất phát từ v. Bậc trong và bậc ngoài của v được ký hiệu là deg+(v) và deg-(v).
Đỉnh với deg(v) được gọi là đỉnh cô lập. Đỉnh có deg(v) = 1 được gọi là lá. Nếu mỗi đỉnh của đồ thị đều có bậc bằng nhau và bằng k thì đồ thị được gọi là đồ thị chính quy bậc k và đồ thị được coi là có bậc bằng k. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 14 Trong đồ thị có hướng G, bậc ngoài deg+(v), số cung xuất phát từ đỉnh v, và bậc trong deg-(v), số cung đi vào đỉnh v.
Bậc deg+(v) của đỉnh v bằng tổng bậc ngoài và bậc trong của đỉnh đó. Bậc ngoài cực đại và cực tiểu được ký hiệu Δ+(G) và δ+(G); bậc trong cực đại và cực tiểu, Δ-(G) và δ-(G). Trong ngữ cảnh rõ ràng, có thể bỏ qua chỉ số dưới G [8]. Đường đi, chu trình, tính liên thông của đồ thị Đường đi có độ dài k từ đỉnh u đến đỉnh v trên đồ thị vô hướng G = (V, E) là dãy: x0, x1,…, xn-1, xk Trong đó: + k là số nguyên dương, + x0 = u, xk = v, (xi, xi+1) E, + i = 0, 1, 2,.
Đường đi như trên còn có thể biểu diễn thành dãy các cạnh: (x0, x1), (x1,x2) ,. Đỉnh u là đỉnh đầu, đỉnh v là đỉnh cuối của đường đi. Chu trình: là đường đi có đỉnh đầu trùng với đỉnh cuối (u = v). Đường đi đơn: là đường đi mà không có cạnh nào lặp lại.
Chu trình đơn: là chu trình mà không có cạnh nào lặp lại. Thí dụ: Tìm các đường đi, chu trình trong đồ thị vô hướng như hình 1. Đường đi trên đồ thị + a, b, c, d là đường đi đơn độ dài 3. + a, b, f, không là đường đi vì (b, Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 15 f) không phải là cạnh của đồ thị.
+ Dãy a, b, c, f, e, a là chu trình độ dài 5. + Đường đi a, b, c, f, e, b, c có độ dài 6 không phải là đường đi đơn vì cạnh (b, c) xuất hiện hai lần. Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự, chỉ có điều khác biệt duy nhất là ta phải chú ý tới các cung của đồ thị Đồ thị liên thông: Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tồn tại đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Nếu G không liên thông thì chắc chắn nó sẽ là hợp của hai hay nhiều đồ thị con liên thông, các đồ thị con này đôi một không có đỉnh chung.
Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét [1]. Một đồ thị được coi là hoàn toàn không liên thông nếu không có đường đi giữa hai đỉnh bất kỳ trong đồ thị.