has_eulerian_path#

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

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

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

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

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

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

  • 其他每个顶点的入度和出度相等，

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

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

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

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

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

如果 source 不是 None，则从 source 开始的欧拉路径存在，如果存在欧拉回路或 source 的度数为奇数并且上述条件成立。

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

Parameters:
GNetworkX 图

要查找欧拉路径的图。

source节点, 可选

路径的起始节点。

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

See also

is_eulerian
eulerian_path

Examples

如果你希望允许具有孤立顶点的图具有欧拉路径，可以先移除这些顶点，然后调用 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
On this page