發(fā)布時間：2020-11-17 13:28

　　 本篇論文,主要考慮的是非空簡單圖.通常所說的圖即包含有向圖也包含無向圖,在圖論中沒有明確的規(guī)定圖的符號.一般地,用G =(V,E)來表示圖,其中V=V(G)表示圖G的頂點集以及E= E(G)表示圖G的邊集.頂點對(u,v)表示的是從頂點u指向頂點v的一條有向邊,注意當(dāng)(u,v),(v,u)∈E時,則可把這兩條有向邊當(dāng)成一條無向邊,用uv表示.設(shè)圖G是有向圖,如果G的每條邊(u,v)都有(v,u)∈E則圖G就稱為無向圖.設(shè)D為圖G的頂點子集,如果對于任意一個不在D當(dāng)中的頂點v都有u ∈D使得(u,v)∈E,則稱D為圖G的控制集.圖G的控制數(shù)是指最小控制集所含頂點的個數(shù),通常用γ(G)來表示.設(shè)S為每個頂點入度大于零的圖G的頂點子集,如果對于每一個頂點v ∈ V(G)都有u∈D使得(u,v)∈E,則稱S為圖G的全控制制集.圖G的全控制數(shù)是指在最小全控制集所含有頂點數(shù),通常用γ_t(G)來表示.圖G的約束數(shù)是指刪除G中最少邊集的數(shù)目使得圖G的控制數(shù)增加,用b(G)表示.圖G的全約束數(shù)是指刪除G中最少邊集的數(shù)目使得圖G的全控制數(shù)增加,用b_t(G)表示.在這篇論文中,我們建立了點可遷圖的全約束數(shù)的一個緊的下界(通常下界比上界難很多),通過研究全約束數(shù)和有效全控制數(shù)之間的關(guān)系,我們也得到了正則圖全約束數(shù)的一個上界.如果圖有有效全控制集,在無向圖情形下給出了緊的上下界,在有向圖情況下,完全確定了全約束數(shù)的精確值.作為應(yīng)用推廣,我們也研究了一些循環(huán)圖、哈拉里圖、網(wǎng)格網(wǎng)絡(luò)的運算,通過它們有效控制集存在的特征,研究得到它們的全約束數(shù).另外對于一些特殊的圖,例如超級立方體我們也得到了它的全約束數(shù)的上下界.實際應(yīng)用中的圖模型大都是點可遷圖,論文取得的成果,加深了點可遷圖在控制理論上的認(rèn)識,在實際網(wǎng)絡(luò)中的結(jié)果為人們在現(xiàn)實中應(yīng)用這些網(wǎng)絡(luò)提供了全控制容錯性的參考.
【學(xué)位單位】：安徽大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5
【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 圖論的由來和發(fā)展過程
    1.2 關(guān)于圖論的基本概念
    1.3 控制數(shù)和約束數(shù)的概念
第二章 全約束數(shù)和有效全控制
    2.1 引言
    2.2 初步的結(jié)果
    2.3 主要的結(jié)果
第三章 循環(huán)圖的全約束數(shù)和有效全控制集
    3.1 雙環(huán)網(wǎng)絡(luò)圖的有效全控制集和全約束數(shù)的上下界
    3.2 Harary圖的全約束數(shù)和有效全控制集
    3.3 其它的應(yīng)用
第四章 總結(jié)與展望
    4.1 總結(jié)
    4.2 展望
參考文獻
攻讀碩士學(xué)位期間科研情況及學(xué)術(shù)活動
致謝

【相似文獻】

相關(guān)期刊論文 前10條

1 李念祖;劉儒英;;非色唯一的連通頂點可遷圖的廣泛存在性[J];青海師范大學(xué)學(xué)報(自然科學(xué)版);2006年01期

2 歐見平,張�；�;點可遷圖中的正則因子(英文)[J];數(shù)學(xué)研究與評論;2004年03期

3 歐見平,張�；�;點可遷圖的頂點劃分[J];廈門大學(xué)學(xué)報(自然科學(xué)版);2003年01期

4 郭大昌;吳傳榮;;關(guān)于L.Lovase猜想[J];工業(yè)工程;1989年02期

5 鄧漢元;關(guān)于連通點可遷圖的色性[J];北京理工大學(xué)學(xué)報;1989年01期

6 李才恒;;距離可遷圖在笛卡爾積下封閉的條件[J];云南師范大學(xué)學(xué)報(自然科學(xué)版);1989年02期

7 歐見平;;點可遷圖的限制邊連通性[J];數(shù)學(xué)物理學(xué)報;2005年06期

8 劉儒英;李念祖;;連通的頂點可遷圖的色唯一性[J];應(yīng)用數(shù)學(xué);1991年02期

9 李念祖;劉念祖;劉儒英;;幾類非色唯一的連通頂點可遷圖[J];上海第二工業(yè)大學(xué)學(xué)報;2005年04期

10 王朝瑞,石民勇;點可遷圖中的兩個不相交的極大獨立點集(英文)[J];北京理工大學(xué)學(xué)報;1991年03期

相關(guān)博士學(xué)位論文 前1條

1 洪振木;某些網(wǎng)絡(luò)可靠性和有效性研究[D];中國科學(xué)技術(shù)大學(xué);2014年

相關(guān)碩士學(xué)位論文 前4條

1 李露;點可遷圖的全約束數(shù)和有效全控制[D];安徽大學(xué);2018年

2 張國春;擬可遷圖上滲流臨界概率的唯一性[D];首都師范大學(xué);2007年

3 王彥;一類與sierpi(?)ski地毯相關(guān)的擬可遷圖上的滲流模型[D];首都師范大學(xué);2007年

4 徐根玖;有向圖中若干問題的研究[D];西北工業(yè)大學(xué);2004年

本文編號：2887551