We would like to construct roads for 5 villages such that no village is isolated . How many ways can we do this ?
我的想法只到下面這裡而已
希望有高人指點
謝謝
假設村莊為abcde。因為村莊有五個，使其不孤立，''至少''需要四個邊
示意圖如下：
a-b-c-d-e
因為abcde彼此可互換，仍可使五個村莊不孤立。
所以是 ''5！''
但題目沒規定路有幾條
所以我的想法只到這邊而已
謝謝回答
8 則留言:
用圖論
突然想到有個 Kn*的spanning tree個數公式可以用-->n^(n-2)即其個數。但spanning tree並無cycle，所以仍然會少算了題目所要求的條件(使其不孤立即可)。希望有同學可以幫忙解惑。
先前貼了才發現自己想的不夠周延。應該可以利用排容原理：
S0=2^(5,2)=1024(5個vertexes的simple graph數)
令Ai為有i個isolated vertex的性質
S1=N(A1)=(5,1)*2^(4,2)=5*64=320
S2=N(A2)=(5,2)*2^(3,2)=10*8=80
S3=N(A3)=(5,3)*2^(2,2)=10*2=20
S4=N(A4)=(5,4)*2^(1,2)=5*1=5
S5=N(A5)=(5,5)*2^(0,2)=1*1=1
所以有1024-320+80-20+5-1=768種
如果"使其不孤立"的意思是，沒有孤立點，那就是算 5 個點而且沒有孤立點的圖；如果"使其不孤立"的意思是要連通，那就是算 5 個點的連通圖。
張貼留言