[理工] [離散]-圖論

[gn00618777 (123)]

                                            10
Let G=(V,E) be a graph where V={x｜x屬於{0,1}  is a bit string of length 10  }
E={{x,y}|x defferes from y in exactly 2 positions}. Then what is the value
of |E| ?
                             10          10
解法：對於所有v屬於V,deg(v)=C  =45,|V|＝2
                             2

所有deg(x)的和 = 2 |E|

 10
2  *45 = 2|E|

      9
|E| =2 *45
            10
不太懂為何 C     ?
            2

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.168.61.186
推 ianwuzack:長度10 恰兩個位置不同 所以就10個選哪2個位置不同連起
→ ianwuzack:來 那點的線有幾條就是那點的degree是多少
→ gn00618777:我還是不懂 0000000000 不就沒有可以連起來了 哪裡還
→ gn00618777:以選2
→ gn00618777:能否用圖說明一下呢  我覺得好抽象  感謝~"~
→ gn00618777:還有E集合裡的y是指誰
→ yesa315:EX:0000000000 0000000011 這兩點就有邊 差了兩個位子就有
→ yesa315:邊 10個0 與它差兩個位子 一定恰8個0 2個1 再去做排列
→ yesa315:10!/8!*2! = C(10,2) (重複排列 你會吧)
→ yesa315:我這例子只是剛好C(10,2)而已不是那個C(10,2)
→ yesa315:喔 不 我會錯意了 剛我打得那些別看....
→ yesa315:0000000000 與它差兩個位子 eg. 0010000100 0000110000 ..
→ yesa315:全部都是0 你一定要塞兩個1 才會與之相差兩個位子 那個兩
→ yesa315:個1塞哪? 10個位子挑兩個來塞 C(10,2) 假如有01混合的
→ gn00618777:我大概懂了，且聽我這樣解釋是否正確
→ gn00618777:一個位元字串長度10，要相差兩個bits連一條鞭
→ yesa315:則你就要選兩個位子來塞與原本相反的值 例如 xxx0xxxx1x
→ gn00618777:疑？>"<我突然又對C10取2不了了
→ gn00618777:喔喔喔 謝謝指教
→ yesa315:塞與相反的值後變 xxx1xxxx0x 那這兩點就有邊