欧拉算法#
在本教程中，我们将探讨欧拉算法及其在 NetworkX 中的实现，具体位于 networkx/algorithms/euler.py。
导入包#
import networkx as nx
柯尼斯堡七桥问题#
您在下方看到的是美丽的柯尼斯堡老城，它因其七座桥梁而闻名。这些桥梁中的每一座都连接着两座大岛——克奈普霍夫岛和洛姆泽岛——或城市的两块大陆部分。
这座城市声名鹊起的原因是一个大约在300年前向数学家莱昂哈德·欧拉提出的问题[1]
你能否走遍柯尼斯堡的每一块陆地，并且每座桥梁恰好只经过一次？
欧拉对这个问题的否定性解答奠定了图论的基础。在深入探讨欧拉的解法之前，让我们重新表述一下这个问题。
用抽象术语重新表述问题#
为了看得更清楚，我们应该先稍微简化一下地图。
欧拉观察到，在每块陆地内部选择路线是无关紧要的。唯一重要的是要经过的桥梁的顺序。这一观察使我们能够进一步抽象化问题。在下面的图中，蓝色顶点代表陆地，边代表连接它们的桥梁。
# Create graph
G = nx.DiGraph()
G.add_edge("A", "B", label="a")
G.add_edge("B", "A", label="b")
G.add_edge("A", "C", label="c")
G.add_edge("C", "A", label="d")
G.add_edge("A", "D", label="e")
G.add_edge("B", "D", label="f")
G.add_edge("C", "D", label="g")
positions = {"A": (0, 0), "B": (1, -2), "C": (1, 2), "D": (2, 0)}
# Visualize graph
nx.draw_networkx_nodes(G, pos=positions, node_size=500)
nx.draw_networkx_edges(
G, pos=positions, edgelist=[("A", "D"), ("B", "D"), ("C", "D")], arrowstyle="-"
)
nx.draw_networkx_edges(
G,
pos=positions,
edgelist=[("A", "B"), ("B", "A"), ("C", "A"), ("A", "C")],
arrowstyle="-",
connectionstyle="arc3,rad=0.2",
);
基于这种抽象，我们可以将问题转述如下
你能否不抬笔且不在同一条线上重复画地画出上面的图？
如果可以，这意味着图中有欧拉路径。如果这条路径的起点和终点是同一个蓝色圆圈，则称为欧拉回路。
注意，每条欧拉回路也是一条欧拉路径。
欧拉方法#
欧拉[2]用大写字母\(A\)、\(B\)、\(C\)和\(D\)表示城市的陆地块，用小写字母\(a\)、\(b\)、\(c\)、\(d\)、\(e\)、\(f\)和\(g\)表示桥梁。让我们根据这些节点和边的标签来绘制图。
# Design and draw graph
edge_labels = nx.get_edge_attributes(G, "label")
nx.draw_networkx_nodes(G, pos=positions, node_size=500)
nx.draw_networkx_labels(G, pos=positions, font_color="w")
nx.draw_networkx_edges(
G, pos=positions, edgelist=[("A", "D"), ("B", "D"), ("C", "D")], arrowstyle="-"
)
nx.draw_networkx_edges(
G,
pos=positions,
edgelist=[("A", "B"), ("B", "A"), ("C", "A"), ("A", "C")],
arrowstyle="-",
connectionstyle="arc3,rad=0.2",
)
nx.draw_networkx_edge_labels(G, pos=positions, edge_labels=edge_labels, label_pos=0.2);
他将他的逻辑描述如下
如果我们经过桥梁\(a\)，我们从\(A\)走到\(B\)。在这种情况下，我们的行程路线记作\(AB\)。
如果我们先经过\(a\)然后经过\(f\)，我们的路线将是\(ABD\)。
因此，连续使用\(n\)座桥梁，其路线表示为\(n+1\)个大写字母。
由于我们需要经过全部7座桥梁，我们的路线应该由长度为8的\(A\)、\(B\)、\(C\)和\(D\)的序列组成。
他还阐述了一个事实：每块陆地在路线中出现的次数取决于它拥有的桥梁数量。
\(A\)有5座桥。这5座桥都应该在我们的欧拉路径中恰好出现一次。那么，\(A\)应该在我们的路线中出现3次。
\(B\)有3座桥。它应该在路线中出现2次。
\(C\)有3座桥。它应该在路线中出现2次。
\(D\)有3座桥。它应该在路线中出现2次。
那么，路线的总长度应该是 3 + 2 + 2 + 2 = 9。
显然，我们不能同时满足这两个条件。因此，欧拉得出结论，柯尼斯堡七桥问题无解（即柯尼斯堡没有欧拉路径）。
推广欧拉的解法#
欧拉将他应用于柯尼斯堡问题的方法推广如下
当且仅当图中度数为奇数的顶点数量为零或二时，该图才存在欧拉路径。
如果有两个度数为奇数的顶点，那么它们就是起点和终点。
如果没有度数为奇数的顶点，任何顶点都可以作为起点或终点，并且图也存在欧拉回路。
NetworkX 中的欧拉算法#
NetworkX 使用欧拉算法实现了一些方法。它们是：
is_eulerian：图是否具有欧拉回路
eulerian_circuit：图中欧拉回路的边序列。
eulerize：将图转换为欧拉图
is_semieulerian：图是否具有欧拉路径但不具有欧拉回路。
has_eulerian_path：图是否具有欧拉路径。
eulerian_path：图中欧拉路径的边序列。
在这部分，我们将通过解释其中一些方法来简要说明 NetworkX 中欧拉算法的实现。
注意：NetworkX 的实现不允许具有孤立节点的图拥有欧拉路径和/或欧拉回路。因此，欧拉路径或欧拉回路必须访问图中的所有边，同时也访问所有顶点。
1. 欧拉回路的实现#
is_eulerian 方法的实现相当简单。为了具有欧拉回路（即成为欧拉图），
有向图必须是强连通的，并且其每个顶点的入度和出度必须相等。
无向图必须是连通的，并且不能有度数为奇数的顶点。
这是一个例子
T = nx.Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (2, 3), (2, 4)])
nx.draw(
T, with_labels=True, node_size=1000, font_color="White", node_color="darkorange"
)
def is_eulerian(G):
if G.is_directed():
return all(
G.in_degree(n) == G.out_degree(n) for n in G
) and nx.is_strongly_connected(G)
else:
return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G)
is_eulerian(T)
True
NetworkX 还实现了 eulerian_circuit 方法来确定构成欧拉回路的边序列。
该方法使用栈数据结构来保存顶点，它从源顶点开始并推入栈中。在每次后续迭代中，它从栈中弹出一个顶点，选择它的一个邻居，将选择的顶点推入栈中，并从图中移除选择的边。
circuit = []
if G.is_directed():
degree = G.out_degree
edges = G.out_edges
else:
degree = G.degree
edges = G.edges
vertex_stack = [0]
last_vertex = None
while vertex_stack:
current_vertex = vertex_stack[-1]
circuit.append(current_vertex)
if G.degree(current_vertex) == 0:
if last_vertex is not None:
break
last_vertex = current_vertex
vertex_stack.pop()
else:
_, next_vertex = next(iter(G.edges(current_vertex)))
vertex_stack.append(next_vertex)
G.remove_edge(current_vertex, next_vertex)
2. 欧拉路径的实现#
Networkx 的 has_eulerian_path 实现首先检查图是否 is_eulerian。记住，如果一个图是欧拉图（即具有欧拉回路），那么它也具有欧拉路径。
def has_eulerian_path(G, source=None):
if nx.is_eulerian(G):
return True
如果一个无向图不是欧拉图，它仍然可能是半欧拉图，这意味着它可能存在起点和终点不同的欧拉路径。如上所述，这当且仅当以下条件满足时才可能发生：
恰好有两个度数为奇数的顶点，并且
其所有顶点都属于一个连通分量。
如果用户提供了源顶点，则该顶点必须具有奇数度。否则，从给定的源顶点开始将无法存在欧拉路径。
if G.is_directed() == False:
if source is not None and G.degree[source] % 2 != 1:
return False
return(sum(d % 2 == 1 for _, d in G.degree()) == 2 and nx.is_connected(G))
对于有向图而言，要拥有欧拉路径，它必须满足以下条件：
至多一个顶点的出度 - 入度 = 1，
至多一个顶点的入度 - 出度 = 1，
所有其他顶点的入度和出度相等，并且
其所有顶点都属于其基础无向图的单个连通分量（即应该是弱连通的）。
if G.is_directed():
ins = G.in_degree
outs = G.out_degree
if source is not None and outs[source] - ins[source] != 1:
return False
unbalanced_ins = 0
unbalanced_outs = 0
for v in G:
if ins[v] - outs[v] == 1:
unbalanced_ins += 1
elif outs[v] - ins[v] == 1:
unbalanced_outs += 1
elif ins[v] != outs[v]:
return False
return (
unbalanced_ins <= 1 and unbalanced_outs <= 1 and nx.is_weakly_connected(G)
)
利用已经实现的方法，is_semieulerian 只需一行代码即可简单地检查输入图是否不具有欧拉回路但具有欧拉路径。
def is_semieulerian(G):
return has_eulerian_path(G) and not is_eulerian(G)
3. 示例#
让我们在柯尼斯堡七桥问题上调用上述方法。出于上面解释的原因，我们预计我们的图既不具有欧拉回路，也不具有欧拉路径。
nx.is_eulerian(G)
False
nx.has_eulerian_path(G)
False
我们可以用另一个例子来结束本节。你期望轮图具有欧拉路径吗？
W = nx.wheel_graph(6)
nx.draw(W, with_labels=True, node_size=1000, font_color="White", node_color="green")
答案是否定的！除了中心节点外，轮图中的所有节点都恰好有3条边。因此，它不能具有欧拉路径。
nx.has_eulerian_path(W)
False
欧拉无处不在！#
欧拉算法对于任何使用路径的人或事物都至关重要。它的一些实际应用示例包括：
解决许多复杂问题，例如上面解释的柯尼斯堡七桥问题。
邮递员可以使用欧拉路径来规划一条不需要重复经过之前走过的路段的路线。
对画家、垃圾收集、飞机驾驶员、GPS开发者（例如谷歌地图开发者）有用。