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

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

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