本文關(guān)鍵詞：計(jì)算代數(shù)方法在圖論中的幾個(gè)應(yīng)用，由筆耕文化傳播整理發(fā)布。

【摘要】：圖論中許多計(jì)數(shù)問(wèn)題一般涉及的都是求極小或極大值的問(wèn)題,而且大多數(shù)是限制在某些特殊類(lèi)型圖的范圍采用優(yōu)化的方法來(lái)解決的.對(duì)于一般有限圖G的支配集問(wèn)題、邊覆蓋問(wèn)題、強(qiáng)邊著色問(wèn)題、星著色問(wèn)題和2距離著色問(wèn)題,本學(xué)位論文首先引入κ-支配集問(wèn)題,κ-邊覆蓋問(wèn)題,κ-強(qiáng)邊著色問(wèn)題,κ-星著色問(wèn)題,κ-2距離著色問(wèn)題,并建立由多元多項(xiàng)式方程組給出的與每個(gè)κ-計(jì)數(shù)問(wèn)題相對(duì)應(yīng)的代數(shù)模型；其次,運(yùn)用計(jì)算代數(shù)中的Grobner基方法給出每個(gè)多元多項(xiàng)式方程組模型的解的存在性的有效判別準(zhǔn)則；在每個(gè)多元多項(xiàng)式方程組模型的解的存在性確定的前提下,用Grobner基方法給出具體的求解方案,并用計(jì)算機(jī)代數(shù)程序MAPLE給出驗(yàn)證實(shí)例；最后由此給出求解對(duì)應(yīng)的極大與極小值問(wèn)題的具體步驟. 由于計(jì)算代數(shù)原理,特別是關(guān)于多元多項(xiàng)式理想的Grobner基原理和方法,已經(jīng)成為數(shù)學(xué)領(lǐng)域中處理涉及可交換多元多項(xiàng)式有關(guān)問(wèn)題的強(qiáng)有力工具,而使用諸如MAPLE, CoCoA, MACAULAY中任何一個(gè)成熟的計(jì)算機(jī)代數(shù)系統(tǒng),都可有效地計(jì)算出一個(gè)Grobner基,因此本學(xué)位論文的研究工作對(duì)于用計(jì)算代數(shù)方法解決圖論中其它類(lèi)似的計(jì)數(shù)問(wèn)題也可提供進(jìn)一步的可行性依據(jù)和可參考途徑.
【關(guān)鍵詞】：圖 計(jì)算代數(shù) 支配集 邊覆蓋 強(qiáng)邊著色 星著色 2距離著色 Gr(o|")bner基
【學(xué)位授予單位】：海南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-8
• 引言8-10
• 1 預(yù)備知識(shí)10-17
• 1.1 圖論中的基本定義10-11
• 1.2 多項(xiàng)式理想的Grobner基11-17
• 2 圖的κ-支配集問(wèn)題與Grobner基求解17-26
• 2.1 支配集的預(yù)備知識(shí)17-18
• 2.2 κ-支配集問(wèn)題的多項(xiàng)式方程組模型與Grobner基求解18-20
• 2.3 求圖的支配數(shù)和極小支配集的計(jì)算方法20-21
• 2.4 MAPLE驗(yàn)證舉例21-26
• 3 圖的κ-邊覆蓋問(wèn)題與Grobner基求解26-33
• 3.1 邊覆蓋集的預(yù)備知識(shí)26-27
• 3.2 邊覆蓋問(wèn)題的多項(xiàng)式方程組模型27-28
• 3.3 κ-邊覆蓋存在性的Grobner基判別28-29
• 3.4 求圖的κ-邊覆蓋,邊覆蓋數(shù)與極小邊覆蓋的Grobner基方法29-30
• 3.5 MAPLE驗(yàn)證舉例30-33
• 4 圖的κ-強(qiáng)邊著色問(wèn)題與Grobner基求解33-41
• 4.1 強(qiáng)邊著色的預(yù)備知識(shí)33
• 4.2 κ-強(qiáng)邊著色問(wèn)題的多項(xiàng)式方程組模型33-36
• 4.3 求κ-強(qiáng)邊著色的Grobner基方法36
• 4.4 求圖的強(qiáng)邊著色數(shù)的計(jì)算方法36
• 4.5 MAPLE驗(yàn)證舉例36-41
• 5 圖的κ-星著色問(wèn)題與Grobner基求解41-47
• 5.1 星著色的預(yù)備知識(shí)41
• 5.2 κ-星著色問(wèn)題的多項(xiàng)式方程組模型41-44
• 5.3 求κ-星著色的Grobner基方法44
• 5.4 求圖的星著色數(shù)的計(jì)算方法44
• 5.5 MAPLE驗(yàn)證舉例44-47
• 6 圖的κ-2距離著色問(wèn)題與Grobner基求解47-55
• 6.1 2距離著色的預(yù)備知識(shí)47
• 6.2 2距離著色問(wèn)題的代數(shù)不等式方程組模型47-48
• 6.3 κ-2距離著色問(wèn)題的多項(xiàng)式方程組模型48-50
• 6.4 κ-2距離著色存在性的Grobner基判別50-51
• 6.5 求κ-2距離著色的Grobner基方法51
• 6.6 求圖的κ-2距離著色數(shù)的計(jì)算方法51-52
• 6.7 MAPLE驗(yàn)證舉例52-55
• 參考文獻(xiàn)55-57
• 碩士期間提交和發(fā)表論文情況57-58
• 后記58

【相似文獻(xiàn)】

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

1 劉桂真;鄧小鐵;徐常青;;系列平行圖的除V*外的邊覆蓋劃分[J];中國(guó)科學(xué)(A輯:數(shù)學(xué));2006年06期

2 王紀(jì)輝;;關(guān)于近似二部圖邊覆蓋染色的一個(gè)充分條件[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2006年01期

3 宋慧敏,劉桂真;邊覆蓋臨界圖的一些性質(zhì)[J];數(shù)學(xué)進(jìn)展;2004年01期

4 歐陽(yáng)章東;黃元秋;任俊峰;;圖的邊覆蓋數(shù)、圍長(zhǎng)和最大虧格[J];內(nèi)蒙古師范大學(xué)學(xué)報(bào)(自然科學(xué)漢文版);2008年03期

5 張福基,林詒勛;圖的兩類(lèi)一般多項(xiàng)式[J];數(shù)學(xué)學(xué)報(bào);1985年01期

6 袁春華;馮立華;邢順來(lái);;關(guān)于圖的bondage數(shù)的一點(diǎn)注記[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2006年04期

7 閔安共;;彼得松圖的幾個(gè)性質(zhì)[J];數(shù)學(xué)學(xué)習(xí)與研究(教研版);2009年10期

8 ;[J];;年期

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

1 尹杰杰;計(jì)算代數(shù)方法在圖論中的幾個(gè)應(yīng)用[D];海南大學(xué);2015年

  本文關(guān)鍵詞：計(jì)算代數(shù)方法在圖論中的幾個(gè)應(yīng)用，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：286340