> 数学 >
证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的.
人气:202 ℃ 时间:2020-03-23 07:11:49
解答
有G和G的补图,K+K(补)=n(n-1)/2
设G不连通,则G的补图是连通,K(补)>=n-1;
k+k(bu)>=k+n-1;
k+k(bu)=n(n-1)/2;
推出k
推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版