Question

n个结点的有向图，至少需要多少条弧才能构成强连通图

Answer 1

强连通图必须从任何一点出发都可以回到原处，每个节点至少要一条出路(单节点除外)，至少有n条边，正好可以组成一个环。

n在有向图G中，如果对于任何两个不相同的点a，b，从a到b和从b到a都存在路径，则称G是强连通图。

这里的有向图，应该指强连通有向图。如果允许孤点，有1条弧也行。

强连通有向图，满足两个条件：

（1）没有孤点；

（2）任何两点A、B，至少存在1条路径，从A到B；也至少存在1条路径，从B到A。

A>B>C>D,A-->D,存在；D--->A不存在。

n个顶点排在一个圆周上，需要的弧最少。n条。

扩展资料：

一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

证明：

（1）充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。

（2）必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。

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

Answer 2

强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路(单节点除外)
至少有n条边,正好可以组成一个环！