• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于Gr?bner基的圖動態(tài)染色求解方案

      2015-03-08 07:13:52何文峰張勇軍符一平

      何文峰,張勇軍,符一平

      ( 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院,海南 海口 570228)

      ?

      基于Gr?bner基的圖動態(tài)染色求解方案

      何文峰,張勇軍,符一平

      ( 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院,海南 ???570228)

      摘要:考察了一般有限連通圖的動態(tài)染色方案以及動態(tài)色數(shù),首先利用多元多項(xiàng)式方程組對其進(jìn)行建模,然后利用方程組對應(yīng)的Gr?bner基來判定方程組解存在性,進(jìn)而達(dá)到判定圖的動態(tài)染色方案的存在性的目的,最后給出求動態(tài)色數(shù)及相應(yīng)動態(tài)染色方案的方法,并給予實(shí)例驗(yàn)證.

      關(guān)鍵詞:動態(tài)染色; 動態(tài)色數(shù); Gr?bner基

      圖染色問題就是用最少種類的顏色對圖的點(diǎn)、邊、面以某種規(guī)則進(jìn)行染色,研究染色所用色數(shù)以及設(shè)計(jì)對應(yīng)的染色方案就成為圖染色的基本工作.近年來,隨著通信以及計(jì)算機(jī)技術(shù)方面的長足發(fā)展,對染色問題提出了更高的要求.在此背景之下,2001年Montgomery在文獻(xiàn)[1]中提出動態(tài)染色概念,同時證明了一般圖的動態(tài)色數(shù)上界為Δ+3.林越等在文獻(xiàn)[2]中得到平面圖的動態(tài)色數(shù)上界為5的結(jié)論,除此之外,還有一些學(xué)者對特殊圖的動態(tài)色數(shù)給予了研究,如文獻(xiàn)[1],[3-9]分別對多重完全圖、二部完全圖、完全圖、樹、k-正則圖、偽哈林圖、單圈圖及雙圈圖等特殊圖的動態(tài)色數(shù)進(jìn)行了研究.

      從以上研究的過程中可以發(fā)現(xiàn),幾類特殊圖和平面圖的動態(tài)染色的上界已經(jīng)研究的較清楚,但一般圖的動態(tài)色數(shù)還知之甚少.因此,筆者考察了一般有限連通圖的動態(tài)染色方案以及動態(tài)色數(shù),首先對其進(jìn)行多元多項(xiàng)式方程組建模,然后利用方程組對應(yīng)的Gr?bner基來判定方程組解的存在性,進(jìn)而達(dá)到判定圖的動態(tài)染色方案的存在性的目的,最后給出求動態(tài)色數(shù)的可行方法.

      1預(yù)備知識

      本文提到的圖G(V,E)均指n階連通圖,V(G)表示G(V,E)的頂點(diǎn)集,E(G)表示G(V,E)的邊集,

      N(v)表示G(V,E)中頂點(diǎn)v的鄰點(diǎn)集,dG(v)=d(v)=|N(v)|表示G(V,E)的頂點(diǎn)v的度.

      定義1 圖G(V,E)的動態(tài)d-染色是一個這樣的映射C:V(G)→C(d)={1,2,…,d},且滿足:

      定義2若圖G(V,E)存在動態(tài)d-染色,而不存在動態(tài)(d-1)-染色,那么就把d稱為圖G(E,V)的動態(tài)色數(shù),記為χd(G).

      定義3 設(shè)圖G(V,E)是一個有限的簡單連通圖,鄰接矩陣(AdjacencyMatrix)記為A=(aij)n×n,其中,

      2描述動態(tài)k-染色的多元多項(xiàng)式方程組的建立

      圖G(V,E)動態(tài)d-染色就是用顏色集{1,2,…,d}對G(V,E)進(jìn)行正常頂點(diǎn)染色(即相鄰頂點(diǎn)染不同色),同時,若某頂點(diǎn)有2個以上鄰點(diǎn),要使得至少有2個鄰點(diǎn)染不同色.如果要把圖G(V,E)動態(tài)d-染色用多元多項(xiàng)式方程組描述出來,即根據(jù)圖G(V,E)的動態(tài)d-染色的定義建立多元多項(xiàng)式方程組模型.現(xiàn)取頂點(diǎn)染色方案向量X=(x1,x2,…,xn)T,其中,

      若頂點(diǎn)vi用顏色集{1,2,…,d}中的顏色染色,那么vi的顏色xi為多項(xiàng)式方程

      (xi-1)(xi-2)…(xi-d)=0

      的解.

      (|xi-xj|-1)(|xi-xj|-2)…(|xi-xj|-(d-1))=0

      的解,而方程

      (|xi-xj|-1)(|xi-xj|-2)…(|xi-xj|-(d-1))=0

      等價(jià)于

      ((xi-xj)2-1)((xi-xj)2-22)…((xi-xj)2-(d-1)2)=0.

      對于圖G(V,E)任一頂點(diǎn)vi,其度(即鄰邊數(shù)目)dG(vi)=AiAiT, 通過鄰接矩陣A 就可以確定. 若dG(vi)=AiAiT=1,正常頂點(diǎn)染色方案一定符合|C(N(vi))|≥min{2,dG(vi)};若dG(vi)=AiAiT≥2,由鄰接矩陣A一定可以找到vi的鄰點(diǎn)集N(vi)={vi1,vi2,…,vidG(vi)},若要求N(vi)={vi1,vi2,…,vidG(vi)}至少染2種顏色(即要求|C(N(vi))|≥min{2,dG(vi)}),那么頂點(diǎn)vi1,vi2,…,vidG(vi)對應(yīng)的顏色xi1,xi2,…,xidG(vi)就是方程

      的解.

      由以上過程,可以看到G(V,E)的動態(tài)染d-色方案與方程組

      的解有關(guān).用定理1給定關(guān)系.

      定理1 方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案,且是一一對應(yīng).

      證明充分性方程組Sd的解X會使第一組方程和第二組方程都成立,那么X就會使得每個頂點(diǎn)都在顏色集{1,2,…,d}中選一種顏色,且相鄰的點(diǎn)顏色不同;方程組Sd的解X會使第三組方程成立,那么X就會使得任何有2個鄰點(diǎn)以上的頂點(diǎn)有至少2個鄰點(diǎn)染色不同.因此,方程組得解X就是圖G(V,E)的一個動態(tài)d-染色方案.

      必要性若X是圖G(V,E)的一個動態(tài)d-染色方案,X就是圖G(V,E)的一個頂點(diǎn)正常染色方案,必然符合第一組方程和第二組方程,即代入必使其成立.X要使得任何有2個鄰點(diǎn)以上的頂點(diǎn)有至少2個鄰點(diǎn)染色不同,那么代入第三組方程,第三組方程也成立.由此,X代入方程組Sd會使得其成立,即X是方程組Sd的一個解.

      綜上所述,方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案.且是一一對應(yīng).

      3圖G(V,E)的動態(tài)d-染色方案存在性的Gr?bner基判別方法

      對于圖G(V,E),動態(tài)d-染色方案是否一定存在?存在的話,是否d種顏色構(gòu)成的任一方案都可以對圖G(V,E)進(jìn)行動態(tài)染色?這些問題的解決可以從定理1中找到線索,方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案,且是一一對應(yīng).因此,要判定圖G(V,E)是否動態(tài)d-染色,是否d種顏色構(gòu)成的任一方案都可以對圖G(V,E)進(jìn)行動態(tài)染色就可以轉(zhuǎn)化為多元多次方程組解的存在性問題及求解問題.對于多元多項(xiàng)式方程組根的存在性可以借助于Gr?bner基來判定.因此,定理2就可以解決所提問題.

      定理2對于給定的d(其中0

      1)圖G(V,E)是動態(tài)d-染色的?Sd有解;

      2)倘若Sd有解,那么Sd的所有解就給出圖G(V,E)的所有的動態(tài)d-染色方案;

      3) Sd有解?理想I的Gr?bner基不包括非零的常數(shù),其中,理想I是Sd各方程左端多元多項(xiàng)式在環(huán)R=C[x1,x2,…,xn]中生成的.

      證明 1)和2)由定理1(方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案,且是一一對應(yīng))可以直接推得成立.

      由于Sd解的存在性?I的Gr?bner基生成的多元多項(xiàng)式方程組解的存在性,如果Sd有解,那么V(I)≠?,即理想I的Gr?bner基不包括非零的常數(shù);若理想I的Gr?bner基不包括非零的常數(shù),那么I的Gr?bner基生成的多元多項(xiàng)式方程組解就存在,即方程組Sd有解.3)成立.

      4動態(tài)色數(shù)χd(G)的確定

      定理3Sd-1無解而Sd有解?χd(G)=d.

      證明充分性根據(jù)定理2 1)的逆否命題可知,如果Sd-1無解,那么圖G(V,E)就不存在動態(tài)(d-1) -染色,根據(jù)定理2 1)可知,如果Sd有解,那么圖G(V,E)就存在動態(tài)d-染色,由動態(tài)色數(shù)的定義可知χd(G)=d.

      必要性如果χd(G)=d,根據(jù)動態(tài)色數(shù)的定義就知若要對圖G(V,E)進(jìn)行動態(tài)染色,最少需要d種顏色,即動態(tài)d-染色存在,而動態(tài)(d-1) -染色不存在,結(jié)合定理2 1)和2)就可以得到Sd-1無解而Sd有解.

      5實(shí)例驗(yàn)證

      根據(jù)定理1、定理2和定理3,在實(shí)例中可以依照方程組S2,S3,S4…逐個利用數(shù)學(xué)軟件Maple計(jì)算所對應(yīng)的理想I的Gr?bner基,通過觀察理想I的Gr?bner基是否包含不為零的常數(shù)的方法來確定所對應(yīng)的染色方案是否存在,若存在,就利用理想I的Gr?bner基生成的多元多項(xiàng)式的方程組取得圖G(V,E)的所有的動態(tài)d-染色方案,同時根據(jù)定理3確定χd(G).

      例有限圖G(V,E) (如圖1),其中V={v1,v2,v3,v4,v5,v6},鄰接矩陣為

      根據(jù)定理3,先驗(yàn)證G(V,E)的動態(tài)2-染色的存在性,再驗(yàn)證G(V,E)的動態(tài)3-染色的存在性,依次進(jìn)行下去,直到找到合適的d值,同時得到相應(yīng)的動態(tài)染色方案.

      動態(tài)2-染色

      利用Maple中計(jì)算Gr?bner基的程序可以計(jì)算出G2={1}是IS2的唯一約化Gr?bner基,由定理2可得S2無解,即圖G(V,E)的動態(tài)2-染色不存在.

      動態(tài)染色

      利用Maple中計(jì)算Gr?bner基的程序可以計(jì)算出

      G3={x63-6x62+11x6-6,x62+x52+x5x6-6x5-6x6+11,x5+x6+x4-6,x5x6-x3x6-x3x5+x32,

      x6+x5+x1-1,x3+x2-x6-x5,x5+x1-6}.

      由定理2說明S3有解,且與G3對應(yīng)的方程組G3=0的解相同,在軟件Mapple中調(diào)用程序解G3=0,

      得到結(jié)果(3,2,1,3,2,1),(3,1,2,3,1,2),(3,1,2,3,2,1),(3,1,2,3,2,1),(3,3,1,3,1,2),(2,3,1,2,1,3),(1,3,2,3,1,2),(2,1,3,2,3,1),(1,2,3,1,2,3),(1,3,2,1,3,2),(1,2,3,1,3,2),(2,1,3,2,1,3).

      由定理2也說明這些解恰好是動態(tài)3-染色的所有方案,同時,由定理3也可以知道χd(x)=3.

      參考文獻(xiàn):

      [1] Montgomery B.Dynamic coloring[D].West Virginia:West Virginia University, 2001.

      [2] 林越,趙克文.平面圖的動態(tài)著色[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2010,42(3):34-35.

      [3] Alishahi M.On the dynamic coloring of graphs[J].Discrete Applied Mathematics,2011,159(3):152-156.

      [4] Esperet L.Dynamic list coloring of bipartite graphs [J].Discrete Applied Mathematics,2010,158(17):1 963-1 965.

      [5] 秦健,張巖.單圈圖和雙圈圖的動態(tài)色數(shù)[J].山東大學(xué)學(xué)報(bào)(理學(xué)版),2007,42(10):37-40.

      [6] Akbari S,Ghanbari M,Jahanbekam S.On the list dynamic coloring of graphs[J].Discrete Applied Mathematics, 2009,157(14):3 005-3 007.

      [7] Meng X Y,Miao L Y,Su B T.The dynamic coloring numbers of Pseudo-Halin graphs [J].Ars Combinatoria, 2006, 79:3-9.

      [8] Kim S J,Park W J.List Dynamic coloring of sparse graphs[J].Combinatorial Optimization and Applications,2011,6 831:156-162.

      [9] Kim S J,Lee S J,Park W J.Dynamic coloring and list dynamic coloring of planar graphs[J].Discrete Applied Mathematics,2013,161:2 207-2 212.

      [10] 王桂平,王衍,任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京:北京大學(xué)出版社,2011.

      Dynamic Coloring Solving Scheme Based on Gr?bner Basis

      He Wenfeng, Zhang Yongjun, Fu Yiping

      (College of Information Science and Technology, Hainan University, Haikou 570228,China)

      Abstract:In the report, the dynamic coloring solution of the Limited connected graph and the dynamic coloring number were investigated. Firstly, the multivariate polynomial equation group was used to construct a model of the dynamic coloring problem; Secondly, the corresponding Gr?bner basis of the multivariate polynomial equations was used to determine the existence of solutions, which can judge the existence of the dynamic coloring protocol; Lastly, the dynamic coloring number and the solution method of the corresponding dynamic coloring were proposed, and which was validated by specific examples.

      Keywords:dynamic coloring; dynamic coloring number; Gr?bner basis

      中圖分類號:O 157.5

      文獻(xiàn)標(biāo)志碼:ADOl:10.15886/j.cnki.hdxbzkb.2015.0023

      文章編號:1004-1729(2015)02-0125-05

      收稿日期:------------------------ 2014-10-10

      作者簡介:何文峰(1978-)男,陜西蒲城人,講師.通信作者: 張勇軍(1977-)男,陜西渭南人,講師.

      依兰县| 凤凰县| 调兵山市| 夏邑县| 阜城县| 温州市| 新安县| 中山市| 井研县| 遂平县| 金川县| 益阳市| 醴陵市| 乡城县| 湖南省| 宾阳县| 大足县| 海南省| 荔波县| 施甸县| 肇庆市| 濮阳市| 叙永县| 鹤岗市| 白银市| 蕉岭县| 辽源市| 阳朔县| 错那县| 沙坪坝区| 铜梁县| 葵青区| 防城港市| 安乡县| 鄯善县| 周宁县| 延庆县| 瑞金市| 曲麻莱县| 安达市| 安阳县|