本文關(guān)鍵詞：若干圖類(lèi)的全符號(hào)控制數(shù)的研究

  更多相關(guān)文章： 全符號(hào)控制數(shù) 笛卡爾乘積圖 路徑圖 圈圖

【摘要】：圖的符號(hào)控制是圖論的一個(gè)重要的研究方向,不僅僅在實(shí)際生活中有著非常廣泛的應(yīng)用,例如,發(fā)射基站的選址、計(jì)算機(jī)通訊網(wǎng)絡(luò)和群決策等,而且人們也可以在計(jì)算的復(fù)雜性和算法設(shè)計(jì)、優(yōu)化理論、通訊網(wǎng)絡(luò)設(shè)計(jì)與分析等方面應(yīng)用圖的控制理論。我們研究圖的符號(hào)控制尤其是一些特殊圖的符號(hào)控制問(wèn)題可以為解決一般的NP-困難問(wèn)題提供重要的借鑒,具有較為重要的意義,圖的控制數(shù)的研究也因此一直受到廣大學(xué)者的關(guān)注。本文主要研究路徑圖Pm與圈圖Cn的交圖的全符號(hào)控制數(shù)。本文考慮的圖G均為有限簡(jiǎn)單連通圖,根據(jù)Pm□Cn的點(diǎn)和邊鄰域的特點(diǎn)(在全符號(hào)控制研究中,頂點(diǎn)的鄰域中包含邊,邊的鄰域中也包含頂點(diǎn)),給出圖Pm□Cn的全符號(hào)控制數(shù)較好的上下界。首先,根據(jù)前人的重要結(jié)論,對(duì)于任意圖G,如果圖G頂點(diǎn)的最小度為δ(G),最大度為△(G),頂點(diǎn)數(shù)為|V(G)|,邊數(shù)為|E(G)|,那么G的全符號(hào)控制數(shù)為：并且這個(gè)下界是可達(dá)的,其中ρ(s)表示s的奇偶性,即如果s是奇數(shù)時(shí),則ρ(s)=奇數(shù),如果s是偶數(shù)時(shí),則ρ(s)=偶數(shù)。對(duì)于Pm□Cn,根據(jù)上式可以得到γs*(Pm□Cn)≥0,由于Pm□Cn的點(diǎn)和邊鄰域的特性,我們可知其全符號(hào)控制數(shù)γs*(Pm□Cn)的下界可以比零更大一些。利用解析法證明Pm□Cn的全符號(hào)控制數(shù)γs*(Pm□Cn)的下界,該下界比一般圖G的全符號(hào)控制數(shù)γs*(G)的下界大。然后,利用計(jì)算機(jī)構(gòu)造證明給出圖Pm□Cn的全符號(hào)控制數(shù)較好的上界。基于Pm□Cn點(diǎn)和邊鄰域的特點(diǎn),設(shè)計(jì)有效的分支限界條件,研制計(jì)算機(jī)算法,構(gòu)造全符號(hào)控制函數(shù),計(jì)算γs*(Pm□Cn)的上界。最終,我們給出圖Pm□Cn的全符號(hào)控制數(shù)。
【關(guān)鍵詞】：全符號(hào)控制數(shù) 笛卡爾乘積圖 路徑圖 圈圖
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O157.5
【目錄】：

• 摘要5-7
• ABSTRACT7-11
• 第1章 緒論11-18
• 1.1 控制數(shù)問(wèn)題的研究背景和意義11-14
• 1.1.1 研究背景11-13
• 1.1.2 研究意義13-14
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀及發(fā)展動(dòng)態(tài)14-17
• 1.2.1 圖的符號(hào)(點(diǎn))控制數(shù)14-15
• 1.2.2 圖的符號(hào)邊控制數(shù)15-16
• 1.2.3 圖的全符號(hào)控制數(shù)16-17
• 1.3 本文主要工作與結(jié)構(gòu)安排17-18
• 第2章 圖的控制理論及其應(yīng)用18-26
• 2.1 圖的基本概念18-19
• 2.2 圖的控制理論的基本概念與性質(zhì)19-21
• 2.3 圖的控制問(wèn)題在實(shí)際中的應(yīng)用21-26
• 2.3.1 安排考試時(shí)間問(wèn)題22
• 2.3.2 計(jì)算機(jī)通訊問(wèn)題22-23
• 2.3.3 選址問(wèn)題23-24
• 2.3.4 群決策問(wèn)題24
• 2.3.5 研究社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)和屬性24-25
• 2.3.6 影響最大化問(wèn)題25-26
• 第3章 路徑與圈交圖的全符號(hào)控制數(shù)研究26-43
• 3.1 路徑與圈交圖的相關(guān)概念26-27
• 3.1.1 路徑圖26
• 3.1.2 圈圖26
• 3.1.3 笛卡爾乘積圖26-27
• 3.2 路徑與圈交圖的相關(guān)結(jié)論27-28
• 3.2.1 點(diǎn)控制27
• 3.2.2 邊控制27-28
• 3.2.3 全控制28
• 3.3 路徑與圈交圖的全符號(hào)控制數(shù)的界限28-43
• 3.3.1 路徑與圈交圖的全符號(hào)控制數(shù)的下界29-31
• 3.3.2 路與圈交圖的全符號(hào)控制數(shù)的上界31-43
• 第4章 總結(jié)與展望43-45
• 4.1 總結(jié)43-44
• 4.2 本課題今后需要進(jìn)一步研究的地方44-45
• 參考文獻(xiàn)45-50
• 攻讀碩士學(xué)位期間發(fā)表論文情況50-51
• 致謝51

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 徐保根;關(guān)于圖的符號(hào)星控制數(shù)[J];華東交通大學(xué)學(xué)報(bào);2004年04期

2 徐保根;關(guān)于n階圖的最小減控制數(shù)[J];華東交通大學(xué)學(xué)報(bào);2005年02期

3 袁春華;劉堅(jiān);馮立華;;圖的占優(yōu)控制數(shù)與符號(hào)k-子控制數(shù)的幾個(gè)界[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年02期

4 熊坤;蘇健基;;幾類(lèi)圖的符號(hào)星控制數(shù)[J];廣西科學(xué);2007年03期

5 孫桂艷;喬永濤;;關(guān)于圖的減控制數(shù)[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年04期

6 趙金鳳;徐保根;趙華;帥春萍;;關(guān)于圖的兩類(lèi)邊控制數(shù)[J];華東交通大學(xué)學(xué)報(bào);2008年05期

7 徐保根;李春華;;圖的符號(hào)星k控制數(shù)[J];純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué);2009年04期

8 周仲旺;;偶階完全圖的點(diǎn)-邊全符號(hào)控制數(shù)[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2010年01期

9 黃中升;;圖的逆符號(hào)邊全控制的性質(zhì)[J];赤峰學(xué)院學(xué)報(bào)(自然科學(xué)版);2010年06期

10 李艷坡;高明晶;王宏麗;;圖的負(fù)邊全控制數(shù)[J];河北師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年05期

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前10條

1 ;今一季度全市安全生產(chǎn)事故通報(bào)[N];漢中日?qǐng)?bào);2007年

2 記者 宋蘭蘭;我市首次曬“三公”經(jīng)費(fèi)[N];長(zhǎng)江日?qǐng)?bào);2011年

3 粟時(shí)勇 記者　黃先明;“人員控制數(shù)”破終身制[N];四川日?qǐng)?bào);2006年

4 科訊;引進(jìn)院士不計(jì)入結(jié)構(gòu)比例控制數(shù)[N];廣東科技報(bào);2005年

5 記者 馬曉芳;我區(qū)實(shí)行事業(yè)編制分類(lèi)管理[N];寧夏日?qǐng)?bào);2009年

6 記者　呂玲;逾六成醫(yī)療費(fèi)超標(biāo)[N];福州日?qǐng)?bào);2006年

7 陳會(huì)揚(yáng);福建患者醫(yī)藥費(fèi)用偏高[N];健康報(bào);2006年

8 記者 車(chē)?yán)?去年我市“三公經(jīng)費(fèi)”支出3.33億[N];長(zhǎng)江日?qǐng)?bào);2012年

9 徐侃;把安全生產(chǎn)工作抓實(shí)抓細(xì)[N];安慶日?qǐng)?bào);2009年

10 陸天榮;車(chē)禍猛于虎[N];蘇州日?qǐng)?bào);2006年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前8條

1 單而芳;圖的控制數(shù)及其相關(guān)參數(shù)[D];上海大學(xué);2005年

2 蔣紅星;圖的幾類(lèi)控制參數(shù)研究[D];上海大學(xué);2009年

3 趙衍才;圖的某些控制參數(shù)的計(jì)算[D];上海大學(xué);2011年

4 李寧;圖的控制問(wèn)題研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

5 王超;圖的配對(duì)控制數(shù)和彩虹控制數(shù)研究[D];華東師范大學(xué);2015年

6 呂長(zhǎng)虹;[D];南京大學(xué);2000年

7 趙敏;幾類(lèi)圖的控制參數(shù)的理論與算法[D];上海大學(xué);2006年

8 曹永昌;圖的穩(wěn)定性的相關(guān)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2009年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 陳悅;圖的幾類(lèi)K控制數(shù)[D];華東交通大學(xué);2012年

2 孟弦;基于距離條件下的圖參數(shù)與圖結(jié)構(gòu)研究[D];華中師范大學(xué);2015年

3 杜娟;圖的符號(hào)控制數(shù)[D];山西大學(xué);2014年

4 張利賢;圖的參數(shù)控制研究[D];浙江師范大學(xué);2015年

5 黃海圓;笛卡爾乘積圖的配對(duì)控制數(shù)[D];浙江師范大學(xué);2015年

6 于涵;圖的兩種控制數(shù)中相關(guān)問(wèn)題的研究[D];哈爾濱師范大學(xué);2015年

7 曹惠萍;若干圖類(lèi)的全符號(hào)控制數(shù)的研究[D];大連海事大學(xué);2016年

8 廖萬(wàn)生;圖的減邊控制數(shù)[D];暨南大學(xué);2008年

9 崔玉燕;樹(shù)的減邊控制數(shù)[D];暨南大學(xué);2009年

10 尹傳勇;關(guān)于圖的幾類(lèi)控制數(shù)的界[D];華中師范大學(xué);2002年

，

本文編號(hào)：567019