給定一個(gè)非負(fù)整數(shù)序列，若存在一個(gè)無(wú)向圖使得圖中各點(diǎn)的度與此序列一一對(duì)應(yīng)，則稱此序列可圖化。進(jìn)一步，若圖為簡(jiǎn)單圖，則稱此序列可簡(jiǎn)單圖化。
可圖化的判定比較簡(jiǎn)單：
。
關(guān)于具體圖的構(gòu)造，我們可以簡(jiǎn)單地把奇數(shù)度的點(diǎn)配對(duì)，剩下的全部搞成自環(huán)。
可簡(jiǎn)單圖化的判定，有一個(gè)Havel定理，是說(shuō): 我們把序列排成不增序，即
則d可簡(jiǎn)單圖化當(dāng)且僅當(dāng)
可簡(jiǎn)單圖化。這個(gè)定理寫起來(lái)麻煩，實(shí)際上就是說(shuō)，我們把d排序以后，找出度最大的點(diǎn)(設(shè)度為d1)，把它和度次大的d1個(gè)點(diǎn)之間連邊，然后這個(gè)點(diǎn)就可以不管了，一直繼續(xù)這個(gè)過(guò)程，直到建出完整的圖，或出現(xiàn)負(fù)度等明顯不合理的情況。
定理的簡(jiǎn)單證明如下:
(<=)若d'可簡(jiǎn)單圖化，我們只需把原圖中的最大度點(diǎn)和d'中度最大的d1個(gè)點(diǎn)連邊即可，易得此圖必為簡(jiǎn)單圖。 (=>)若d可簡(jiǎn)單圖化，設(shè)得到的簡(jiǎn)單圖為G。分兩種情況考慮:
(a)若G中存在邊，則把這些邊除去得簡(jiǎn)單圖G'，于是d'可簡(jiǎn)單圖化為G'
(b)若存在點(diǎn)Vi,Vj使得i=dj，必存在k使得(Vi, Vk)在G中但(Vj,Vk)不在G中。這時(shí)我們可以令GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}。GG的度序列仍為d，我們又回到了情況(a)。
題目練習(xí):http://acm.hdu.edu.cn/showproblem.php?pid=2454
posted on 2008-11-02 17:06
小果子 閱讀(1303)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
學(xué)習(xí)筆記