W-,3，n-的支配問題與二部圖的弧的公有性研究.pdf

1、圖論是研究由線連接的點集的理論。圖論是組合數(shù)學(xué)的一個重要分支，同時也是離散數(shù)學(xué)的一個重要組成部分。隨著計算機科學(xué)與數(shù)學(xué)的發(fā)展，圖論已經(jīng)成為人們研究自然科學(xué)以及社會科學(xué)的一個重要工具。 圖的支配問題是近年來圖論中一個比較活躍的研究領(lǐng)域。圖的支配問題的研究不僅具有很重要的理論意義，在優(yōu)化理論、通訊網(wǎng)絡(luò)的設(shè)計與分析、社會科學(xué)、計算復(fù)雜性和算法設(shè)計等許多領(lǐng)域也有很重要的應(yīng)用背景。 圖的支配數(shù)問題在網(wǎng)絡(luò)設(shè)計中有許多應(yīng)用。比如在一個

2、通訊網(wǎng)絡(luò)的一些節(jié)點上放置發(fā)射器，要求每個發(fā)射器的節(jié)點一定和某個發(fā)射器的節(jié)點有一個直接的通訊線路。如何選擇節(jié)點，使得放置的發(fā)射器的數(shù)目最小，這就是一個支配數(shù)問題。 計算圖的支配數(shù)問題屬于NP-完全問題，因此至今只有少數(shù)圖的支配數(shù)被找到并證明。本文對Kn(o)del圖W3,n的支配數(shù)γ(W3,n)及其密切相關(guān)的PaCking數(shù)ρ(W3,n)進行了較深入的研究。證明了每個圈連通的有向完全二部圖有一條公有弧并提出兩個問題：(1)假設(shè)C是