矩陣在多部圖和最小生成樹中的應用.pdf

1、在二部圖和最小生成樹問題的研究中，產(chǎn)生了一些經(jīng)典算法。然而，隨著科技的發(fā)展，二部圖和最小生成樹的一些原有的算法不能滿足發(fā)展的需求，促使人們尋找多部圖和最小生成樹的新算法。應用其他學科完成這項工作，不失為一個好的策略。
　　矩陣論，作為一個古典而又具有新鮮內(nèi)容的學科，已經(jīng)與圖論的研究密不可分。因為圖中頂點與邊之間的關系可以用矩陣來描述,因此，通過圖的矩陣表示，可以清楚地觀察到圖的結(jié)構(gòu)，能準確地計算出圖中一些重要數(shù)據(jù)。
　　基于

2、矩陣與圖的關系，本文利用矩陣的方法，分別給出多部圖和最小生成樹的矩陣算法，其主要內(nèi)容如下：
　?。?）提出有關部圖和通匹配的定義，構(gòu)造k部圖的鄰接矩陣，利用優(yōu)先匹配度較小頂點的原理，得到部圖矩陣算法的思想、步驟；并用歸納的方法，證明了算法的正確性。同時，對算法的復雜性加以分析，得到此處設計的部圖矩陣算法比經(jīng)典的匈牙利算法復雜度低，最后用實例說明矩陣算法的有效性。
　　（2）利用避圈的原理，得到最小生成樹矩陣算法的思想、步驟；