离散数学图论：用线使n个点构成连通图（即用线来将所有点连起来,注意不是说的欧拉图）除了满足至少需要n也就是求连通图的充要条件

Question

离散数学图论：用线使n个点构成连通图（即用线来将所有点连起来,注意不是说的欧拉图）除了满足至少需要n
也就是求连通图的充要条件

Answer 1

你要的充要条件是不存在的.
我是这么想的,以无向图G=(V,E)为例
假如图中|V|-1个顶点是完全图,再用一条边连接余下的那个顶点.
也就是|E|>=(|V|-1)(|V|-2)/2+1的时候G一定是连通图.
但是反回来G是连通图的时候,边数未必会这么多啊,|E|>=|V|-1即可.
A可以推出B,B可以推出A.我们才称A,B互为充要条件.
一定要的话,那就是每个点的度数大于等于1.即beg(vi)≥1,i=1,2,...,|V|,vi∈V.
注：
图是连通的必要条件
无向图 G=(V,E) 是连通的,那么边的数目大于等于顶点的数目减一：|E|>=|V|-1
如果G=(V,E) 是有向图,它是强连通图,那么边的数目大于等于顶点的数目：|E|>=|V|
|A|表示集合A的基数,也就是元素个数.
|E|表示图的边数
|V|表示图的顶点数.