mycielski圖的染色問題-全文預覽
【正文】 6 (二 )鄰強邊色數 6 1. Myciel ski 圖的鄰強邊色數 7 2. 廣義 Mycielski 圖的鄰強邊色數 7 （三）全色數 8 1. Mycielski 圖的全色數 8 2. 廣義 Mycielski圖 的 全色數 9 （四）鄰點可區(qū)別全色數 9 圖的鄰點可區(qū)別全色數 10 Mycielski 圖的鄰點可區(qū)別全色數 12 致謝 13 參考文獻 14 2 Mycielski 圖的染色問題 摘要： 本論文總結了 Mycielski 圖 及廣義 Mycielski 圖關于染色問題的各方面定義和定理，主要包括邊色 數、鄰強邊色數、全色數、鄰點可區(qū)別全色數的相關結論。所謂四色猜想就是在平面上任何一張地圖，總可以用至多四種顏色給每一個國家染色，使得任何相鄰國家的顏色是不同的。( ( ) ( ) { }V G V G V w? ? ? ? 39。 39。( ) , { | ( ) }w V G V v v V G? ? ?.稱 ()G? 為 G的 Mycielski 圖 . Mycielski 圖的定義 定義 2 [10] 對簡單圖 G , ()VG= 01{ | 1, 2 , .. ., }, ( )nv i p M G? 被稱為 G 的廣義 Mycielski 圖，若 01 02 0 11 12 1 1 2( ( ) ) { , , .. ., 。( ) ( )f e f e? ,則稱 f為 G 的 k 正常邊染色 ,簡記作 k EC? 。 ( ( )) ( ( ))GG? ? ??? 猜想 [2] 對簡單圖 G , 1))(())(( ???? GG ??? 當且僅當 2GK? .其中 2K 表示階為 2 的完全圖 . Mycielski 圖的邊色數 定理 1[5] 對 p 個點的路 ,( 2)pPp? 39。 7 , 3 。 ( ( )) ( ( ))nnM G M G? ?? ,其中 ()G? 表示 G 的最大度 . (二 ) 鄰強邊色數 定義 4 [3] 對圖 ( , )GVE , 若 一 正 常 染 色 f 滿足 ( ) ( )Cu Cv? , 其中( ) , ( ) { ( ) | }uv E G C u f uv uv E? ? ?,則稱 f 為 G 的鄰強邊染色法 ,簡記作 k ASEC? ,且稱 39。 7 , 3( ( ))2 , 4as n nW nn?? ??? ? ?? 定理 4[3] 設 G 為階不小于 1n? 的星圖 nS (即完全二部圖 ,lnK ),則有 8 39。 7 , 3( ( ) )2 , 4as n p pMW pp? ??? ? ?? 定理 2[5] 完全二部圖 ,mnK 的廣義 Mycielski 圖記為 ,( ) , ( 1, 2)l m nM K l n m? ? ?. 對圖 ,( ) , ( 1, 2)l m nM K l n m? ? ?,有 39。 5 , 2( ( )) 7 , 32 , 4TppFpnp???
畢業(yè)設計相關推薦
鄂ICP備17016276號-1