教甄◆電腦科專業題庫下載題庫

上一題
36.一個有 9 個點（vertex）的完成圖（complete graph），最少需要拿走幾條邊（edge） 才能變成二分圖（bipartite graph）？
(A)14
(B)16
(C)18
(D)20

答案：B
難度： 非常困難
4F
古佳怡 小六上 (2017/04/18)

complete graph：
共有8+7+...+1 = 36條邊

bipartite graph：
點可以分兩群，群與群之間有邊，群內則沒有邊。
兩群的分法，可能是：1個點對8個點、2個點對7個點、3個點對6個點、4個點對5個點，共有四種分法。
以(1，8)來說，最大可能邊數會是1*8
以(2，7)來說，最大可能邊數會是2*7
以(3，6)來說，最大可能邊數會是3*6
以(4，5)來說，最大可能邊數會是4*5

因此，最少需要去掉(8+7+...+1) - (4*5) = 16 條邊

5F
becky_0li 大一下 (2017/05/11)

計算邊數=(N)*(N-1)/2

二分=分為二群
4個點可形成(4*3)/2=6個邊,
5個點可形成(5*4)/2=10個邊,


6F
109考上台北市! 感恩阿 大四下 (2019/05/09)

分兩群


不見得要4.5


36.一個有 9 個點（vertex）的完成圖（complete graph），..-阿摩線上測驗