圖的兩種控制數(shù)中相關(guān)問題的研究.pdf

1、自歐拉發(fā)表第一篇圖論論文以來，圖的理論逐漸建立并完善和豐富起來.其中，圖的控制理論在圖論中占據(jù)著舉足輕重的地位.許多實(shí)際問題可以用圖進(jìn)行建模，將其轉(zhuǎn)化為計算圖的控制數(shù)問題來解決.除此之外，圖的控制理論對運(yùn)籌學(xué)、網(wǎng)絡(luò)理論、社會科學(xué)等學(xué)科的發(fā)展有著深遠(yuǎn)的影響.因此，近年來，關(guān)于圖的控制數(shù)理論的研究成果層出不窮.由于確定任意圖的控制數(shù)問題是一個NP-完全問題，于是，確定控制數(shù)的盡可能好的上界和下界就具有非常重要的意義，進(jìn)而可以繼續(xù)研究達(dá)到上下

2、界時極值圖的結(jié)構(gòu)問題.
　　本文主要討論了給定控制數(shù)的連通二部圖極圖的結(jié)構(gòu)，以及倍圖的全符號點(diǎn)控制數(shù)達(dá)到上界時圖的結(jié)構(gòu)問題.
　　第一章介紹了圖論這門分支的歷史背景和圖的控制數(shù)的發(fā)展進(jìn)程；第二章介紹了圖的基本概念和符號表示，為后兩章做準(zhǔn)備工作；第三章研究了給定控制數(shù)的連通二部圖極圖的結(jié)構(gòu)問題，刻畫了當(dāng)控制數(shù)大于等于3時邊數(shù)達(dá)到極值時的連通二部圖所滿足的特性；第四章研究了倍圖的全符號點(diǎn)控制問題，利用圖的全符號點(diǎn)控制數(shù)的性質(zhì)，刻