周源：

貪心算法，也可以說(shuō)成是構(gòu)造算法吧，證明是我自己寫的，應(yīng)該是對(duì)的吧。

本題可以理解為，給定頂點(diǎn)數(shù)N和每個(gè)定點(diǎn)的度，要求構(gòu)造一個(gè)滿足要求的簡(jiǎn)單圖。構(gòu)造算法是這樣的：為了敘述方便，我們每次選擇剩余度數(shù)最大的點(diǎn)A（這是無(wú)所謂的，但是如果選擇最大的點(diǎn)，算法描述和證明要簡(jiǎn)單一些）。讓這個(gè)點(diǎn)依次和度數(shù)次大，第3大……的點(diǎn)連線，如果最終不夠連了，那么顯然無(wú)解，否則連完之后，該點(diǎn)就可以不考慮了，然后繼續(xù)子問(wèn)題的求解……，直到構(gòu)造出解或者得到無(wú)解。

證明：設(shè)在某步構(gòu)造的時(shí)候，將A和B連線，但是已知解中，A,B間卻沒(méi)有連線，相反的，A,C之間卻有邊相連，且D(B)>D(C) （D表示定點(diǎn)的度），正因?yàn)槿绱耍欢ㄖ辽儆幸粋€(gè)點(diǎn)Z滿足Z和B之間有邊但是與C卻沒(méi)有邊，這樣，將A,C邊改為C,Z，B,Z邊改為A,B仍然滿足條件，于是也滿足算法的要求，可以被算法構(gòu)造出來(lái)。