資源描述：
《求頂點著色問題的一種新方法》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、維普資訊http://www.cqvip.com第l9卷第3期重慶工學院學報2005年3月Vo1．19No．3JournalofChongqingInstituteofTechnologyMar．2005【計算機與自動化】求頂點著色問題的一種新方法胡青龍，何軍(1．西昌學院工程技術系，四川西昌615013；2．重慶師范大學經濟與政治學院，重慶400047)ANewMethodofVerterColouringHUQing．1ong，HEJun(1．EngineeringDepartment，XiehangCollege，Xichang，
2、615013，China；2．DepartmentofEconomicsandPolitics，ChongqingNormalUniversity，Chongqing400047，China)Abstract：Thispaperputsforwardanewmethodofvertexcolouringofagraph，thatis，togetakindofsubdivision(V1，，??)ofthevertexsetV(G)ofagraphG(i．e．，permutingitsrowandcor-respondingseries)
3、bymeansoftransformationofsimilitudeandpermutation．Keywords：Vertexcolouring；adjacentmatrix；permutationmatrix；directionadjointmatrix；lexico—graphicorder；partitionofavertexset1預備知識獨立集，(G)的獨立集分劃(V，，?，)，最小覆蓋數，根據團的定義及獨立集與團的關系，還能對于圖的頂點著色問題(僅考慮連通的簡單得到其補圖的最小團覆蓋數(即色數)和最大團圖)，人們關心的往
4、往是色數及最小著色問題等一(數)．些相關問題，文獻[1]介紹了一種求色數及最小著定義1．1用n種顏色對圖G的頂點進行著色的方法，但這種方法容易忽略一部分情況，實際色，且沒有相異的鄰接頂點著色相同，則稱為G的上，我們可以對這種方法作一些改進，即若圖的邊—個n一頂點著色(n—vertexcolouring)，簡稱n一按某種方式收縮，得到三角形(或完全四邊形著色．)，那么我們判斷一下圖中是否含有團Ks(或定義1．2使圖G為n一著色的最小數值稱為)，若有，則最小色數為3(或4)即可停止計算．G的色數(chromaticnumber)，記作(G)
5、．如果文獻[2]介紹了另外一種用線性整數規(guī)劃的方法(G)=n，則G為n一色的(n—colouring)．來求圖的著色問題．下面筆者將介紹的是如何利從頂點著色的定義可以看出，具有任何一種用鄰接矩陣置換行和相應的列(即置換相似變換)相同顏色的所有頂點集為圖的獨立集(indepent來求圖的色數及最小著色，同時還可以得到最大set)，因此圖G的一個n一著色，也就是把(G)分·收稿日期：2004．10．13作者簡介：胡青龍(1966一)，男，四川儀隴人，副教授，主要從事運籌學及圖論研究．維普資訊http://www.cqvip.com36重慶工
6、學院學報成個幾個獨立集的一個劃分(，，?，)．關于=JBl，2=JB2??。=，?≤+l，則稱A≤B，圖的著色問題，我們可以運用文獻[1]第151頁i=1，2，?，P．TH所給的方法求圖G的色數，也可以利用線由前所知，對任意連通的簡單圖G，其鄰接矩．：．性整數規(guī)劃中的最小覆蓋問題來求解．如果需要陣為A，都存在最小著色問題，也即存在圖G的頂一個圖G的非圖形表示時(例如使用計算機時)，點集V(G)的一個劃分(，，?，)．如果我們通常利用圖的鄰接矩陣來描述它的結構．下面給按(G)的劃分中頂點順序給圖G重新標定，則可出它的定義：得到鄰接矩陣A’
7、，且存在置換矩陣P，使得A=定義1．3設圖G的頂點集(G)=(V1，，PAP，因此可以得到下述定理：?，)，令定理2．1設簡單的連通圖G，頂點集為f1，若與鄰接(G)，鄰接矩陣為A，圖G的色數為n，V，，，?，，若與不鄰接，或：y是圖G的一種最小著色，其中y為獨立集，i=則稱元素0(i，=1，2，?，P)構成的P階矩陣為1，2，?n，則若按，，，?，中頂點順序重新標圖的鄰接矩陣(adjacentmatrix)，記作A(G)或記定圖G，對應的鄰接矩陣A’的形狀如下：為A．0那么在不同的標定下，圖的鄰接矩陣之間有0什么關系呢?鄰接矩陣的行與
8、列按相同的頂點次0序排列，置換行和相應的列，即重新安排頂點的次0序．如在鄰接A中交換兩行(同時交換相應的列)，那么圖G。同構于圖G：的充要條件為存在一個置其中0．為II階零矩陣，空白處為1或0，i=1，換矩
