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

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

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