推 VB2005:謝啦。我研究一下 08/16 19:09
→ VB2005:知道了。謝謝 08/16 23:48
※ 引述《VB2005 (DaiJouBu)》之銘言：
: 題目：
: G=(V,E) , |V|＝N,N >= 3
: 若G中恰含一個點,degree是偶數，請問
: G的補圖中,degree偶數的點數是多少？
: ans：1
: 此題，有請版上高手講解。
: 因為課本解答，有看沒有懂…
首先，我們必須先導出 N 的奇偶性
圖論裡面的公式說 Σdeg(v)=2|E|
所以我們可以知道，在圖 G 中所有的點的 degree 加起來會是 2 的倍數
又，其中有一個點的 degree 是偶數，其餘是奇數，所以我們可以知道的是
一個偶數加上 (N-1) 個奇數會等於某個偶數，也就是說 (N-1) 必須是一個偶數
所以， N 是一個奇數。
既然 N 是一個奇數，所以假設 G 中唯一一個偶數 degree 的點的 degree 是 r ，
_
r∈Z_even，其餘點的 degree 為 s, ∀s∈Z_odd ， 又 G+G=Kn
_
所以，每個點與其在 G 中對應的點之 degree 的和為 N-1 。
_
也就是說， G 中偶度數的點，對應其在 G 中，度數為 N-1-r
_
而其他奇度數的點，在 G 中的 degree 為 N-1-s
因為 N 為一個奇數，所以 N-1-r 為一個偶數， N-1-s 為一個奇數
_
也就是說， G 中擁有偶度數的點的個數為 1 。
用了有點多的文字，希望你看得懂。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.184.12
※ 編輯: stillstand 來自: 114.32.184.12 (08/16 14:20)