证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的.
人气:117 ℃ 时间: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
推荐
猜你喜欢
- 方程:X+y=11,Xy=28,求xy,急
- 300(1+x)平方=400要答案
- 已知递减的等差数列{an}满足a12=a92,则a5=( ) A.-1 B.0 C.-1或0 D.4或5
- 新概念英语第二册 77课课文
- 两包饼干是two packs of 还是two packets of pack packet都有包的意思
- 已知关于x的方程k^2*x^2+(2k-1)x+1=0有两个不相等的实数根x1,x2,一、求k的取值范围;二、是否存在实数k,使方程的两实数根互为相反数?如果存在,求出k的值;如果不存在,请说明理由
- 有一根绳子和一根竹竿,把绳子对折后比竹竿长2米;把绳子4折后比竹竿短2米.竹竿和绳子各长几米?
- 已知圆O的半径为1,AB是圆O的一条弦,且AB=根号3