证明 一个 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