最小生成樹的概念與應用（最小生成樹的作用和意義）
本文目錄一覽：
【離散數(shù)學】樹(二)最小生成樹基本原理
最小生成樹是指從一個給定的連通網絡中，選擇若干條邊，使得所選邊的權值之和最小，而且這些邊連接了所有的頂點，形成一棵樹。離散數(shù)學中求最小生成樹的方法有Prim算法和Kruskal算法。
） 樹是無回路的連通圖。2）對于某個圖，求它的最小生成樹，比較簡單的方法，先畫出圖中所有節(jié)點，從權值最小的邊開始依次連接頂點，注意不要形成回路，最后得到的圖就是最小生成樹。
最小生成樹不需要學離散數(shù)學 Kruskal算法很容易理解啊， 從所有邊中找到一個最小的邊，且將改變放入后不會生成圈，重復n-1次后求出最小生成樹。 我們首先將所有邊排序，然后從小到大判斷，如果不產生圈就加入樹中，當加入n-1條邊時停止。
em，其中e1的權最小，em的權最大，m為邊數(shù)。②取權最小的兩條邊構成邊集T0，即T0={e1，e2}，從e3起，按次序逐個將各邊加進 *** T0中去，若出現(xiàn)回路則將這條邊排除（不加進去），按此法一直進行到em，最后得到n-1條邊的 *** T0={e1，e2，…，en-1}，則T0導出的子圖就是圖G的最小生成樹。
第一步：加入邊V1V2，包含2個頂點。第二步：加入邊V2V6，包含3個頂點。第三步：加入邊V2V4，包含4個頂點。第四步：去掉V4V6，否則就構成回路了。加入V5V6，包含5個頂點。第五步：去掉V1V4，否則就構成回路了。加入V3V6，包含所有頂點了。
所謂權值，實際上是賦予一個抽象概念一個數(shù)值。最小生成樹中的權值，是邊的權值之和。
最小樹問題的求解方法
常用的求最小樹的算法有：破圈法、避圈法、邊割法和Dijkstra算法等等?；靖拍?最小樹問題是網絡最優(yōu)化問題之一，是指如何從網絡的支撐樹中求出最小樹的問題。求解最小樹問題常用破圈法和貪婪算法。最小生成樹問題是組合優(yōu)化中的一個重要的問題。
破圈法，在網絡圖中尋找一個圈。若不存在圈，則已經得到最短樹或網絡不存在最短樹；去掉該圈中權數(shù)最大的邊；反復重復前兩步，直到最小樹。破圈法為“見圈破圈”，即如果看到圖中有一個圈，就將這個圈的邊去掉一條，直至圖中再無一圈為止。
用matlab做最小樹問題，可以用graph函數(shù)求得其最佳路線和最短距離。編程后可以得到如下結果。
生成樹的定義是什么?
1、生成樹的定義是生成樹是指一個連通的無圈圖，最小樹是指一個連通圖的子圖。生成樹是指一個連通的無圈圖，最小樹是指一個連通圖的子圖。
2、對連通圖進行遍歷，過程中所經過的邊和頂點的組合可看做是一棵普通樹，通常稱為生成樹。在圖論的數(shù)學領域中，如果連通圖G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹(SpanningTree)。生成樹是連通圖的包含圖中的所有頂點的極小連通子圖。圖的生成樹不惟一。
3、那么，對于一張n個點帶權圖，它的生成樹就是用其中的n-1條邊來連接這n個點，那么最小生成樹就是n-1條邊的邊權之和最小的一種方案，簡單的理解，就是用讓這張圖只剩下n-1條邊，同時這n-1條邊的邊權總和最小。紅邊即為此圖的最小生成樹。樹形圖的概念 無圈且連通的無向圖稱為樹。
4、生成樹是原圖的極小連通子圖，包含原圖所有n個節(jié)點，并且保持圖連通的同時，邊最少。一個有n個頂點的完全圖其生成樹有n-1條邊。生成樹中頂點數(shù)和邊數(shù)分別為n，n-1。
