點(diǎn)可遷圖的全約束數(shù)和有效全控制.pdf

1、霉短’砍學(xué)點(diǎn)可遷圖的全約束數(shù)和有效全控制密級(jí)：保密期限：TheTotalBondageNumbersandEfficientTotalDominationsofVertex—transitiveGraphs學(xué)號(hào)姓名學(xué)位類別學(xué)科專業(yè)指導(dǎo)教師完成時(shí)間A15201024李露理學(xué)碩士應(yīng)用數(shù)學(xué)胡夫濤副教授2018年3月摘要本篇論文，主要考慮的是非空簡(jiǎn)單圖通常所說(shuō)的圖即包含有向圖也包含無(wú)向圖，在圖論中沒(méi)有明確的規(guī)定圖的符號(hào)一般地，用G=(KE)來(lái)表

2、示圖，其中V=v(a)表示圖G的頂點(diǎn)集以及E=E(G)表示圖G的邊集頂點(diǎn)對(duì)(Ⅱ，勘)表示的是從頂點(diǎn)他指向頂點(diǎn)V的一條有向邊，注意當(dāng)(u，u)，(V，亂)∈E時(shí)，則可把這兩條有向邊當(dāng)成一條無(wú)向邊，用UV表示設(shè)圖G是有向圖，如果G的每條邊(U，V)都有(V，u)∈E則圖G就稱為無(wú)向圖設(shè)D為圖G的頂點(diǎn)子集，如果對(duì)于任意一個(gè)不在D當(dāng)中的頂點(diǎn)V都有U∈D使得(“，V)∈E，則稱D為圖G的控制集圖G的控制數(shù)是指最小控制集所含頂點(diǎn)的個(gè)數(shù)，通常用7(G

3、)來(lái)表示設(shè)S為每個(gè)頂點(diǎn)入度大于零的圖G的頂點(diǎn)子集，如果對(duì)于每一個(gè)頂點(diǎn)u∈v(a)都有u∈D使得(u，V)∈E，則稱S為圖G的全控制集圖G的全控制數(shù)是指在最小全控制集所含有頂點(diǎn)數(shù)，通常用y(a)來(lái)表示圖G的約束數(shù)是指刪除G中最少邊集的數(shù)目使得圖G的控制數(shù)增加，用b(a)表示圖G的全約束數(shù)是指刪除G中最少邊集的數(shù)目使得圖G的全控制數(shù)增加，用bt(G)表示在這篇論文中，我們建立了點(diǎn)可遷圖的全約束數(shù)的一個(gè)緊的下界(通常下界比上界難很多)，通過(guò)研

4、究全約束數(shù)和有效全控制數(shù)之間的關(guān)系，我們也得到了正則圖全約束數(shù)的一個(gè)上界如果圖有有效全控制集，在無(wú)向圖情形下給出了緊的上下界，在有向圖情況下，完全確定了全約束數(shù)的精確值作為應(yīng)用推廣，我們也研究了一些循環(huán)圖、哈拉里圖、網(wǎng)格網(wǎng)絡(luò)的運(yùn)算，通過(guò)它們有效控制集存在的特征，研究得到它們的全約束數(shù)另外對(duì)于一些特殊的圖，例如超級(jí)立方體我們也得到了它的全約束數(shù)的上下界實(shí)際應(yīng)用中的圖模型大都是點(diǎn)可遷圖，論文取得的成果，加深了點(diǎn)可遷圖在控制理論上的認(rèn)識(shí)，在實(shí)