[理工] [離散]-圖論

看板Grad-ProbAsk作者 (123)時間14年前 (2009/09/23 19:22), 編輯推噓1(1推 0噓 19→)
留言20則, 3人參與, 最新討論串1/6 (看更多)
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
推
09/23 19:41, , 1F
長度10 恰兩個位置不同 所以就10個選哪2個位置不同連起
09/23 19:41, 1F
→
09/23 19:41, , 2F
來 那點的線有幾條就是那點的degree是多少
09/23 19:41, 2F
→
09/23 20:01, , 3F
我還是不懂 0000000000 不就沒有可以連起來了 哪裡還
09/23 20:01, 3F
→
09/23 20:01, , 4F
以選2
09/23 20:01, 4F
→
09/23 20:02, , 5F
能否用圖說明一下呢 我覺得好抽象 感謝~"~
09/23 20:02, 5F
→
09/23 20:24, , 6F
還有E集合裡的y是指誰
09/23 20:24, 6F
→
09/23 20:32, , 7F
EX:0000000000 0000000011 這兩點就有邊 差了兩個位子就有
09/23 20:32, 7F
→
09/23 20:33, , 8F
邊 10個0 與它差兩個位子 一定恰8個0 2個1 再去做排列
09/23 20:33, 8F
→
09/23 20:34, , 9F
10!/8!*2! = C(10,2) (重複排列 你會吧)
09/23 20:34, 9F
→
09/23 20:39, , 10F
我這例子只是剛好C(10,2)而已不是那個C(10,2)
09/23 20:39, 10F
→
09/23 20:43, , 11F
喔 不 我會錯意了 剛我打得那些別看....
09/23 20:43, 11F
→
09/23 20:50, , 12F
0000000000 與它差兩個位子 eg. 0010000100 0000110000 ..
09/23 20:50, 12F
→
09/23 20:51, , 13F
全部都是0 你一定要塞兩個1 才會與之相差兩個位子 那個兩
09/23 20:51, 13F
→
09/23 20:52, , 14F
個1塞哪? 10個位子挑兩個來塞 C(10,2) 假如有01混合的
09/23 20:52, 14F
→
09/23 20:53, , 15F
我大概懂了，且聽我這樣解釋是否正確
09/23 20:53, 15F
→
09/23 20:54, , 16F
一個位元字串長度10，要相差兩個bits連一條鞭
09/23 20:54, 16F
→
09/23 20:55, , 17F
則你就要選兩個位子來塞與原本相反的值 例如 xxx0xxxx1x
09/23 20:55, 17F
→
09/23 20:56, , 18F
疑？>"<我突然又對C10取2不了了
09/23 20:56, 18F
→
09/23 20:57, , 19F
喔喔喔 謝謝指教
09/23 20:57, 19F
→
09/23 20:57, , 20F
塞與相反的值後變 xxx1xxxx0x 那這兩點就有邊
09/23 20:57, 20F
‣ 更多 gn00618777 的文章
文章代碼(AID): #1AkWJro7 (Grad-ProbAsk)
‣ 更多 gn00618777 的文章
文章代碼(AID): #1AkWJro7 (Grad-ProbAsk)