CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
3.Bài toán cây khung nhỏ nhất:
Cho đồ thị G=(V,E) là đồ thị vô hướng , liên thông với
V={v1,v2,...,vn}, E= m cạnh với ∀e ∈ E, ∃C(e)>0: C(e) gọi là độ dài của nó.
H=(V,T) là cây khung của đồ thị G. Ta gọi độ dài C(H) của cây khung H là tổng độ dài các cạnh của nó
C(H) = ΣC(e), e ∈ H.
Tìm H sao cho C(H) nhỏ nhất.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
thay đổi nội dung bởi: myhanh, 03-06-2008 lúc 09:52 AM.
|