Cây khung của đồ thị

Định nghĩa 2. Đồ thị G và cây khung của nó được cho trong hình 2

Hình 2. Đồ thị và các cây khung của nó

Định lý sau đây cho biết số lượng cây khung của đồ thị đầy đủ K_n:

Định lý 2 (Cayley). Số lượng cây khung của đồ thị K n là n n-2 .

Định lý 2 cho thấy số lượng cây khung của đồ thị là một số rất lớn. Bây giờ ta xét áp dụng của thuật toán tìm kiếm theo chiều sâu và theo chiều rộng trên đồ thị để xây dựng cây khung của đồ thị vô hướng liên thông. Trong cả hai trường hợp mỗi khi ta đến được đỉnh mới u (tức Chuaxet[u]=true) từ đỉnh v thì cạnh (v, u) sẽ được kết nạp vào cây khung. Hai thuật toán tương ứng được trình bày trong hai thủ tục sau đây.

Procedure stree_DFS(v);

(* tim kiem theo chieu sau ap dung vao tim tap canh cua cay khung T cua do thi vo huong lien thong G cho boi danh sach ke. Cac bien Chuaxet, Ke, T la toan cuc*)

begin

Chuaxet[v]:=false;

For u ∈ Ke(v) do

If Chuaxet[u] then

Begin

T:=T  (u,v);

STREE_DFS(u);

End;

end;

(* Main Program *)

begin

(* Initialition *)

for u ∈ V do Chuaxet[u]:=true;

T := ∅ ; (* T la tap canh cua cay khung *)

STREE_DFS(root); ( root la dinh nao do cua do thi *)

end.

Procedure Stree_BFS(v);

(* tim kiem theo chieu rong ap dung tim tap canh cua cau khung T cua do thi vo huong lien thong G cho boi danh sach Ke *)

begin

Queue:= ∅ ;

Queue ⇐ r;

Chuaxet[r]:=false;

While queue <> ∅ do

Begin

V ⇐ queue;

For r ∈ Ke(v) do

If Chuaxet[u] then

Begin

Queue ⇐ u;

Chuaxet[u]:=false;

T:= T  (u,v);

End;

End;

end;

(* Main Program *);

begin

for u ∈ V do Chuaxet[u]:=true;

T := ∅ ; (* T la tap canh cua cay khung *)

Stree_BFS(root); (* root la mot dinh tuy y cua do thi *)

end.

 

Chú ý:

1. Lập luận tương tự như trong phần trước có thể chỉ ra được rằng các thuật toán mô tả ở trên có độ phức tạp tính toán O(m+n).

2. Cây khung tìm được theo thủ tục Stree_BFS() là cây đường đi ngắn nhất từ gốc r đến tất cả các đỉnh còn lại của đồ thị.