在圖論中老師提到一題我沒能馬上體會，希望能位我解說一下。
G=(V,E) , V=n
G中恰有一Degree為Even，問"G爸"中有幾個點Degree為Even?
解說是因為G和G爸的Degree和會是n-1
所以 deg (G爸)(v) ＝ （n - 1）- deg(G)(v)
因為定理加上deg(G)(v)是偶數，所以(n-1)將會是偶數，這樣deg(G爸)(v)才會合理
以上是我目前的想法，但是要怎樣想才能推出答案是一個呢？
Research Space for Linear Algebra & Discrete Mathematics
4 則留言:
因為如果你現在看的是偶數點
deg(g爸)=(N-1)-deg(G)(偶點)
(因為G+G爸是完全圖，所以在補圖中的deg要扣掉原圖的deg)
那只有一個是偶數點，其餘是奇數點，又奇數點必偶個故N-1是偶數，所以偶數減偶度數必偶
接著看奇數點，deg(g爸)=(N-1)-deg(G)(奇點)，
你看著現在的奇數點，因為奇數點必偶個，扣掉你現在看的這一個，剩下的奇數點剩 奇數個+偶數點 所以N-1是偶數，偶-奇度數=奇數
所以偶數點在補圖中也是1個
有點饒舌希望你能看得懂
因為依照全圖來看的話
全圖的邊數=G的邊數加上我G霸的邊數=C的n取2
ps: |V|=n 代表點的個數
其中:C的n取2這個數=n(n-1)/2為偶數
而討論n跟n-1就像你說的根據第一定理的推廣可以知道n-1為偶數,因為我只有1個點的deg為偶數,代表我剩下n-1個點的degree均為奇數,而degree為奇數的點數又必為偶數個,所以n-1為偶數
再利用
全圖中一個點v可多連n-1個邊
題目告訴我們在G中只有一個點的degree為偶數
代表這個點在G霸中的degree也是偶數
因為偶數 -偶數 =偶數
ps: deg(G)-(n-1) =deg(G霸)
而其他n-1個點因為在G中degree為奇數
,在G霸中其degree亦為奇數
因為奇數 -偶數 =奇數
ps: deg(G)-(n-1) =deg(G霸)
所以在G霸中只有一個點的degree為偶數
希望有解決你的困擾
不好意思~更正一下,在第二段中,
C的n取2這個數=n(n-1)/2為一個整數,令為m,所以可以知道n(n-1)=2m為偶數
張貼留言