has_eulerian_path#

has_eulerian_path(G, source=None)[source]#

当且仅当 G 具有欧拉路径时返回 True。

欧拉路径是图中使用每条边恰好一次的路径。如果指定了 source，则此函数检查是否存在从节点 source 开始的欧拉路径。

有向图具有欧拉路径当且仅当

  • 至多一个顶点的出度 - 入度 = 1，

  • 至多一个顶点的入度 - 出度 = 1，

  • 所有其他顶点入度等于出度，

  • 并且其所有顶点都属于底层无向图的单个连通分量。

如果 source 不是 None，则存在从 source 开始的欧拉路径，当且仅当没有其他节点的出度 - 入度 = 1。这等价于存在欧拉回路，或者 source 的出度 - 入度 = 1 且满足上述条件。

无向图具有欧拉路径当且仅当

  • 恰好有零个或两个顶点的度为奇数，

  • 并且其所有顶点都属于单个连通分量。

如果 source 不是 None，则存在从 source 开始的欧拉路径，当且仅当存在欧拉回路，或者 source 的度为奇数且满足上述条件。

具有孤立顶点（即度为零的顶点）的图不被认为具有欧拉路径。因此，如果图不连通（或者对于有向图，不强连通），则此函数返回 False。

参数:
GNetworkX 图

要在其中查找欧拉路径的图。

source节点, 可选

路径的起始节点。

返回:
Bool如果 G 具有欧拉路径，则为 True。

另请参阅

is_eulerian
eulerian_path

示例

如果您希望允许具有孤立顶点的图也拥有欧拉路径，您可以先移除这些顶点，然后像下面的示例所示调用 has_eulerian_path。

>>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
>>> G.add_node(3)
>>> nx.has_eulerian_path(G)
False

>>> G.remove_nodes_from(list(nx.isolates(G)))
>>> nx.has_eulerian_path(G)
True
在此页面上