强连通图有n个顶点至少有几条边（强连通图）

大家好,小东方来为大家解答以上的问题。强连通图有n个顶点至少有几条边，强连通图这个很多人还不知道,现在让我们一起来看看吧！

1、不一定，这样的反例有很多：　　对于一个有向图，只要有一个经过所有结点的环路，就成为强连通图。

2、不妨构造一个强连通图，其所有边恰好构成一个环，串联了所有结点；如：a1→a2→a3→……→a1；　　此时，这个图中恰好有一个欧拉回路；即：a1→a2→a3→……→a1；　　然后，在这个图中随便增加一条边；如：< a2，a1 >；　　这样欧拉回路就被破坏了；。

本文到此分享完毕，希望对大家有所帮助。

免责声明：本文由用户上传，如有侵权请联系删除！