[理工] [離散] 90交大

看板Grad-ProbAsk作者 (小李)時間14年前 (2010/03/10 11:25), 編輯推噓4(4推 0噓 13→)
留言17則, 6人參與, 最新討論串1/2 (看更多)
題目如下 4 An undirected graph G has n verties and all but one vertex of G are of odd degree. (a)What are the possible values of n ? (b)How many vertices of odd degree are there in the complement of G? 我的問題是:題目是指說在G中只有一個點的degree是odd嗎?但這不是不合圖論第一定裡嗎 還是說這個英文是說除了一個點之外其他點都是odd degree啊, 感覺英文好難喔! 謝謝指教 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.119.164.166 ※ 編輯: linesx3 來自: 140.119.164.166 (03/10 11:26) ※ 編輯: linesx3 來自: 140.119.164.166 (03/10 11:27)
→
03/10 11:30, , 1F
除了一個點之外
03/10 11:30, 1F
→
03/10 11:31, , 2F
其實你發現不合定理的時候->沒辦法算->大膽用另一個想法吧
03/10 11:31, 2F
推
03/10 11:31, , 3F
除了一個點之外+1
03/10 11:31, 3F
→
03/10 12:04, , 4F
除了一個點外,其他點都是odd degree
03/10 12:04, 4F
→
03/10 12:12, , 5F
請問這一題怎樣解呢 ?
03/10 12:12, 5F
推
03/10 12:18, , 6F
(a)n is odd and n>1,這樣degree加起來才會是偶數
03/10 12:18, 6F
推
03/10 12:19, , 7F
這題要用偶、奇數相加減的結果是否為偶奇數的觀點解
03/10 12:19, 7F
→
03/10 12:22, , 8F
(a)n為odd (b)邊數：完全G = G + G補
03/10 12:22, 8F
→
03/10 12:22, , 9F
(b)n-1個,原本為奇數degree的點在這個補圖還是奇數
03/10 12:22, 9F
→
03/10 12:23, , 10F
嗯嗯 感謝回答 我也知道是要奇數個 可是沒解答很不踏實..
03/10 12:23, 10F
→
03/10 12:24, , 11F
講錯,(a)n=0也可以
03/10 12:24, 11F
→
03/10 12:24, , 12F
1
03/10 12:24, 12F
→
03/10 12:24, , 13F
1
03/10 12:24, 13F
→
03/10 12:25, , 14F
XD
03/10 12:25, 14F
→
03/10 12:29, , 15F
(b)有什麼直觀一點的想法嗎 ? 雖然畫圖可以知道...
03/10 12:29, 15F
推
03/10 12:31, , 16F
degree(v)+degree(v補)=n-1,n是odd的話,n-1就是even囉
03/10 12:31, 16F
→
03/10 12:32, , 17F
嗯嗯 感謝樓上
03/10 12:32, 17F
‣ 更多 linesx3 的文章
文章代碼(AID): #1Bbn4OnG (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 linesx3 的文章
文章代碼(AID): #1Bbn4OnG (Grad-ProbAsk)