本文選題：Kempe變換 + Kempe等價類��； 參考：《電子與信息學報》2017年06期

【摘要】：給定一個圖G及它的一個正常頂點著色f,G中所有著兩種顏色之一的頂點構成的頂點子集導出的子圖稱為G的一個2-色導出子圖,該2-色導出子圖的分支稱為G的一個2-色分支。Kempe變換是指將圖G的某個2-色分支實施顏色互換。自1879年Kempe引入Kempe變換用于證明四色猜想至今,眾多學者從不同的角度對Kempe變換展開了研究。該文總結了Kempe變換的一些基本性質(zhì);對已有的一些重要成果進行了較為詳細的綜述;針對Meyniel定理,即每個平面圖的所有5-著色構成一個Kempe等價類,給出了一個新而簡短的證明方法;提出了一個與著色類型相關的問題,意在探索不同Kempe等價類之間的關系,以加深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.
【作者單位】： 北京大學信息科學技術學院;北京大學高可信軟件技術教育部重點實驗室;
【基金】：國家973計劃項目(2013CB329600) 國家自然科學基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)~~
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

1 韓紹岑;;有限集合上函數(shù)的強等價類[J];四川師范學院學報(自然科學版);1989年01期

2 王杰;關于排列的型[J];北京大學學報(自然科學版);1990年05期

3 韓紹岑;關于Polya-de Bruijn計數(shù)定理局限性的評注[J];數(shù)學研究與評論;1991年01期

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

5 趙樹理;王軍昌;史開泉;;逆P-等價類的逆P-推理分離-還原[J];山東大學學報(理學版);2013年01期

6 林培榕;張其森;李進金;;基于交可約等價類的概念格屬性約簡[J];模式識別與人工智能;2010年05期

7 王建豐;陳佐利;;一類圖的伴隨等價類的應用[J];河北科技師范學院學報;2007年03期

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

9 韓紹岑;有限集合上函數(shù)的強等價類[J];科學通報;1989年18期

10 李囡囡;;設計距離為δ的q元BCH碼的非循環(huán)等價類[J];科學技術與工程;2007年01期

，

本文編號：1840326