補倍圖的染色

摘要：補倍圖的概念是由張忠輔教授在文獻Zhang Zhongfu，Qiu pengxiang，Zhang donghan and Bian liang.The doule graph and complement double graph of graph.數學進展，2008，37（9），303-310.中提出的概念，在計算機科學數據庫的關系中有著較好的應用.設是一個簡單圖，若， 且 ，

我們稱為 的補倍圖，其中 為的拷貝.

本文對路的補倍圖的點染色和邊染色問題進行了討論，分別給出了路的補倍圖的點色數和邊色數.

關鍵詞：路 補倍圖 點染色 邊染色

第1章 緒論

1.1補倍圖染色的研究背景及研究現狀

圖論是離散數學的重要組成部分，是近代應用數學的重要分支.人們常稱1736年時圖論歷史元年，因為在這一年瑞士數學家歐拉（Euler）發表了圖論的首篇論文——《哥尼斯堡七橋問題無解》，所以人們普遍認為歐拉是圖論的創始人.1936年，匈牙利數學家寇尼格（Konig）出版了圖論的第一部專著《有限圖與無限圖理論》，這是圖論史上的重要里程碑，它標志著圖論將進入突飛猛進發展的新階段.進40年來，隨著計算機科學的發展，圖論更以驚人的速度向前發展，有人形容說:真是異軍突起，活躍非凡.其主要原因有二:其一，計算機科學的發展為圖論的發展提供了計算機工具;其二，現代科學技術的發展需要借助圖論來描述和解決各類課題中的各種關系，從而推動科學技術不斷地攀登新的高峰.作為描述事物之間關系的手段和工具，目前，圖論問題在許多領域諸如，計算機科學、物理學、化學、運籌學、信息論、控制論、網絡通訊、社會科學以及經濟管理、軍事、國防、工農業生產等方面都得到了廣泛應用.圖論中所討論的\"圖\"是有結點和帶方向或不帶方向的弧線連接而成的線狀圖，不是直線、圓、橢圓、曲線等在微積分、解析幾何、幾何學中討論的圖.例如，點可以表示人，連線表示一對朋友;或者用點表示通訊站，而連線表示通訊路線.在這類圖形中，人們主要感興趣的是給定兩點是否有一條線連結，而不考慮點的位置及連線的長短曲直.這類事例的數學抽象，就產生了圖的概念.

染色問題是圖論的重要內容，圖的著色問題的研究起源于四色猜想，四色猜想的提出來自英國。1852年，畢業于倫敦大學的弗南西斯·格思里(Francis Guthrie)來到一家科研單位搞地圖著色工作時，發現了一種有趣的現象:\"看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家著上不同的顏色.\"這個結論能不能從數學上加以嚴格證明呢?弗南西斯·格思里和他的弟弟經過研究始終未能得出結論，后來直到1865年哈密爾頓逝世為止，問題也沒有能夠解決。1872年，英國當時最著名的數學家凱利正式向倫敦數學學會提出了這個問題，于是四色猜想成了世界數學界關注的問題。世界上許多一流的數學家都紛紛參加了四色猜想的大會戰。1878-1880年兩年間，著名的律師兼數學家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認為四色猜想從此也就解決了。11年后，即1890年，數學家赫伍德以自己的精確計算指出肯普的證明是錯誤的。不久，泰勒的證明也被人們否定了。后來，越來越多的數學家雖然對此絞盡腦汁，但一無所獲。進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行.美國數學家富蘭克林于1939年證明了22國以下的地圖都可以用四色著色。1950年，有人從22國推進到35國.1960年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨后又推進到了50國。電子計算機問世以后，由于演算速度迅速提高，加之人機對話的出現，大大加快了對四色猜想證明的進程。1976年，在J. Koch的算法的支持下，美國數學家阿佩爾(Kenneth Appel)與哈肯(Wolfgang Haken)在美國伊利諾斯大學的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明。四色猜想的計算機證明，轟動了世界，當時中國科學家也有在研究這原理。它不僅解決了一個歷時100多年的難題，而且有可能成為數學史上一系列新思維的起點。四色猜想問題得到證明后人們將染色問題開始進行推廣。日程表安排問題便可抽象為圖的染色理論。

例如:（日程表與圖的著色問題）

假設要安排參議院的會議日程表，如果兩個委員會有相同成員，則不能將這兩個委員會的會議安排在同一時間.我們需要多少個不同的時間段呢?將這樣一個安排日程表的問題，我們可以引申為圖的著色問題.我們為每個委員會構造一個頂點，如果兩個委員會有相同的成員，則相應的兩個頂點是相鄰的，我們要給這些頂點分配標記（時間段）使得每條邊的端點都有不同的標記，

如圖1.1-1

有三個獨立集，我們可以給每一個獨立集分配一個標記，圖中的所有成員必須被分配不同的標記，故這個例子至少需要3個時間段.

因為我們只對頂點集的劃分感興趣且標記沒有數值意義，因此將他們稱為顏色會更方便，于是有了點染色的問題．隨著研究的深入與發展之后就有了點染色，邊染色，全染色和鄰點可區別的全染色問題.

補倍圖是是張忠輔教授在數學進展中提出的概念，在計算機科學數據庫的關系中有著較好的應用.本文主要進行補倍圖的點染色和邊染色的研究.

1.2基本概念及符號說明

定義1 一個無向圖是一個有序的二元數組〈V，E〉，記作G，其中，

⑴V≠φ稱為頂點集，其元素稱為頂點或結點.

⑵E稱為邊集，它是無序積V＆V的多重子集，其元素稱為無向邊，簡稱邊.

定義2 在無向圖中，關聯一對頂點的無向邊如果多于一條，則稱這些邊為平行邊，平行邊的條數稱為重數.即不含平行邊也不含環的圖稱為簡單圖.

定義3 對無環圖G的每個頂點涂上一種顏色，使相鄰的頂點涂不同的顏色，稱為對圖G的一種著色.若能用K種顏色給G的頂點著色，就稱對G進行了K著色，也稱G是K—可著色的.若G是K—可著色的，但不是（k-1）—可著色的，就稱G是K色圖，并稱這樣的K為G的色數，記作X（G）=k，不混淆時，色數X（G）也可記作x.

定義4 對圖G的每條邊涂上一種顏色，使相鄰的邊涂不同顏色，稱為對圖G邊的一種著色.若能用k種顏色給G的邊著色，就稱G是k—邊可著色的.若G是k—邊可著色的，但不是（k-1）—邊可著色的，就稱k是G的邊色數，記作X’=k.

定義5 設G(V，E)是一個簡單圖，若

，我們稱 為 的補倍圖，其中 為 的拷貝.

引理1 若C2k為2k階偶圈，則 ，

其中k為正整數.

引理2 若圖G為簡單圖，則 是正則圖.

第2章 補倍圖的染色問題

2.1路的補倍圖的點染色

定理1 設 為n階路，則

證明 分三種情況

情況1：當n=3時

顯然為6階偶圖，由引理1可知， 是2-可著色的，即，圖2.1-1給出了 的2-點染色．

圖 2.1-1

情況2：當n=4時

令 為 的同構圖.首先 ，用對 的點依次循環著色，由定義5， 的頂點中， 與 ， 鄰接，因此 不能著 .故可用 給 著色.同理可用 給 著色，由 與 不鄰接，而與 鄰接， 與 ， 鄰接知 不能著

，因此可用 給 著色，

由上述方法可知， 是3-可著色的，即，圖2.1-2給出了 的3-點染色．

圖2.1-2

情況3：

證畢

圖2.1-3 圖2.1-4

2.2路的補倍圖的邊染色

定理2 設Pn為n階路，則

證明 由于 的每個頂點的度數

故給 作點染色時至少需要n-1種顏色，即

為證明，只需給出 的一個點染色的方案，使 可以用n-1種顏色染完即可.

設映射 滿足

情況1：當時

情況2：當時

證畢

結論

本文討論了路的補倍圖的點染色和邊染色問題，得出以下主要結果：

定理1 設Pn為n階路，則

定理2 設Pn為n階路，則

以上兩個定理給出了路的補倍圖的點色數和邊色數，以上結論均在本文中給出了證明.在討論路的補倍圖的點染色和邊染色問題的過程出，本人提出以下兩個猜想：

1.路的補倍圖的全染色

定理3 設Pn為n階路，則

2. 路的補倍圖的鄰邊可區別的全染色

定理4 設Pn為n階路，則

參考文獻:

[1]張忠輔，仇鵬翔，張東翰，卞量，李敬文，張婷.圖的倍圖與補倍圖(英文)[J].數學進展. 2008.7 03期

[2]劉永平，張忠輔，謝繼國，蘇旺輝.路和圈的倍圖的鄰點可區別全染色[J].甘肅高師學報.2007.(02)

[3]蘇旺輝，劉永平，謝繼國，張忠輔.完全圖的倍圖的鄰點可區別全染色[J].蘭州理工大學學報.2008.(03)

[4]安常省，馮旭霞.幾類特殊圖的補倍圖的點色數[J].天水師范學報.2008.3.02期

[5]劉永平，劉玉勝.離散數學[M].第一版.兵器工業出版社.2006.12

[6]王樹禾.圖論[M]. 第一版.高等教育出版社.2004

[7]（美）（韋斯特）DouglasWest;李建中，駱吉洲（美）（韋斯特）DouglasB.West著;李建中，駱吉洲譯.圖論導引[M].第一版.機械工業出版社，2006.02

[8]劉纘武.應用圖論[M]. 第二版.國防科技大學出版社，2006.01

[9]張先迪，李正良.圖論及其應用[M].北京:高等教育出版社，2005