Re: [理工] [離散]圖論求cut set之相關定義
※ 引述《sroeud7l (Teddy Bear)》之銘言：
: 雖然有答案 但定義看不懂
: 一Kn求
: <a>two equal subgraph之size of such a cut set
: <b>equal bi-partion of the graph之total number of all possible cut sets
: 看不懂這兩者有何不同?
: Ans:
: <a> (n/2)*(n/2)=n^2/4
: <b>相當於將 n 個點分堆, 且兩邊的大小要一樣, 所以共有 c(n,n/2) 種
<a>
這題感覺是要問 cut set有幾個邊
也就是你要切掉幾個邊才可以讓這各一半的點都斷開
因為是完全圖 所以任兩點都有邊相連
然後因為要切成兩邊一樣大小 所以各n/2個點
每點連到另一邊的每個點各n/2條邊 所以一組cut set的size就是(n/2)*(n/2)
<b>
這題這是問有幾種切法 也就是有幾種分法可以分出兩邊一樣的圖
然後因為兩邊的點只要確定出來 切法就必定唯一(把相連的邊都cut掉)
所以只要決定如何分成兩邊 就決定出一組cut set
又題目要求兩邊size一樣 也就是各n/2點
所以分堆方法就是 C(n,n/2) 種
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.226.226
→
01/17 16:17, , 1F
01/17 16:17, 1F
討論串 (同標題文章)