本文選題：Kempe變換 + Kempe等價(jià)類(lèi)��； 參考：《電子與信息學(xué)報(bào)》2017年06期

【摘要】：給定一個(gè)圖G及它的一個(gè)正常頂點(diǎn)著色f,G中所有著兩種顏色之一的頂點(diǎn)構(gòu)成的頂點(diǎn)子集導(dǎo)出的子圖稱(chēng)為G的一個(gè)2-色導(dǎo)出子圖,該2-色導(dǎo)出子圖的分支稱(chēng)為G的一個(gè)2-色分支。Kempe變換是指將圖G的某個(gè)2-色分支實(shí)施顏色互換。自1879年Kempe引入Kempe變換用于證明四色猜想至今,眾多學(xué)者從不同的角度對(duì)Kempe變換展開(kāi)了研究。該文總結(jié)了Kempe變換的一些基本性質(zhì);對(duì)已有的一些重要成果進(jìn)行了較為詳細(xì)的綜述;針對(duì)Meyniel定理,即每個(gè)平面圖的所有5-著色構(gòu)成一個(gè)Kempe等價(jià)類(lèi),給出了一個(gè)新而簡(jiǎn)短的證明方法;提出了一個(gè)與著色類(lèi)型相關(guān)的問(wèn)題,意在探索不同Kempe等價(jià)類(lèi)之間的關(guān)系,以加深Kempe變換的研究。
[Abstract]:Given a graph G and one of its normal vertex coloring subgraphs, all vertex subgraphs derived from a vertex subset of one of two colors are called a 2-chromatic derived subgraph of G. The branch of the 2-chromatic derived subgraph is called a 2-chromatic branch of G. Kempe transformation means that some 2-chromatic branch of G is interchanged. Since Kempe introduced Kempe transform to prove four-color conjecture in 1879, many scholars have studied Kempe transform from different angles. In this paper, some basic properties of Kempe transformation are summarized, some important achievements are summarized in detail, and for the Meyniel theorem, all 5-coloring of every planar graph constitutes a Kempe equivalence class. In this paper, a new and brief proof method is given, and a problem related to coloring type is presented, which is intended to explore the relationship between different Kempe equivalence classes in order to deepen the study of Kempe transformation.
【作者單位】： 北京大學(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)~~
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 韓紹岑;;有限集合上函數(shù)的強(qiáng)等價(jià)類(lèi)[J];四川師范學(xué)院學(xué)報(bào)(自然科學(xué)版);1989年01期

2 王杰;關(guān)于排列的型[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);1990年05期

3 韓紹岑;關(guān)于Polya-de Bruijn計(jì)數(shù)定理局限性的評(píng)注[J];數(shù)學(xué)研究與評(píng)論;1991年01期

4 徐鳳生;于秀清;張環(huán)理;;S-粗等價(jià)類(lèi)與知識(shí)動(dòng)態(tài)挖掘-發(fā)現(xiàn)[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2013年03期

5 趙樹(shù)理;王軍昌;史開(kāi)泉;;逆P-等價(jià)類(lèi)的逆P-推理分離-還原[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2013年01期

6 林培榕;張其森;李進(jìn)金;;基于交可約等價(jià)類(lèi)的概念格屬性約簡(jiǎn)[J];模式識(shí)別與人工智能;2010年05期

7 王建豐;陳佐利;;一類(lèi)圖的伴隨等價(jià)類(lèi)的應(yīng)用[J];河北科技師范學(xué)院學(xué)報(bào);2007年03期

8 韓紹岑,查曉亞;Pòl(fā)ya計(jì)數(shù)定理之精細(xì)化[J];科學(xué)通報(bào);1986年09期

9 韓紹岑;有限集合上函數(shù)的強(qiáng)等價(jià)類(lèi)[J];科學(xué)通報(bào);1989年18期

10 李囡囡;;設(shè)計(jì)距離為δ的q元BCH碼的非循環(huán)等價(jià)類(lèi)[J];科學(xué)技術(shù)與工程;2007年01期

，

本文編號(hào)：1840326