CHƯƠNG 1 TỔNG QUAN VỀ CÂY KHUNG 1.1 MỘT SỐ KHÁI NIỆM LIÊN QUAN TỚI ĐỒ THỊ ( Các khái niệm cơ bản liên quan đến đồ thị được trình bày chi tiết trong tài liệu [1,2,6]) 1.1 Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh của đồ thị. Các loại đồ thị khác nhau được phân biệt dựa trên kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. u x y - Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề nhau. - Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
u x - Nếu u = (x,y) mà x,y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh vào. xX y 5 - Khi giữa cặp đỉnh (x, y) có nhiều hơn một cạnh thì ta nói những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội. Đồ 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ự.1: Đơn đồ thị vô hướng gồm 8 đỉnh 7 cạnh b. Đồ 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.2: Đơn đồ thị có hướng gồm 8 đỉnh và 7 cạnh c. Đồ 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. Bậc của đồ thị a. Bậc của đồ thị vô hướng 6 4 5 1 2 3 Hình 1.3 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 dG(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ị ví dụ, các đỉnh 1 và 3 có bậc là 2, các đỉnh 2, 4 và 5 có bậc bằng 3, đỉnh 6 có bậc 1. 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 A B C E D Hình 1.4: Đồ thị có hướng Xét đồ thị cho trong hình 1.
8 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à. 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à và.
Đỉnh với được gọi là đỉnh cô lập. Đỉnh có đượ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. Đỉnh có được gọi là đỉnh phát, đỉnh có là đỉnh thu.
Trong đồ thị có hướng Γ, bậc ngoài dΓ+(v), số cung xuất phát từ đỉnh v, và bậc trong dΓ-(v), số cung đi vào đỉnh v. Bậc dΓ(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 Δ+(Γ) và δ+(Γ); bậc trong cực đại và cực tiểu, Δ-(Γ) và δ-(Γ). Trong ngữ cảnh rõ ràng, có thể bỏ qua chỉ số dưới Γ 1.
ĐỒ THỊ CON, ĐỒ THỊ BỘ PHẬN 1. Đồ thị con, đồ thị bộ phận Cho đồ thị G = (V,E. - Nếu trong đồ thị đó ta bỏ đi một số đỉnh nào đó và các cạnh (cung) xuất phát từ đỉnh đó thì phần còn lại của đồ thị được gọi là đồ thị con của đồ thị G đã cho. - Nếu trong đồ thị G ta bỏ đi một số cạnh nhưng giữ nguyên các đỉnh thì phần còn lại của đồ thị được gọi là đồ thị bộ phận của đồ thị G.
Đường đi, chu trình trong đồ thị 9 Đường đi có độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x 0 , x 1 ,…, x n-1 , x n trong đó u = x 0 , v = x n , (x i , x i+1 ) ∈ E, i = 0, 1, 2,…, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x 0 , x 1 ), (x 1 , x 2 ), …, (x n-1 , x n ) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi làchu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.8: Đường đi trên đồ thị.
Trên đồ thị vô hướng cho trong hình 1.7 : a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 5. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 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ự như trong trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung.3 TỔNG QUAN VỀ CÂY KHUNG 1.1 Định nghĩa về cây : Cho đồ thị G = <V, E>, G được gọi là một cây nếu G liên thông và không có chu trình đơn, Đồ thị vô hướng không có chu trình đơn gọi là rừng (hợp của nhiều cây), với n = V > 1. Khi đó sáu tính chất sau là tương đương (1) G là đồ thị liên thông và không có chu trình (2) G không có chu trình và có n - 1 cạnh (3) G liên thông và có n - 1 cạnh (4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì G xuất hiện duy nhất một chu trình. (5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được sẽ không liên thông. (6) Mỗi cặp đỉnh trong G nối với nhau bằng một đường duy nhất.2 Cây khung Định nghĩa : Cây khung (còn gọi là cây bao trùm) của một đồ thị n đỉnh, m cạnh là cây gồm n đỉnh với số cạnh tối thiểu bảo toàn tính liên thông của đồ thị.
Cho đồ thị G = <V, E> với số đỉnh n lớn hơn 1. Giả sử G' là đồ thị bộ phận của G (G' nhận được từ G bằng cách bỏ đi một số cạnh nhưng vẫn giữ nguyên đỉnh). Nếu G' = <V, E'> là một cây thì G' gọi là cây bao trùm của G. Theo đúng tính chất về cây.
G' là cây bao trùm phải có n - 1 cạnh và là một đồ thị liên thông không có chu trình. Giả sử G = (V, E) là đồ thị vô hướng. Cây T = (V, F) với F E gọi là cây khung của đồ thị G. Tức là nếu như loại bỏ một số cạnh của G để được một cây thì cây đó gọi là cây khung (hay cây bao trùm của đồ thị).
Dễ thấy rằng với một đồ thị vô hướng liên thông có thể có nhiều cây khung. Điều kiện cần và đủ để một đồ thị vô hướng có cây khung là đồ thị đó phải liên thông.21 cây khung của đồ thì G.3 Cây khung cực tiểu Định nghĩa : Cho đồ thị G vô hướng và liên thông với n đỉnh và m cạnh, cạnh (u,v) có trọng số p(u,v) là một số dương. Cây khung cực tiểu (còn gọi là cây bao trùm ngắn nhất) của G là cây khung với tổng trọng số của các cạnh trong khung là nhỏ nhất.23 Cây khung cực tiểu của đồ thị G có trọng số = 30.4 Rừng khung, rừng khung cực tiểu 1.1 Rừng khung Định nghĩa : Cho G là một đồ thị vô hướng gồm n đỉnh và m cạnh. Hãy xác định các cây khung trong mỗi mảnh liên thông của G.
Tập hợp các cây khung đó được gọi là rừng khung của đồ thị G. Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.24 Đồ thị vô hướng có 8 đỉnh và 8 cạnh.25 Rừng gồm 2 cây khung 1.2 Rừng khung cực tiểu Định nghĩa: Cho đồ thị G vô hướng và liên thông với n đỉnh và m cạnh, cạnh (u,v) có trọng số p(u,v) là một số dương. Rừng khung cực tiểu của G là rừng khung với tổng trọng số của các cạnh trong khung là nhỏ nhất.26 Đồ thị có 8 đỉnh và 8 cạnh dạng x y p 7 4 3 7 5 5 2 5 3 3 6 8 2 1 Hình 1.27 Rừng khung cực tiểu 1.5 Cầu, cạnh trọng yếu Định nghĩa : Một cạnh trong đồ thị G được gọi là cầu hoặc cạnh trọng yếu nếu xóa cạnh đó đi (giữ lại các đỉnh ở hai đầu), sẽ làm tăng số thành phần liên thông của đồ thị. cầu phải là cạnh khung, nghĩa là phải thuộc một cây hoặc rừng khung.28 Đồ thị có 8 đỉnh, 7 cạnh.6 Khớp Một đỉnh v được gọi là điểm khớp của đồ thị G=(V,E) nếu loại bỏ v cùng các cạnh liên thuộc với nó khỏi đồ thị sẽ làm tăng số thành phần liên thông của đồ thị.7 Liên thông hóa Đối với đồ thị vô hướng G ( V, E .
G gọi là liên thông (connected) 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.