[理工] 離散 Graph

[yad50968 (boringday)]

1.
http://i.imgur.com/22f6v7O.jpg

這題的證明
我想到的是
因為任兩點才能形成一個邊
所以e>=n-1
這樣對嗎



2.
For each of the following sequence,determine if there exists a graph whose deg
ree sequence is the one specified .

(B) 5 5 4 3 2 1
想請問這題如何計算

謝謝～




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.87.231
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1446826990.A.91C.html
推 kev72806: 第一題想法上是那樣，可是證明不能這樣寫，要對點作數
→ kev72806: 學歸納法
推 npes89033: 第2個感覺好像有a小題？，不過但看b小題的話應該不存在
→ npes89033: ，因為有六個點的簡單圖最大deg為5，有2個deg5卻有一個
→ npes89033: deg1產生矛盾，所以不存在
→ yad50968: 好的 謝謝大家
推 iwtes: degree sequence 可以把degree最大的那點去掉假設為x  接
→ iwtes: 著在後面x個點的degree全部減1
推 iwtes: 5 5 4 3 2 1  > 4 3 2 1 0 > 3 2 1 0 -1>>出現-1就不可能
→ iwtes: 有這樣的圖出現了
→ iwtes: 5 5 4 3 2 1  > 4 3 2 1 0 >  2 1 0 -1>>出現-1就不可能有
→ iwtes: 這樣的圖出現了