[其他] [圖論]degree和的問題

看板Math作者 (3.14159265358979)時間7年前 (2018/03/19 18:54), 7年前編輯推噓3(3推 0噓 4→)
留言7則, 2人參與, 7年前最新討論串1/1
The non-negative integer d_1, ..., d_n are the vertex degrees of some graph if and only if \sigma d_i is even. (=>) 這個方向用degree sum formula (<=) 但這個方向只想到 odd degree 的數量是偶數 接下來就不知道怎麼做了 麻煩版上大神指點 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.209.214 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1521456854.A.496.html
推
03/19 19:08, 7年前 , 1F
看起來應該是 multigraph, 那建個圖出來不太難
03/19 19:08, 1F
L大可以稍微解釋一下怎麼建嗎？ ※ 編輯: ohyesiamhone (111.82.209.214), 03/19/2018 19:10:42
推
03/19 19:41, 7年前 , 2F
奇點成對連一連就剩偶數, 然後用圈吃掉所有人的 2
03/19 19:41, 2F
請問, 用圈吃掉所有人的2是什麼意思? 不好意思, 初學者比較不了解 ※ 編輯: ohyesiamhone (123.240.209.162), 03/19/2018 20:25:40
推
03/19 20:34, 7年前 , 3F
喔, 我講太簡略了: 注意到一個圈可以用掉其上所有點
03/19 20:34, 3F
→
03/19 20:35, 7年前 , 4F
各兩個 degree, 所以就用一個一個圈把所有偶數減到0
03/19 20:35, 4F
證明順序了解了, 但想問為什麼這樣就可以說這些degree可以畫出一個圖? 問題有點多, 先謝謝L大大了 ※ 編輯: ohyesiamhone (123.240.209.162), 03/19/2018 20:40:43
→
03/20 18:52, 7年前 , 5F
你可以每個點自己連自己，然後奇點兩個兩個互連
03/20 18:52, 5F
→
03/20 18:54, 7年前 , 6F
或著是 degree 最小的和 degree 第二小的互連
03/20 18:54, 6F
→
03/20 18:55, 7年前 , 7F
然後第二小的再去連第三小的，以此類推
03/20 18:55, 7F
‣ 更多 ohyesiamhone 的文章
文章代碼(AID): #1QhvRMIM (Math)