圖的支配臨界問(wèn)題研究.pdf

1、圖論是組合數(shù)學(xué)的重要分支.圖論的廣泛應(yīng)用，促進(jìn)了它自身的發(fā)展.尤其是近幾十年來(lái)，隨著計(jì)算機(jī)技術(shù)的出現(xiàn)和進(jìn)步，圖論理論有了飛速的發(fā)展并取得了驚人的成績(jī). 圖的支配問(wèn)題是近年來(lái)圖論中一個(gè)比較活躍的研究領(lǐng)域.圖的支配臨界問(wèn)題是其中一類重要問(wèn)題，它在網(wǎng)絡(luò)設(shè)計(jì)中有許多實(shí)際應(yīng)用。對(duì)于圖G=(V，E)的頂點(diǎn)集V的子集S，如果對(duì)V中每個(gè)頂點(diǎn)或者在S中，或者與S中的某個(gè)頂點(diǎn)相鄰，則稱集合S是圖G的一個(gè)支配集.圖G的最小支配集元素的個(gè)數(shù)稱為其支配數(shù)，記為γ

2、(G).如果圖G的支配集S中的每個(gè)頂點(diǎn)至少與S中的另一個(gè)頂點(diǎn)相鄰，則S稱為圖G的一個(gè)全支配集.圖G的最小全支配集元素的個(gè)數(shù)稱為其全支配數(shù)，記為γt(G). 本文設(shè)計(jì)了計(jì)算圖的支配數(shù)及其相關(guān)問(wèn)題的算法，利用該算法構(gòu)造出了一類k-(γ，2)-邊臨界圖，并給出了k-(γ，2)-邊臨界圖最小邊數(shù)的一個(gè)上界.然后對(duì)直徑為2的4-γt-點(diǎn)臨界圖進(jìn)行了研究，并成功的構(gòu)造出了一個(gè)直徑為2的4-γt-點(diǎn)臨界圖，在此基礎(chǔ)上又進(jìn)一步構(gòu)造出了一類k-