[圖論] Simple Graph

看板Math作者 (註定的孤獨)時間14年前 (2011/09/28 11:38), 編輯推噓2(2推 0噓 7→)
留言9則, 5人參與, 最新討論串1/2 (看更多)
有一個簡單的 Simple Graph的問題想要問問大家.. 題目如下： Is There a simple graph with 6 vertices of respective degrees 1,2,2,2,3 and 4. 碰到的問題是我不太懂怎麼做像這種有重複點的題目..|| 感覺算蠻基本的題目，想要弄懂，有人可以回答我嗎Orz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 130.216.30.112
→
09/28 12:07, , 1F
是不是畫一畫就出來了？答案應該是肯定的。
09/28 12:07, 1F
先謝謝您的回應。 其實這題是有兩個題目，一個是0,1,2,3,4,5 ←這個我還畫的出來 但是另一題我有點卡在222不會畫Orz|| ※ 編輯: sayane 來自: 130.216.30.112 (09/28 12:12)
推
09/28 12:34, , 2F
先畫 deg 4, 再畫 deg 3 就畫出來了
09/28 12:34, 2F
→
09/28 12:45, , 3F
0,1,..,5 是不可能的
09/28 12:45, 3F
推
09/28 21:15, , 4F
可以查查 degree sequence 之類的
09/28 21:15, 4F
→
09/28 21:16, , 5F
Erdos–Gallai theorem給出了如何判定所給的degree
09/28 21:16, 5F
→
09/28 21:16, , 6F
sequence是不是簡單圖, 而 Havel-Hakimi Theorem
09/28 21:16, 6F
→
09/28 21:17, , 7F
則除了判定外 順便給出了製作一個相對應的圖的方法
09/28 21:17, 7F
→
09/28 21:17, , 8F
當然可能不同的圖對應到同樣的degree sequence...
09/28 21:17, 8F
→
09/28 22:17, , 9F
謝謝大家的回覆O_Q 搞懂了一些東西了
09/28 22:17, 9F
‣ 更多 sayane 的文章
文章代碼(AID): #1EWfQOCi (Math)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 sayane 的文章
文章代碼(AID): #1EWfQOCi (Math)