Cây bao trùm
Bách khoa toàn thư mở Wikipedia
Cây bao trùm (tiếng Anh: spanning tree), còn được gọi là cây khung, của đồ thị G là cây con chứa tất cả các đỉnh của G. Nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình.
Cây bao trùm của đồ thị liên thông G cũng có thể định nghĩa như một đồ thị con không chu trình lớn nhất, hay một đồ thị con liên thông nhỏ nhất của G.
Mọi đồ thị liên thông đều có cây bao trùm.
Mục lục |
[sửa] Số các cây bao trùm của một đồ thị liên thông
Gọi t(G) là số các cây bao trùm của đồ thị liên thông G. Trong một số trường hợp, số t(G) có thể tính trực tiếp. Chảng hạn nếu G là một cây, khi đó t(G)=1, còn khi G là một đồ thị vòng Cn với n đỉnh thì t(G)=n. Với đồ thị G bất kỳ, số t(G) có tính nhờ Định lý Kirchhoff.
Công thức Cayley là công thức cho số các cây bao trùm của đồ thị đầy đủ Kn với n đỉnh: t(Kn) = nn − 2.
Nếu G là đồ thị hai phía đầy đủ Kp,q, thì t(G) = pq − 1qp − 1, còn nếuG là [[đồ thị khối n-chiều]] Qn, thì 
. Các công thức này rút ra từ lỹ thuyết các ma trận.
Nếu G là một đa đồ thị và e là một cạnh của G, thí số t(G) các cây bao trùm của G thỏa mãn quan hệ t(G)=t(G-e)+t(G/e) (deletion-contraction recurrence), trong đó G-e là đa đò thị suy ra từ G bằng cách xóa đi cạnh e và G/e là đồ thị rút gọn cạnhe của G, trong đó các cạnh bội xuất hiện từ phpé rút gọn mày không bị xóa.
Để tìm cây bao trùm, ta có thể áp dụng các thuật toán tìm kiếm theo chiều rộng hoặc tìm kiêm theo chiều sâu. Giả sử G=(X,E) là đồ thị liên thông. Vì cây bao trùm phải chứa tất cả các đỉnh của đồ thị nên bất kỳ đỉnh nào cũng phải có mặt trong cây bao trùm. Do đó cả hai thuật toán sau đều lấy điểm xuất phát từ một đỉnh bất kỳ.
- Xem thêm Tìm cây bao trùm nhỏ nhất
[sửa] Thuật toán tìm cây bao trùm theo chiều rộng
Tìm kiếm ưu tiên chiều rộng (tiếng Anh: Breadth first search, viết tắt BFS) là thuật toán tìm đồ thị bắt đầu ở đỉnh gốc và trước tiên tìm kiếm trong các đỉnh kề.
[sửa] Miêu tả thuật toán
Tư tưởng của thuật toán này là tước tiên tìm trên tất các đỉnh gần với đỉnh xuất phát nhất trong khả năng có thể. Áp dụng vào tìm cây bao trùm, thuật toán được mô tả như sau
Gọi T là cây con sẽ được xây dưng:
- Chọn một đỉnh s bất kỳ của đồ thị làm gốc của cây T. Lúc này cây T chỉ có một đỉnh s là gốc của T., (s có mức 0) và chưa có cạnh nào. Tất cả các đỉnh trong G chưa được xét.
- Lần lượt xét tất cả các đỉnh trong T có mức thấp nhất chưa xét xong. Mỗi lần xét đỉnh u:
- Tìm tất cả các cạnh nối đỉnh u với một đỉnh ngoài T.
- Nếu không có các cạnh như vậy thì đỉnh u đã được xét xong.
- Nếu có e=(u,v) nối u với v nằm ngoài T thì bổ sung vào T tất cả các cạnh e=(u,v) và đỉnh v như vậy . Nếu u có mức k thì các đỉnh mới bổ xung có mức k+1. Khi đó đỉnh u đã được xét xong.
- Quá trình dừng lại khi tất cả các đỉnh đã nằm trong T đã được xét.
- T là cây bao trùm cần tìm.
[sửa] Ví dụ
Với sự mô tả trên đây có thể tìm cây bao trùm dễ dàng trên các đồ thị có số các đỉnh và cạnh tương đối nhỏ.
[sửa] Mã giả
Để xây dựng giải thuật trên máy tính cần làm rõ các cấu trúc dữ liệu biểu diễn đồ thị cũng như quá trình xét các đỉnh và các cạnh. Giả sử đồ thị G cho bởi các danh sách các cạnh kề với từng đỉnh. Danh sách này thường được ký hiệu là Adj[u] đối với danh scáh các cạnh kề đỉnh u. Để phân biệt các đỉnh chưa nằm trong T, các đỉnh trong T đã xét xong và chưa xét, ta hình dung một quá trình tô màu các đỉnh: Đỉnh mới bổ xung vào T thì tô màu xám (GRAY), đỉnh trong T đã xét xong thi tô màu đen (BLACK), các đỉnh chưa nằm trong T thi tô mầu trắng (WHITE). Ta còn muốn xác định các cạnh nào nằm trên cây. Xem T như một cây có gốc, trừ gốc, mỗi cạnh trong cây nối một đỉnh với cha của nó, vì vậy ta dùng một hàm Parent(u) để xác định các cạnh được đưa vào cây T. Vì thế, khi khởi tạo ta có các biến danh sách COLOR(u) và PARENTS(u). Theo nguyên tắc xét đỉnh gần gốc nhất, các đỉnh gia nhập cây sớm sẽ được xét trươc. Để "theo dõi" chặt chẽ thứ tự các đỉnh được đưa vào T ta dùng một cấu trúc hàng đợi Q (Queue).
Procedure BFS(G,r) {
Var list COLOR(u),PARENTS(u),Queue Q
/* Khởi tạo */
For each u of E do {
GRAY(u)=WHITE
PARENTS(u)=Null
}
Push(Q,r) /*Đẩy đỉnh đầu tiên vào hàng đợi*/
/*Xét các đỉnh*/
While Q <> rỗng do {
u = Pop(Q);/*Lấy đỉnh đầu hàng đợi Q ra để xét*/
COLOR(s)=GRAY
For each v of Adj(u)
{
if COLOR(v)=WHITE then {
COLOR(v)=GRAY
PARENTS(v)=u
Push(Q,v) /*đẩy đỉnh v vào hàng đợi*/
}
COLOR(u)=BLACK
}
}
Return PARENTS
[sửa] Thuật toán tìm cây bao trùm theo chiều sâu
[sửa] Miêu tả thuật toán
Tìm kiếm ưu tiên chiều chiều sâu (tiếng Anh :Depth-first search , viết tắt là DFS) là một thuật toán tìm kiếm trên đồ thị.
Tư tưởng của thuật toán này là trong quá trình tìm các đỉnh của đồ thị để ghép vào cây ta luôn tìm các tìm các đỉnh càng xa gốc càng tốt. Áp dụng vào tìm cây bao trùm, thuật toán này được mô tả như sau. Gọi T là cây con sẽ được xây dưng
- Chọn một đỉnh s bất kỳ của đồ thị làm gốc của cây T. Lúc này cây T chỉ có một đỉnh s là gốc của T., (s có mức 0) và chưa có cạnh nào. Tất cả các đỉnh trong G chưa được xét.
- Lần lượt xét tất cả các đỉnh trong T có mức cao nhất nhất chưa xét xong. Mỗi lần xét đỉnh u: Tìm một cạnh nối đỉnh u với một đỉnh ngoài T.
- Nếu không có các cạnh như vậy thì đỉnh u đã được xét xong. Ta quay về đỉnh đứng ngay trước đỉnh u.
- Nếu có cạnh e=(u,v) nối u với v ngoài T thì bổ sung vào T cạnh e và đỉnh v. Nếu u có mức k thì đỉnh mới bổ xung v có mức k+1. Đỉnh mới bổ xung v chỉnh là đỉnh có mức cao nhất mới được bổ xung vào T.
- Quá trình dừng lại khi tất cả các đỉnh nằm trong T đã được xét.
- T là cây bao trùm cần tìm.
[sửa] Ví dụ
[sửa] Mã giả
Trong mã của giải thuật tìm kiếm theo chiều sâu ta cũng đưa vào các biến danh sách CORLOR(u) và PARENTS(u) trên tập các đỉnh. Sau khi khởi tạo ta dùng cách gọi đệ quy để tìm cây bao trùm của G(X,E)
Procedure DFS ( G ){
/*Khởi tao*/
For each đỉnh of E do {
COLOR[u] := WHITE
PARENTS(u)=Null
}
/* Tìm kiếm đệ quy*/
For each đỉnh u of E do
if if COLOR[u] = WHITE
then DFS-Visit (u)
Return PARENTS;
}
Procedure DFS-Visit(u) {
COLOR[u]:= GRAY /*Bắt đầu xét u*/
for each v of Adj[u] do {
if COLOR[v] = WHITE
then {
PARENTS[v] := u
DFS-Visit (v)
}
}
COLOR[u]:=BLACK /*Xét xong u*/
}
Giải thuật đệ quy trên đây dễ viết nhưng khó nhìn thấy ý nghĩa thực sự của giải thuật tìm khiếm theo chiều sâu. Trong nó có chứa một thao tác được gọi là thao tác quay lui: đi xa hết mức nếu có thể, nếu không thể đi được nữa thì lùi lại xét đỉnh ở bước trước (tức là đỉnh cha của nó).
[sửa] Giải thuật không đệ quy
Theo nguyên tắc đị xa nhất có thể, giải thuật không đệ quy tìm cây bao trùm theo chiều sâu cần đến một cấu trúc ngăn xếp S (Stack) để lưu trữ các đỉnh theo thứ tự đưa vào cây. Khi khới tạo ta cho một đỉnh bất kỳ váo ngăn xếp S.
Ở mỗi bước ta lấy đỉnh u nằm cuối Stack ra để xét. Nếu trong danh sách các đỉnh kề với u không còn đỉnh nào chưa nằm trong cây T (tất cả chúng đã xét xong hoặc nằm trong Stack) thì đỉnh u đã xét xong, nếu có một đỉnh không nằm trong Stack và chưa xét thì chó nó vào Stack. Quá trình chấm dứt khi Stack là rỗng.
Procedure DFS(G,r){
Var Stack S, list COLOR(u), PARENTS(u)
/*Khởi tạo: Tất cả các đinh chưa xét */
For each' v of E do {
COLOR(u):=WHITE
PARENTS(u):=NULL
}
/* Cho đỉnh đầu tiên vào Stack*/
COLOR(r):=GRAY
Push(S,r)
While' S khác rỗng do (
u= End(S); /* Xét phần tử mằm sau cùng trong Stack*/
Find:=False ;
For each v of Adj(u) do {
If COLOR(v)=WHITE then {
PARENT(v):=u
COLOR(v):=GRAY
Push(S,v) /*Bổ xung v vào cuối ngăn xếp*/
Breack
find=TRUE
}
if not Find then {
COLOR(u)=BLACK
Pos(S,u) /*Lấy u khỏi Stack */
}
}
}
Trong giải thuật này mỗi lần xét một đỉnh cuối trong ngăn xếp, ta không vội vã đưa nó ra khỏi ngăn xếp. Nó chỉ được xét xong và đưa khỏi ngăn xếp khi tất cả các đỉnh kề với nó đã được đưa vào cây (nằm chờ trong ngăn xếp hoặc đã xét xong). Mỗi lần một đỉnh đưa khỏi ngăn xếp ta quay lại xét phần tử đứng trước nó trong ngăn xếp là ta đã thức hiện một thao tác "quay lui". Như vậy đỉnh đưa vào đầu tiên bao giờ cũng là đỉnh cuối cùng ra khỏi ngăn xếp.
Thay cho thao tác tìm đỉnh trắng trong danh sách kề với đỉnh u, ta cũng có thể lấy ngay phần tử đầu tiên v trong danh sách kề Adj(u) (nếu nó khác rỗng) vào ngăn xếp và xóa v khỏi danh sách kề. Khi đó toàn bộ các đỉnh trong danh sách kề của u đều chưa được xét.
Ta có:
Procedure DFS(G,r){
Var Stack S, list COLOR(u), PARENTS(u)
/*Khởi tạo: Tất cả các đinh chưa xét */
For each' v of E do {
COLOR(u):=WHITE
PARENTS(u):=NULL
}
/* Cho đỉnh đầu tiên vào Stack*/
COLOR(r):=GRAY
Push(S,r)
/*lần lượt xét các đỉnh*/
While' S khác rỗng do (
u= End(S); /* Xét phần tử mằm sau cùng trong Stack*/
If Adj(u) khác rỗng then
v=Adj(u)(1)
Delete(Adj(u),v) /*Xóa (tạm thời) v khỏi danh sách kề của u*/
PARENT(v):=u
Push(S,v) /*Bổ xung v vào cuối ngăn xếp*/
else {
COLOR(u)=BLACK
Pos(S,u) /*Lấy u khỏi Stack */
}
}
}
