亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        NIC-平面圖中的輕邊存在性及其定向染色

        2018-04-08 05:46:33劉維嬋
        計算機(jī)工程與應(yīng)用 2018年7期
        關(guān)鍵詞:平面圖度數(shù)權(quán)值

        劉維嬋

        LIU Weichan

        西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,西安 710071

        School of Mathematics and Statistics,Xidian University,Xi’an 710071,China

        1 引言

        圖論是一門古老的數(shù)學(xué)分支,它起源于1736年歐拉對于哥尼斯堡七橋問題的研究。近年來,圖論學(xué)科的發(fā)展非常迅速且應(yīng)用廣泛,已滲透到諸如語言學(xué)、物理學(xué)、化學(xué)、電訊工程、計算機(jī)科學(xué)以及數(shù)學(xué)的其他分支中,特別在計算機(jī)科學(xué)中,圖論在如形式語言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)等方面均扮演著重要的角色。

        本文研究圖的拓?fù)浣Y(jié)構(gòu),只考慮簡單圖。如果一個圖可以畫(嵌入)在平面上,使得不同的邊互不交叉,則稱這樣的圖是平面圖,否則稱為非平面圖。一個平面圖在平面上的嵌入稱為平圖。對于平圖G,用V(G)、E(G)、F(G)分別表示它的點集合、邊集合、面集合。著名的歐拉公式表明:

        設(shè)G為一個圖在平面上的嵌入,如果圖G上存在交叉,則必然是G的某兩條邊交叉產(chǎn)生的,于是G中的每個交叉c都可以與G中的4個頂點(即兩條交叉邊上的4個頂點)所構(gòu)成的點集建立對應(yīng)關(guān)系,稱這個對應(yīng)關(guān)系為θ。如果對于G中任何兩個不同的交叉(如果存在的話)c1與c2,有|θ(c1)?θ(c2)|≤1,則稱圖 G 是NIC-平面圖。NIC-平面圖的概念是由Zhang[1]于2014年提出的。容易看出,每個平面圖都是NIC-平面圖。

        設(shè)?是一個圖類,如果對于?中的任何一個圖G,都存在一條邊uv以及一個與圖G的選擇無關(guān)的常數(shù)ω,使得d(u)+d(v)≤ω,則稱圖類?含有輕邊。Kotzig[2]證明了每個3-連通的平面圖都含有一條邊uv,其兩個頂點的度和至多為13。Fabrici與Madaras[3]證明了每個3-連通的1-平面圖都含有一條邊uv,其兩個頂點的度都不會超過20。具有最小度限制條件的1-平面圖的輕邊或其他輕子圖的存在性的研究可參見文獻(xiàn)[4-12]。

        下文中,對于NIC-平面圖G,用δ(G)表示它的最小度,即度數(shù)(點所關(guān)聯(lián)的邊的條數(shù))最小的頂點的度數(shù);用g(G)表示它的圍長,即圖G所包含的所有圈中長度(圈所關(guān)聯(lián)的邊的條數(shù))最短的圈的長度;用GX表示圖G的關(guān)聯(lián)平面圖,即將圖G的所有交叉全部看成是一個新的度數(shù)為4的點所得到的平圖,這些新的點稱為圖GX的假點,其余的點稱為圖GX的真點;在圖GX中關(guān)聯(lián)假點的面稱為假面,其余的面稱為真面;k-點(面)或k+-點(面)指的是度數(shù)為k或至少為k的點(面)。其余未明確指出的定義或者記號可參閱文獻(xiàn)[7]。

        設(shè)G是一個圍長至少為5的NIC-平面圖?,F(xiàn)從圖G的每一對交叉邊中去除一條,得到圖H。容易看出,圖H是一個圍長至少為5的平面圖。根據(jù)歐拉公式(1),可以得到[13]:

        另一方面,Zhang[1]于2014年證明了圖G的交叉數(shù)至多為3(|V(G)|-2)/5,因此:

        從而圖G的平均度為2|E(G)|/|V(G)|<5,由此可得δ(G)≤4,即每個圍長至少為5的NIC-平面圖都含有一個度數(shù)不超過4的點。基于此,本文將研究圍長至少為5且最小度為4的NIC-平面圖的輕邊存在性,并探討其在定向染色中的應(yīng)用。

        2 NIC-平面圖的輕邊存在性

        定理1設(shè)G是NIC-平面圖,如果δ(G)=4且g(G)≥5,則G存在邊uv,其中d(u)=d(v)=4。

        證明 假設(shè)該命題的結(jié)論不成立,即對于G的任何一條邊uv,當(dāng)d(u)=4時,有d(v)≥5。

        考慮圖G的關(guān)聯(lián)平面圖GX,由于它是平面圖,故根據(jù)歐拉公式(1),有:

        對于圖GX的每個點v,定義權(quán)值c(v)=d(v)-6,對于每個面 f,定義權(quán)值c(f)=2d(f)-6。從而由式(2)可知:

        接下來,定義權(quán)轉(zhuǎn)移規(guī)則如下:

        (R1)每個4-面向其關(guān)聯(lián)的假4-點轉(zhuǎn)移1/2。

        (R2)設(shè) f=uvwx為4-面且 x為假4點,如果v是真4-點,則 f向v轉(zhuǎn)移5/6;如果u或w是真4-點,則 f向u或w轉(zhuǎn)移1/2。

        (R3)每個4+-面向其關(guān)聯(lián)的5-點轉(zhuǎn)移1/3。

        (R4)設(shè) f是一個5+-面,v是其關(guān)聯(lián)的真4-點,如果v在 f的兩個相鄰點都是假4-點,則 f向v轉(zhuǎn)移7/6;否則,f向v轉(zhuǎn)移1。

        (R5)每個5+-面向其關(guān)聯(lián)的假4-點轉(zhuǎn)移3/4。

        設(shè)c*(v)與c*(f)為圖GX中的點v與面 f在執(zhí)行完上述權(quán)轉(zhuǎn)移規(guī)則后的最終權(quán)值。

        情況1點v是假4-點

        如果點v關(guān)聯(lián)4個4+-面,則由(R1)與(R5)可知:

        如果點v關(guān)聯(lián)3-面,則由于圖G是NIC的,并且其圍長至少為5,推得點v關(guān)聯(lián)2個5+-面與1個4+-面,從而根據(jù)(R1)與(R5)可知:

        情況2點v是真4-點

        記v1,v2,v3,v4為點v在GX中的4個鄰點,并且f1,f2,f3,f4分別為與{vv1,vv2},{vv2,vv3},{vv3,vv4},{vv4,vv1}關(guān)聯(lián)的面。

        如果v在GX中的鄰點都是真點,那么由圖G的圍長至少為5可得點v關(guān)聯(lián)4個4+-面,從而根據(jù)(R2)與(R4)得到:

        如果v在GX中的鄰點有假點,則:

        (1)當(dāng)v在GX中的鄰點中有且僅有1個假點時,若點 v關(guān)聯(lián)4個4+-面時,由(R2)與(R4)得式(4)。若點v關(guān)聯(lián)1個3-面時,則其關(guān)聯(lián)3個4+-面,且其中1個是5+-面(否則與圍長限制條件矛盾),因此根據(jù)(R2)與(R4),可得:

        (2)當(dāng)v在GX中的鄰點中有且僅有2個假點時,根據(jù)對稱性,考慮兩種子情況。

        其一,如果v1,v2是假點,則 f1必定為5+-面(否則與NIC-平面圖的定義矛盾),此時若 f3是5+-面,則根據(jù)(R4)有:

        若 f3是4-面,則其必定為假4-面,由(R2)與(R4)得:

        其二,如果v1,v3是假點,則當(dāng) f1,f2,f3,f4均為4+-面時,由(R2)與(R4)可得式(4)。當(dāng)它們中有至少2個3-面時,則其中至少有2個5+-面,故由(R4)得:

        當(dāng) f1,f2,f3,f4中有且只有1個3-面時,則其中有2個4+-面與1個5+-面,從而根據(jù)(R2)與(R4)有:

        (3)當(dāng)v在GX中的鄰點中有且僅有3個假點時,不妨設(shè)其為v1,v2,v3,此時若 f1,f2,f3,f4均為4+-面時,由(R2)與(R4)得式(4)。若 f1,f2,f3,f4中存在3-面時,則其必為 f3或者 f4,不妨設(shè)其為 f4。現(xiàn) f3為4+-面且f1,f2為5+-面,故由(R2)與(R4)得:

        (4)當(dāng)v在GX中的鄰點中有4個假點時,則其關(guān)聯(lián)4個 4+-面,從而由(R2)與(R4)得式(4)。

        情況3點v是5-點

        記v1,v2,v3,v4,v5為點v在GX中的5個鄰點,并且 f1,f2,f3,f4,f5分別為與{vv1,vv2},{vv2,vv3},{vv3,vv4},{vv4,vv5},{vv5,vv1}關(guān)聯(lián)的面。如果 5個面中至少有3個4+-面,則根據(jù)(R3)可得:

        否則這5個面中至少有3個3-面,并且其中2個必定相鄰。因此不妨設(shè) f1,f2為3-面,由于圖G的圍長至少為5,故 f1,f2都為假3-面。此時有兩種情況:其一,當(dāng)v2是假點時,則v1,v3為真點,從而vv1v3構(gòu)成了G中的一個三角形,矛盾;其二,當(dāng)v2是真點時,則v1,v3為假點,此時|θ(v1)?θ(v3)| ≥2,與NIC-平面圖的定義矛盾。

        情況4面 f是4-面

        由于圖G的圍長至少為5,故 f是假4-面。再由于圖是NIC-平面的,其恰好關(guān)聯(lián)1個假4-點。此時如果 f關(guān)聯(lián)(至少)2個真4-點,其必定關(guān)聯(lián)1個5+-點,并且這2個真4-點與 f所關(guān)聯(lián)的假4-點相鄰,于是根據(jù)(R1),(R2)與(R3),有:

        若 f關(guān)聯(lián)恰好1個真4-點,則由前3條規(guī)則可得:

        若 f不關(guān)聯(lián)真4-點,則由(R1)與(R3)可得:

        情況5面 f是5+-面

        當(dāng) d(f)=5時,則根據(jù)(R3)、(R4)與(R5)可知當(dāng) f關(guān)聯(lián)2個真4-點,2個假4-點與1個5-點時,f向外轉(zhuǎn)移的權(quán)值最多,從而:

        當(dāng)d(f)=d≥6時,設(shè) f關(guān)聯(lián)a個真4-點與b個假4-點。因為真4-點與真4-點不相鄰并且假4-點與假4-點不相鄰,因此根據(jù)(R3)、(R4)與(R5)可知:

        最后,由于6+-點與3-面不參與權(quán)轉(zhuǎn)移,故它們的最終權(quán)值和初始權(quán)值相同,為非負(fù)。

        至此,已經(jīng)證明了圖GX中的所有點與面的最終權(quán)值均為非負(fù),即得到:

        由于權(quán)只在圖GX中的所有點與面的內(nèi)部進(jìn)行轉(zhuǎn)移,故轉(zhuǎn)移前后的總權(quán)值和不變,即根據(jù)式(3)有:

        此與式(5)矛盾。

        3 結(jié)論的推廣及其在定向染色中的應(yīng)用

        本章首先給出定理1的一個重要推論。

        推論1設(shè)G是一個圍長至少為5的NIC-平面圖,則G存在一個度數(shù)至多為3的點,或者兩個相鄰的度數(shù)為4的點。

        證明 如果圖G不存在度數(shù)至多為3的點,則δ(G)≥4。另一方面,由第1章最后一段的分析可知δ(G)≤4,于是δ(G)=4。此時根據(jù)定理1可知圖G含有兩個相鄰的度數(shù)為4的點。

        設(shè)G是一個簡單無向圖,現(xiàn)將圖G的每一條邊uv進(jìn)行定向(令u指向v或者v指向u)得到一個有向圖。圖的一個定向k-染色指的是一個從V到{1,2,…,k}的映射c,其對于圖的每一條弧滿足:(1)c(u)≠c(v);(2)不存在弧使得c(x)=c(u)且c(y)=c(v)。從而使得圖具有一個定向k-染色的最小整數(shù)k稱為圖的定向染色數(shù),記為χo。設(shè)Θ(G)為對無向圖G進(jìn)行定向后得到的所有可能的有向圖的集合,則無向圖G定向染色數(shù)定義為

        2007年,Esperet與Ochem[14]證明了如果圖G是不滿足χo(G)≤67的極小反例,則圖G不含有度數(shù)至多為3的點,亦不含有兩個相鄰的度數(shù)為4的點。因此,根據(jù)推論1可得到如下一個結(jié)果。

        定理2設(shè)G是一個圍長至少為5的NIC-平面圖,則 χo(G)≤67。

        注意到Raspaud與Sopena[15]證明了每個平面圖G滿足χo(G)≤80,這也是到目前為止最好的結(jié)果。由于NIC-平面圖類包含平面圖類,故從一定的意義上來看定理2是上述結(jié)論的推廣與改進(jìn)。

        4 結(jié)論

        綜上所述,本文證明了每個圍長至少為5且最小度為4的NIC-平面圖含有一條邊,其2個頂點的度數(shù)都是4,從而推出每個圍長至少為5的NIC-平面圖的定向染色數(shù)至多為67。

        定理1中,關(guān)于NIC-平面圖的圍長的下界5是否可以降低是一個值得繼續(xù)考慮的問題。此外,利用其他方式得到NIC-平面圖的定向染色數(shù)的較好上界也是一個有意義的研究方向。

        參考文獻(xiàn):

        [1]Zhang X.Drawing complete multipartite graphs on the plane with restrictions on crossings[J].Acta Mathematica Sinica:English Series,2014,30(12):2045-2053.

        [2]Kotzig A.Contribution to the theory of Eulerian polyhedra[J].Mat ?as SAV:Math Slovaca,1955,5:111-113.

        [3]Fabrici I,Madaras T.The structure of 1-planar graphs[J].Discrete Mathematics,2007,307:854-865.

        [4]Hudák D,?ugerek P.Light edges in 1-planar graphs with prescribed minimum degree[J].Discussiones Mathematicae Graph Theory,2012,32(3):545-556.

        [5]田京京,聶玉峰.度限制條件下的IC平面圖類中輕弦4-圈的存在性[J].計算機(jī)工程與應(yīng)用,2016,52(20):26-28

        [6]Zhang X.Light 3-cycles in 1-planar graphs with degree restrictions[J].Bulletin of the Korean Mathematical Society,2014,51(2):511-517.

        [7]Tian J,Zhang X,Light triangles in plane graphs with nearindependent crossings[J].Utilitas Mathematica,2015,97:399-405.

        [8]Zhang X.A note one the weight of triangle in 1-planar graphs with minimum degree 6[J].Utilitas Mathematica,2014,93:129-134.

        [9]Zhang X,Liu G.On the lightness of chordal 4-cycle in 1-planar graphs with high minimum degree[J].Ars Mathematica Contemporanea,2014,7(2):233-243.

        [10]Zhang X,Liu G,Wu J.Light subgraphs in the family of 1-planar graphs with high minimum degree[J].Acta Mathematica Sinica:English Series,2012,28(6):1155-1168.

        [11]Zhang X,Wu J,Liu G.New upper bounds for the heights of some light subgraphs in 1-planar graphs with high minimum degree[J].Discrete Mathematics and Theoretical Computer Science,2011,13(3):9-16.

        [12]張欣,劉桂真,吳建良.1-平面圖的結(jié)構(gòu)性質(zhì)及其在無圈邊染色上的應(yīng)用[J].中國科學(xué):數(shù)學(xué),2010,40(10):1025-1032.

        [13]Bondy J A,Murty U S R.Graph theory with applications[M].New York:North-Holland,1976.

        [14]Esperet L,Ochem P.Oriented colorings of 2-outerplanar graphs[J].Information Processing Letters,2007,101:215-219.

        [15]Raspaud A,Sopena E.Good and semi-strong colorings of oriented planar graphs[J].Information Processing Letters,1994,51(4):171-174.

        猜你喜歡
        平面圖度數(shù)權(quán)值
        一種融合時間權(quán)值和用戶行為序列的電影推薦模型
        眼鏡的度數(shù)是如何得出的
        CONTENTS
        圖形中角的度數(shù)
        《別墅平面圖》
        《別墅平面圖》
        《景觀平面圖》
        隱形眼鏡度數(shù)換算
        基于權(quán)值動量的RBM加速學(xué)習(xí)算法研究
        平面圖的3-hued 染色
        久久久久久亚洲AV成人无码国产| 特黄aaaaaaaaa毛片免费视频| 国产精品无码一区二区在线看| 亚洲欧美日韩高清专区一区| 免费人人av看| 成人久久精品人妻一区二区三区| 中文字幕亚洲无线码一区女同| 五十路熟妇高熟无码视频| 国产精品98视频全部国产| 亚洲av成人波多野一区二区| 风韵丰满熟妇啪啪区老熟熟女| 白又丰满大屁股bbbbb| 国产资源在线视频| 亚洲天堂线上免费av| 插鸡网站在线播放免费观看| 亚洲精品久久中文字幕| 一区二区免费电影| 日本在线观看三级视频| 欧美国产亚洲日韩在线二区| 中出内射颜射骚妇| 无码高潮久久一级一级喷水| 视频区一区二在线观看| 天堂国产一区二区三区| 亚洲日韩欧美国产另类综合| 级毛片无码av| 国产精品一区av在线| 窝窝午夜看片| 亚洲欧美日韩综合在线观看| 亚洲国产av中文字幕| 嫩草伊人久久精品少妇av| 国产人妻精品一区二区三区不卡| 波多野结衣一区二区三区免费视频 | 日韩女优一区二区视频| 黄片小视频免费观看完整版| 精品少妇爆乳无码av无码专区| 国产精品久久久久久久久免费观看 | 国产精品自在线拍国产| 婷婷色国产精品视频一区| 亚洲午夜精品第一区二区| 东京热无码av一区二区| 国产小毛片|