Re: [理工] [離散] 90交大
看板Grad-ProbAsk作者Lautreamont (Maldoror is dead)時間16年前 (2010/03/10 12:29)推噓0(0推 0噓 1→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《linesx3 (小李)》之銘言：
: 題目如下
: 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啊,
: 感覺英文好難喔!
: 謝謝指教
(n-1)個點為odd degree
剩下的一個為even
所以(n-1)為even => n為odd
每個點在G與補G的degree加總為(n-1):even
所以原本在G中為odd的點在補G中 degree為odd (odd+odd=even)
even的在補G中仍even (even+even=even)
"all but one vertex"意謂著"除了一個點的其他全部點"
並非"只有一個點"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.244.169
→
03/10 12:30, , 1F
03/10 12:30, 1F
討論串 (同標題文章)