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

答案：登入後查看
統計： A(13), B(57), C(50), D(9), E(0) #601667

詳解 (共 6 筆)

#886538
9個點的完成圖共有(9*8)/2=36個邊
二分圖是將9個點分為二群,故一群為4個點,另一群為5個點,
4個點可形成(4*3)/2=6個邊,
5個點可形成(5*4)/2=10個邊,
故需拿走群內的連結邊 6+10=16個邊。
註：無向圖的邊數為﹝n*(n-1)﹞/2 , n為點的數目
6
0
#2141168
complete graph：共有8+7...
(共 238 字，隱藏中）
前往觀看
5
0
#2183905
計算邊數=(N)*(N-1)/2二分=分...
(共 62 字，隱藏中）
前往觀看
4
0
#963204
不是問最少需要拿走幾條邊嗎?為什麼不是36-16=20個邊?謝謝!!
2
0
#1009603
為什麼不是20？
1
0
#3338182
分兩群不見得要4.5
(共 12 字，隱藏中）
前往觀看
0
0