圖的函數(shù)控制數(shù).pdf

1、圖的控制理論是圖論中的一個重要分支,在編碼理論,計算機科學(xué),通信網(wǎng)絡(luò),社會網(wǎng)絡(luò)等學(xué)科中都有廣泛的應(yīng)用。隨著計算機科學(xué)興起及函數(shù)方法的加入,使得圖的控制理論成為圖論近幾十年發(fā)展最快的領(lǐng)域之一.1998年美國圖論學(xué)者Haynes等人出版了兩部專著,較為系統(tǒng)地綜述了幾千篇關(guān)于函數(shù)控制數(shù)的研究成果.
　　 本文所做工作主要包括以下二個部分:(1)確定幾類函數(shù)控制數(shù)的界(2)某些特殊圖的函數(shù)控制參數(shù)值的確定.
　　 ★在第一章,我

2、們給出了本論文要用的相關(guān)概念及圖的函數(shù)控制數(shù)的研究概況.
　　 ★在第二章,我們得到了圖的反符號圈控制數(shù)的上界,并且給出了幾種特殊圖的反符號圈控制數(shù),主要得到了下面幾個結(jié)果:
　　 ·對任意的圖G都有γ1rsc(G)≤2|V(G)|-|E(G)|-2且等式成立當(dāng)且僅當(dāng)G是樹.
　　 ·γ1rsc(Kn)=2[n/2]-(n2).
　　 ·γ1rsc(Wn+1)=-2[n/4].
　　 ·γ1rsc

3、(Kn,m)=mn-min{(m-1)n,m(n-1)}.
　　 ★在第三章,給出了圖的分?jǐn)?shù)劃分?jǐn)?shù)的界:
　　 ·對任意一個n階圖G,均有γf(G)df(G)≤n.
　　 ·對任意一個最小度為δ的圖G,均有δ≤df(G)≤δ+1.
　　 ★在第四章,通過反證法及構(gòu)造全符號函數(shù)的方法給出了完全圖的全符號控制數(shù)的精確值:γ*s(Kn)=[n/2].
　　 ★在第五章,給出圖的全減符號控制數(shù)的上界.應(yīng)用