chain_decomposition#
- chain_decomposition(G, root=None)[源代码]#
返回图的链分解。
这个 链分解 关于深度优先搜索树的图是以以下方式从树的基本圈的集合导出的圈或路的集合。考虑关于给定树的每个基本循环,表示为从远离树根的非树边缘开始的边的列表。对于每个基本周期,如果它与之前的任何基本周期重叠,只需取最初不重叠的部分,这是一条路径而不是一个周期。每个循环或路径都称为 链式 。有关详细信息,请参阅 [1].
- 参数
- G无向图
- root节点(可选)
图中的一个节点
G
。如果指定,则只返回包含此节点的已连接组件的链分解。该节点指示深度优先搜索树的根。
- 产量
- chain列表
表示链的边的列表。不能保证每个链中的边的方向(例如,如果链包括连接节点1和2的边,则链可能包括(1,2)或(2,1))。
- 加薪
- NodeNotFound
如果
root
不在图表中G
.
笔记
该实现的最坏运行时间与结点数和边数成线性关系 [1].
工具书类
- 1(1,2)
Jens M.Schmidt(2013年)。”对2顶点和2边缘连接的简单测试。” 信息处理信函 ,113,241–244。爱思唯尔。<https://doi.org/10.1016/j.ipl.2013.01.016>