→ GAZZ1234:你可以畫看看不連通 怎樣才會最多邊 就知道那是顯然地 01/21 23:48
證明 一個 simple graph G有n個點
如果有(n-1)(n-2)/2個邊的話
是connected graph
證明過程
若G 為 disconnected graph
則G 中含 r 個 components Gi=(Vi,Ei) i=1.2.3....r,r>=2
當每個component皆為 complete graph時具有最多邊數
因此邊數為
sigma (ni 取2),n1+n2+....+nr=n
i=1 to r
小黃老師的解答上寫說
很顯然地當r=2時具最多邊數(n1 2)+(n2 2) n1+n2=n
~~~~~~~~~~~~~~~~~
請問為甚麼r=2的時候有最多邊數阿?
式子展開之後
2 2
=n1 -n*n1+(n - n)
為甚麼當n1= 1 或 n-1具有最大值阿?
p.s不知道為甚麼在word打了sigma的符號複製進ptt變成國字
sigma 是連加的符號
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.127.25