Re: [理工] 離散圖論
請問哪兒想不通呢？
_
兩圖isomorphic的話就代表node數edge數一樣 所以|E| = |E|
complete graph的edge數 = n(n-1)/2
_
G和G邊數加起來跟complete graph一樣
_
|E| + |E| = 2|E| = n(n-1)/2
|E| = n(n-1)/4
所以 4 | n or 4 | (n-1) → n = 4k or n = 4k+1
還有哪兒想不通呢？
※ 引述《Demonic221 (J)》之銘言：
: If G and G吧 are isomorphic, then G is self-complement. Show that if G=(V,E)
: is self-complement and |V| = n, then n = 4k or 4k+1, k屬於正整數.
: 這題最後的證明結果是:
: |E|=|E吧| & 2|E| = n(n-1)/2 --> |E| = n(n-1)/4
: 故 n = 4k or 4k+1 ,k屬於正整數
: 可是我還是想不通耶xD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.104.205
推
01/12 20:38, , 1F
01/12 20:38, 1F
討論串 (同標題文章)
