本文選題：控制數(shù)　切入點(diǎn)：填充數(shù)　出處：《蘭州大學(xué)》2015年博士論文　論文類型：學(xué)位論文

【摘要】：圖的控制數(shù)是圖的基本的不變量之一,也是反映網(wǎng)絡(luò)性能的一個(gè)參數(shù).圖的約束數(shù)是指讓圖的控制數(shù)增大所需刪除的最少邊的數(shù)目.它能衡量在通信線路發(fā)生故障情況下互聯(lián)網(wǎng)絡(luò)脆弱性.然而,圖的控制數(shù)和約束數(shù)的計(jì)算已經(jīng)分別被證明是NP-完全和NP-困難問題.許多學(xué)者都致力于圖的最小控制集與最小約束邊集的結(jié)構(gòu)和性質(zhì)的研究,以及計(jì)算特殊圖類的控制數(shù)與約束數(shù)的精確值或者給出它們界.一般來說,計(jì)算一個(gè)圖的約束數(shù)比計(jì)算其控制數(shù)更為困難.本論文的研究內(nèi)容包括樹的控制問題和強(qiáng)乘積圖的約束數(shù).其中,對(duì)樹控制問題的研究又為強(qiáng)乘積圖約束數(shù)的計(jì)算提供一定的理論支撐.本文共分為五章.第一章首先介紹一些本文用到的基本概念和記號(hào).然后分別介紹樹的構(gòu)造與刻畫和乘積圖約束數(shù)的研究背景,問題的提出以及研究進(jìn)展.最后介紹本文所得到的主要結(jié)果.在第二章中,根據(jù)與最小控制集的關(guān)系,我們把圖的頂點(diǎn)可分為普遍點(diǎn)、空白點(diǎn)和可變點(diǎn)三類.(圖的普遍點(diǎn)是指屬于圖所有最小控制集的點(diǎn),空白點(diǎn)是指不屬于圖任何最小控制集的點(diǎn),可變點(diǎn)是指既不是普遍也不是空白的點(diǎn).)我們通過定義了9種圖的操作分別給出了僅包含可變點(diǎn),僅包含非普遍點(diǎn)和僅包含非可變點(diǎn)的樹的構(gòu)造.在第三章中,我們給出了一棵樹的約束數(shù)為2的一個(gè)充分條件和一個(gè)充要條件：如果樹T的頂點(diǎn)數(shù)至少為3且它的所有頂點(diǎn)都是可變的,那么T的約束數(shù)為2；非平凡樹T的約束數(shù)為2當(dāng)且僅當(dāng)T的所有γ-可孤立點(diǎn)構(gòu)成T的一個(gè)最大2-填充,(圖的一個(gè)頂點(diǎn)被稱為是γ-可孤立點(diǎn),如果去掉該點(diǎn)后圖的控制數(shù)恰好減少1).另外,我們還得到了一個(gè)圖和一棵樹的強(qiáng)乘積圖最小控制集的一些性質(zhì).在第四章中,我們得到兩條路的強(qiáng)乘積圖約束數(shù)的精確值.即,對(duì)任意兩個(gè)正整數(shù)m≥2和訖≥2,若(r(m),r(n))=(1,1)或(3,3)則b(Pm(?)Pn)=7-r(m)-r(n)；否則b(Pm(?)Pn)=6-r(m)-r(n)其中,r(T)是一個(gè)關(guān)于正整數(shù)t的函數(shù),定義為r(t)=1若t≡1(mod 3)；r(t)=2若t≡2(mod 3)；r(t)=3若t三0(mod 3).在第五章中,我們得到一個(gè)完全圖與一條路的強(qiáng)乘積圖約束數(shù)的精確值.即,對(duì)任意兩個(gè)正整數(shù)m≥1和n≥2,有b(Km(?)Pn)=[m/2]若n≡0(mod 3)；m若n≡2(mod 3)；[3m/2]若n≡1(mod 3)在這個(gè)結(jié)果的基礎(chǔ)上,我們進(jìn)一步得到了一個(gè)完全圖和一類特殊的星狀樹的強(qiáng)乘積圖約束數(shù)的精確值.在第六章中,我們給出了一些在不同條件下一個(gè)非空?qǐng)D與一棵樹的強(qiáng)乘積圖約束數(shù)的上界.并且引用第五章的結(jié)果作為例子,指出我們所得到的上界都是緊的.
[Abstract]:The domination number is one of the basic invariants of graphs, but also reflect the performance of the network. A parameter constraint graph number refers to the number of graph control the minimum number of edges required increase delete. It can measure the failures of Internet vulnerability in the communication line. However, the number and the number of control calculation the constraint graph has been proved to be NP- complete and NP- problems. The structure and properties of the minimum dominating set and minimal constraint, many scholars are committed to the edges of the graph set, and the exact value or give them control number and the bounded number constraint computation of special graphs. In general, the number of constraints is calculated a map of the calculation of the number ratio control is more difficult. The number of constraints is the research contents of this thesis include the tree control problem and strong product graphs. Among them, the calculation of the research provide some control problems for tree and strong product graphs of the number of constraints On the support. This paper is divided into five chapters. The first chapter introduces some basic concepts and mark used in this paper. The research background and then introduces the structure and the number of product description and constraint tree, the progress and the problem of the research. Finally, the main results obtained in this paper. In the second chapter, according to the relationship with the minimum control set, we put the vertices of a graph can be divided into common point, point blank and variable point three. (generally refers to the point of graph graph all minimum dominating set point, point blank that does not belong to any minimum set point control chart, variable point is that neither universal nor blank the point.) we defined 9 kinds of graph operations are given only contain variable, contains only non common point and contains only non variable point tree structure. In the third chapter, we give the number of constraints of a tree is 2 a sufficient condition and a 涓厖瑕佹潯浠訛細(xì)濡傛灉鏍?wèi)T鐨勯《鐐規(guī)暟鑷沖皯涓，

本文編號(hào)：1592483