周源：

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

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

證明：設(shè)在某步構(gòu)造的時候，將A和B連線，但是已知解中，A,B間卻沒有連線，相反的，A,C之間卻有邊相連，且D(B)>D(C) （D表示定點的度），正因為如此，一定至少有一個點Z滿足Z和B之間有邊但是與C卻沒有邊，這樣，將A,C邊改為C,Z，B,Z邊改為A,B仍然滿足條件，于是也滿足算法的要求，可以被算法構(gòu)造出來。