作者svanavs (svanavs)
看板Grad-ProbAsk
标题Re: [理工] [离散]-图论
时间Wed Sep 23 20:30:30 2009
※ 引述《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
任给 一个 string : 0100011010 , 只要与他有两个digit不一样就与他拉一个边
所以 0
00001101
1 ,
11000
01010 ,
...etc ... 都会跟他拉一个边
给订一个 string 就可决定 C(10,2) 种 strings 与他有两个digit 相异
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.222.93