一个简单的强连通图及一个联通分量

强连通图（Strongly Connected Graph）是指一个有向图（Directed Graph）中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径的图。

性质定理：

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

证明：

充分性

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

必要性

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

参考资料论文

书籍

1、《图论》（英文版，Graph Theory），作者：（加）W.T. Tutte，机械工业出版社，2004年9月第1版，ISBN： 7-111-14980-7

网站

 

 

免责声明：本文为网络用户发布，其观点仅代表作者个人观点，与本站无关，本站仅提供信息存储服务。文中陈述内容未经本站证实，其真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。