發(fā)布時(shí)間：2018-10-11 10:18

【摘要】：該文提出一種稱為334擴(kuò)縮運(yùn)算的多米諾擴(kuò)縮運(yùn)算。使用該運(yùn)算構(gòu)造了一類特殊的極大平面圖——334-型極大平面圖,證明了該類圖均為樹型2-色不變?nèi)χ?且每個(gè)4k-階334-型極大平面圖恰有2~(k-1)個(gè)2-色不變?nèi)χ?~(k-2)個(gè)樹著色。證明了該運(yùn)算可用于構(gòu)造純樹著色極大平面圖,并提出猜想:若極大平面圖G是純樹(純?nèi)?混合)著色,則對(duì)G實(shí)施334擴(kuò)(縮)輪運(yùn)算后,所得之圖仍是純樹(純?nèi)?混合)著色。
[Abstract]:In this paper, a domino-scaling operation called 334 scaling operation is proposed. By using this operation, a special maximal planar graph of type 334-type is constructed. It is proved that all of these graphs are tree-type 2-chromatic invariant cycle coloring, and each maximal planar graph of order 334- has exactly 2 ~ (k-1) 2-chromatic invariant cycle coloring and 2 ~ (k-2) tree coloring. It is proved that this operation can be used to construct the coloring maximal planar graph of pure trees. If G is a pure tree (pure cycle, mixed) coloring, the graph obtained is still pure tree (pure cycle) after 334 extension (contraction) round operation of G. Mixed) coloring
【作者單位】： 北京大學(xué)信息科學(xué)技術(shù)學(xué)院;北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室;
【基金】：國(guó)家973計(jì)劃項(xiàng)目(2013CB329600) 國(guó)家自然科學(xué)基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)~~
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 葉載良;極大平面圖的構(gòu)造[J];紡織高�；A(chǔ)科學(xué)學(xué)報(bào);2003年03期

2 韓忠海,楊愛民;關(guān)于(4,6)-正則極大平面圖的構(gòu)造[J];華北工學(xué)院學(xué)報(bào);2004年06期

3 葉載良;;極大平面圖的面嵌入圖[J];紡織高�；A(chǔ)科學(xué)學(xué)報(bào);2005年04期

4 韓忠海;;12階的(4,8)-正則極大平面圖的不存在性[J];山西農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年01期

5 謝力同;極大平面圖的組合運(yùn)算[J];系統(tǒng)科學(xué)與數(shù)學(xué);1993年04期

6 王紹文;;極大平面圖的構(gòu)成算法[J];北京機(jī)械工業(yè)學(xué)院學(xué)報(bào);1997年02期

7 王紹文;極大平面圖結(jié)構(gòu)研究[J];光子學(xué)報(bào);1998年02期

8 王紹文;;同構(gòu)極大平面圖研究[J];北京機(jī)械工業(yè)學(xué)院學(xué)報(bào);1998年01期

9 王紹文;構(gòu)造極大平面圖的三種方法[J];北京機(jī)械工業(yè)學(xué)院學(xué)報(bào);1999年01期

10 許壽椿,劉恒軍,楊麗麗,朱英,許懷皓;著五色極大平面圖的對(duì)偶2～3色子圖及五色點(diǎn)消減的實(shí)驗(yàn)研究[J];中央民族大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年01期

相關(guān)碩士學(xué)位論文 前6條

1 李永麗;（k，l，m）-正則極大平面圖[D];山西大學(xué);2010年

2 韓忠海;（K，L）-正則極大平面圖[D];山西大學(xué);2005年

3 楊寧;極大平面圖略型著色的計(jì)算機(jī)輔助研究[D];中央民族大學(xué);2005年

4 程斌;極大平面圖最簡(jiǎn)非樹型著色的統(tǒng)計(jì)分析與生成[D];中央民族大學(xué);2005年

5 寶力高;極大平面圖最簡(jiǎn)非樹型著色的統(tǒng)計(jì)分析與生成[D];中央民族大學(xué);2005年

6 劉茜;極大平面圖的構(gòu)造方法與幾類特殊圖的色數(shù)分析[D];南京信息工程大學(xué);2008年

，

本文編號(hào)：2263824