[理工] [離散] Euler Formula的推廣證明

看板Grad-ProbAsk作者 (somo)時間14年前 (2010/02/20 04:12), 編輯推噓3(3推 0噓 8→)
留言11則, 6人參與, 最新討論串1/1
對一個無迴圈的簡單連通平面圖G來講 若V=點數、E=邊數、R=區域數 則 (3/2)R <= E <= 3V-6 其證明為：因每個區域至少含3邊，一個邊最多若在2個區域邊界上 ---(1) 所以 3R <= 2E ---(2) (以下略) 我想問的是 從(1)到(2)其中的邏輯推理該如何想呢？ 還有就是為什麼是大於等於 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.126.161.116
推
02/20 08:25, , 1F
v-e+r=2
02/20 08:25, 1F
→
02/20 10:06, , 2F
假設N為所有region上的邊數總和,每個region至少含三邊,所以
02/20 10:06, 2F
→
02/20 10:07, , 3F
N>=3R,而每邊最多與兩個Region相接,所以N<=2E
02/20 10:07, 3F
→
02/20 12:38, , 4F
樓上正解
02/20 12:38, 4F
→
02/20 18:13, , 5F
請問"所有region上的邊數總和"代表的是E嗎？
02/20 18:13, 5F
→
02/20 18:15, , 6F
還是說每一個region的邊各加起來 即三角形的話N=6
02/20 18:15, 6F
→
02/20 18:15, , 7F
四角形的話N=8?
02/20 18:15, 7F
推
02/20 18:17, , 8F
是有重複的
02/20 18:17, 8F
→
02/20 18:28, , 9F
所以單純一個三角形的話 有一個內部region和外部region
02/20 18:28, 9F
→
02/20 18:28, , 10F
所以N=3+3=6 是這樣子理解嗎?
02/20 18:28, 10F
推
02/24 09:36, , 11F
圖的region數不會比全部region都只用三個edge的R數多
02/24 09:36, 11F
‣ 更多 yyc1217 的文章
文章代碼(AID): #1BVl33Vj (Grad-ProbAsk)