最小生成樹
維基百科,自由的 encyclopedia
最小生成樹(英語:Minimum spanning tree,簡稱MST)是最小權重生成樹(英語:Minimum weight spanning tree)的簡稱,是一副連通加權無向圖中一棵權值最小的生成樹。
在一給定的無向圖 中, 代表連接頂點 u 與頂點 v 的邊(即 ),而 代表此邊的權重,若存在 T 為 E 的子集(即 )且 (V, T) 為樹,使得:
的 w(T) 最小,則此 T 為 G 的最小生成樹。
一個連通圖可能有多個生成樹。當圖中的邊具有權值時,總會有一個生成樹的邊的權值之和小於或者等於其它生成樹的邊的權值之和。廣義上而言,對於非連通無向圖來說,它的每一連通分量同樣有最小生成樹,它們的並被稱為最小生成森林。
以有線電視電纜的架設為例,若只能沿着街道佈線,則以街道為邊,而路口為頂點,其中必然有一最小生成樹能使佈線成本最低。