問題詳情

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

參考答案

答案：B
難度：適中0.47
統計：A(9),B(47),C(37),D(7),E(0)

用户評論

【澐】評論

【古佳怡】評論

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 條邊

【becky_0li】評論

計算邊數=(N)*(N-1)/2二分=分為二群