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

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

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

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

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