Question

若无向图G=(V,E)中含有7个顶点，要保证G在任何情况下都是连通的，则需要的边数最少是（）条

Answer 1

至少有n条边，正好可以组成一个环。

无向连通图指的是图中的每个顶点都有边与其相连，且图中没有断处，即对无向连通图进行遍历时，仅需要从图中的一个顶点出发。

进行深度优先或广度优先搜索，便可以访问到图中所有的顶点。无向连通图构成的条件是：边数＝顶点数－1。

连通分量的提出是以＂整个无向图不是连通图＂为前提的，因为如果无向图是连通图，则其无法分解出多个最大连通子图，因为图中所有的顶点之间都是连通的。

扩展资料：

无向图到连通图的tarjan算法：

如果两个顶点可以相互连接，则这两个顶点是强连接的。如果有向图G的每个顶点都是强连通的，则G是一个强连通图。有向图的强连通子图是强连通分量。

在下面的图中，子图｛1，2，3，4｝是一个强连接组件，因为顶点1、2、3和4是不明确的。｛5｝和｛6｝也是两个强连接的分量。

利用Tarjan算法求有向图的强连通分量。寻找有向图强连通分量的Tarjan算法是以其发明者RobertTarjan的名字命名的。RobertTarjan也发明了寻找双连通分量的Tarjan算法。

Tarjan算法是基于图深度优先搜索算法的。每个强连接组件都是搜索树中的一个子树。在搜索过程中，将当前搜索树中未处理的节点添加到堆栈中，并且可以追溯到堆栈顶部的节点，以确定它们是否是强连接组件。

定义DFN（u）为u查找的节点的序列号（时间戳），Low（u）为u或u的子树可以跟踪的最早栈中节点的序号。

当DFN（u）＝Low（u）时，以u为根的搜索子树上所有节点是一个强连通分量。

参考资料来源：百度百科—连通图

参考资料来源：百度百科—无向图

参考资料来源：百度百科—tarjan算法