作者gn00618777 (123)
看板Grad-ProbAsk
标题[理工] [离散]-图论
时间Wed Sep 23 19:22:28 2009
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
1F：推 ianwuzack:长度10 恰两个位置不同 所以就10个选哪2个位置不同连起 09/23 19:41
2F：→ ianwuzack:来 那点的线有几条就是那点的degree是多少 09/23 19:41
3F：→ gn00618777:我还是不懂 0000000000 不就没有可以连起来了 哪里还 09/23 20:01
4F：→ gn00618777:以选2 09/23 20:01
5F：→ gn00618777:能否用图说明一下呢 我觉得好抽象 感谢~"~ 09/23 20:02
6F：→ gn00618777:还有E集合里的y是指谁 09/23 20:24
7F：→ yesa315:EX:0000000000 0000000011 这两点就有边 差了两个位子就有 09/23 20:32
8F：→ yesa315:边 10个0 与它差两个位子 一定恰8个0 2个1 再去做排列 09/23 20:33
9F：→ yesa315:10!/8!*2! = C(10,2) (重复排列 你会吧) 09/23 20:34
10F：→ yesa315:我这例子只是刚好C(10,2)而已不是那个C(10,2) 09/23 20:39
11F：→ yesa315:喔 不 我会错意了 刚我打得那些别看.... 09/23 20:43
12F：→ yesa315:0000000000 与它差两个位子 eg. 0010000100 0000110000 .. 09/23 20:50
13F：→ yesa315:全部都是0 你一定要塞两个1 才会与之相差两个位子 那个两 09/23 20:51
14F：→ yesa315:个1塞哪? 10个位子挑两个来塞 C(10,2) 假如有01混合的 09/23 20:52
15F：→ gn00618777:我大概懂了，且听我这样解释是否正确 09/23 20:53
16F：→ gn00618777:一个位元字串长度10，要相差两个bits连一条鞭 09/23 20:54
17F：→ yesa315:则你就要选两个位子来塞与原本相反的值 例如 xxx0xxxx1x 09/23 20:55
18F：→ gn00618777:疑？>"<我突然又对C10取2不了了 09/23 20:56
19F：→ gn00618777:喔喔喔 谢谢指教 09/23 20:57
20F：→ yesa315:塞与相反的值後变 xxx1xxxx0x 那这两点就有边 09/23 20:57