矩陣在多部圖和最小生成樹中的應(yīng)用.pdf

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

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