若无向图G中含有7个顶点,要保证G在任何情况下都是连通的,则需要

2019-12-26 本文已影响0人 Transartlantic

这个题目的意思是，至少需要多少条边，才能让这7个点不管怎么摆放，组成的图都是一个连通图。

A：先证明边数E必须大于16

引理：N个顶点的图最多使用 $\frac{N*（N-1）}{2}$ 条边

根据引理，6个顶点的完全图使用了15条边。（1）

假设边数E小于16，，那么把这7个点和E条边分配成两组

组I: 1个点，0条边

组II: 6个点，E-1条边（ $E-1<15$ )

由（1）可知，组II的6个点最多可以使用15条边，现在有 $E-1<15$ 条边，那么组II必然有 $>=1$ 个图

组1本身就是一个图

所以组1和组2构成 $>=2$ 个图

所以假设不成立，得到 $E>=16$

B：再证明16条边和7个顶点不管什么情况都组成一个连通图

假设它们组成的不是一个连通图，那么假设组成了N个连通图（ $N>=2$ )。每个连通图的定点依次为V1,V2,V3...VN

由引理可知，每个连通图使用的边数最多是 $\frac{Vi*(Vi-1)}{2}$

由于
$\sum_{1}^{N}\frac{Vi*(Vi-1)}{2}<\frac{N(N-1)}{2}+1=16$

小于号右边的情况就是6个顶点组成一个完全图，并且第七个点随便加在6个点之一上。

（这个不等式可以这么理解：顶点数目一定时，连通图越多，使用的最多边数就越少）

所以假设不成立，

证得16条边和7个顶点不管什么情况都组成一个连通图

综合A，B可知16条边是使得7个顶点不管怎么放都能连通的最小边数