• Nếu đồ thị bộ phận T của đồ thị vô hướng liên thông G = (V, E) là một cây thì khi đó cây T được gọi là cây khung (spanning tree) của đồ thị G.
• Cây khung còn có tên gọi khác là cây phủ, cây bao trùm, cây tối đại.
• Một đơn đồ thị là liên thông nếu và chỉ nếu nó có cây khung.
Chứng minh:
• Chiều đảo: Giả sử G có cây khung T. Do T là cây nên có đường đi trên T giữa 2 đỉnh bất kỳ (tính chất 5). Vì T là đồ thị bộ phận của G (theo định nghĩa cây khung) nên G có đường đi giữa 2 đỉnh bất kỳ. Do đó, G liên thông
• Cho G = (V, E) là đồ thị vô hướng, liên thông. Mỗi cạnh e ∈ E của đồ thị được gán một trọng số (weight) hay chi phí (cost) không âm c(e), gọi là độ dài (length) của cạnh đó. Giả sử T = (V T , E T ) là cây khung của đồ thị G. Ta gọi độ dài c(T) của cây khung T là tổng độ dài các cạnh của nó:
• Một đồ thị mà các cạnh được gán trọng số như trên, được gọi là đồ thị có trọng số (weighted graph).
• Trong số tất cả các cây khung của đồ thị G, hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất (minimum spanning tree) của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất.
• Tương tự như vậy, cây khung có độ dài lớn nhất được gọi là cây khung lớn nhất.
• Bài toán xây dựng hệ thống đường cao tốc: Giả sử ta muốn xây dựng một hệ thống đường cao tốc nối n thành phố sao cho hành khách có thể đi từ một thành phố bất kỳ đến các thành phố còn lại. Mặt khác, trên quan điểm kinh tế đòi hỏi là chi phí về xây dựng hệ thống đường phải là nhỏ nhất.
• Rõ ràng, đây là đồ thị mà đỉnh là các thành phố còn cạnh ứng với các tuyến đường và bài toán đặt ra là phải tìm cây khung nhỏ nhất trong đó trọng số là chi phí thực hiện các tuyến đường cao tốc.
• Bài toán nối mạng máy tính: Cần nối mạng một hệ thống gồm n máy tính đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là c[i, j]. Hãy tìm cách nối mạng sao cho tổng chi phí nối mạng là nhỏ nhất.
• Prim và Kruskal là hai thuật toán thông dụng để tìm cây khung nhỏ nhất.
• Thuật toán Prim do Robert Prim đưa ra vào năm 1957
• Thuật toán Kruscal do Joseph Kruskal phát minh năm 1956.
• Cho G = (V, E) là một đồ thị liên thông có trọng số gồm n đỉnh.
Bước 1. Chọn tùy ý một đỉnh bất kỳ v ∈ V và khởi tạo: Y = {v} và T = ∅.
Bước 2. Trong số những cạnh e = (v, w), trong đó v ∈ Y và w ∈ V\Y, ta chọn cạnh có độ dài nhỏ nhất.
Bước 3. Gán Y = Y ∪ {w} và T = T ∪ {e}
Bước 4. Nếu T đủ n – 1 phần tử thì dừng, ngược lại làm tiếp bước 2.
T chính là cây khung nhỏ nhất.
• Cây khung còn có tên gọi khác là cây phủ, cây bao trùm, cây tối đại.
Chứng minh:
• Chiều đảo: Giả sử G có cây khung T. Do T là cây nên có đường đi trên T giữa 2 đỉnh bất kỳ (tính chất 5). Vì T là đồ thị bộ phận của G (theo định nghĩa cây khung) nên G có đường đi giữa 2 đỉnh bất kỳ. Do đó, G liên thông
• Chiều thuận: Giả sử G liên thông. Nếu G không phải là cây, thì nó phải có một chu trình đơn. Xóa đi một cạnh bất kỳ trong các chu trình đơn này. Đồ thị nhận được có số cạnh ít hơn đồ thị cũ, nhưng số đỉnh bằng nhau và tính liên thông vẫn còn. Nếu đồ thị bộ phận này không là cây, thì nó vẫn còn chứa chu trình, ta lại lặp lại quá trình xóa cạnh cho đến khi không còn chu trình đơn. Điều này có thể vì số cạnh là hữu hạn. Quá trình kết thúc khi không còn chu trình đơn trong đồ thị. Cây được tạo ra vẫn còn liên thông. Cây này, hơn nữa là cây khung vì nó chứa toàn bộ các đỉnh của G.
• Ta có thể sử dụng 2 thuật toán tìm kiếm theo chiều rộng và theo chiều sâu trong chương Đại cương Lý thuyết đồ thị để xác định cây khung.
• Quá trình duyệt các đỉnh chính là quá trình tìm cây khung của đồ thị.
• Định lý Borchart, Sylvester, Cayley: Số cây khung của đồ thị đầy đủ K n là n n-2
• Quá trình duyệt các đỉnh chính là quá trình tìm cây khung của đồ thị.
• Định lý Borchart, Sylvester, Cayley: Số cây khung của đồ thị đầy đủ K n là n n-2• Cho G = (V, E) là đồ thị vô hướng, liên thông. Mỗi cạnh e ∈ E của đồ thị được gán một trọng số (weight) hay chi phí (cost) không âm c(e), gọi là độ dài (length) của cạnh đó. Giả sử T = (V T , E T ) là cây khung của đồ thị G. Ta gọi độ dài c(T) của cây khung T là tổng độ dài các cạnh của nó:
• Một đồ thị mà các cạnh được gán trọng số như trên, được gọi là đồ thị có trọng số (weighted graph).
• Tương tự như vậy, cây khung có độ dài lớn nhất được gọi là cây khung lớn nhất.
• Rõ ràng, đây là đồ thị mà đỉnh là các thành phố còn cạnh ứng với các tuyến đường và bài toán đặt ra là phải tìm cây khung nhỏ nhất trong đó trọng số là chi phí thực hiện các tuyến đường cao tốc.
• Prim và Kruskal là hai thuật toán thông dụng để tìm cây khung nhỏ nhất.• Thuật toán Prim do Robert Prim đưa ra vào năm 1957
• Thuật toán Kruscal do Joseph Kruskal phát minh năm 1956.
Bước 1. Chọn tùy ý một đỉnh bất kỳ v ∈ V và khởi tạo: Y = {v} và T = ∅.
Bước 2. Trong số những cạnh e = (v, w), trong đó v ∈ Y và w ∈ V\Y, ta chọn cạnh có độ dài nhỏ nhất.
Bước 3. Gán Y = Y ∪ {w} và T = T ∪ {e}
Bước 4. Nếu T đủ n – 1 phần tử thì dừng, ngược lại làm tiếp bước 2.
T chính là cây khung nhỏ nhất.
| • Giả sử chọn đỉnh 1 là đỉnh đầu • Cập nhật • Y = {1} • T = ∅ |
 |
|
• Chọn cạnh (1, 2) vì là cạnh có trọng nhỏ nhất trong số các cạnh thỏa yêu cầu ở bước 2: (1, 2), (1, 4) • Cập nhật: • T = {{1, 2}} |
 |
|
Chọn cạnh (2, 4) vì là cạnh có trọng nhỏ nhất trong số các cạnh thỏa yêu cầu ở bước 2: (1, 4), (2,3), (2, 4) • Cập nhật: • T = {{1, 2}, {2, 4}} |