謝謝大大的回覆
因為我是依靠畫圖來想的
但覺得有點混亂
※ 引述《jameschou (DOG)》之銘言：
<a> cut set size
例K4
○一○ 即 一 一
| Ｘ | Ｘ 或 ｜Ｘ｜ 或 ｜ ｜
○一○ 一 一
反正總數就是4條
: <b>
: 這題這是問有幾種切法 也就是有幾種分法可以分出兩邊一樣的圖
: 然後因為兩邊的點只要確定出來 切法就必定唯一(把相連的邊都cut掉)
: 所以只要決定如何分成兩邊 就決定出一組cut set
: 又題目要求兩邊size一樣 也就是各n/2點
: 所以分堆方法就是 C(n,n/2) 種
所以若以K4來想 C(4,2)=6
○:點
○一○
| X |
○一○
虛線
就有 vv
○ ○ | ○一○ | ○ ○ | ○---○ | ○ ○ | ○ ○
| | | | Ｘ | | ! ! | ' '
○ ○ | ○一○ | ○ ○ | ○---○ | ! ! | ' '
列各成1組 ○ ○ ○ ○
每組內不相連 行各成一組 對角各成一組
每組內不相連 每組內不相連
這6種分法 是這樣想嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.69.54.7
※ 編輯: sroeud7l 來自: 210.69.54.7 (01/18 08:49)
※ 編輯: sroeud7l 來自: 210.69.54.7 (01/18 08:49)