algorithm - 我们能否将任何无向图转换为有向图，使得每个顶点的入度和出度之差最多为 1？

给定任何无向图 G，是否总有办法为其边添加方向，使得每个顶点的入度和出度之间的差不大于 1？

例如，考虑 G 由顶点 1、2 和 3 以及无向边 1--2、1--3 和 2--3 定义。然后，有向版本 1 -> 2、2 -> 3 和 3 -> 1 使得所有顶点的入度和出度之间的差异为 0。

标签： algorithmgraphnodesdirected-graphundirected-graph

这个问题是关于无向图的方向。

如果每个顶点的入度和出度之间的差为 0，则方向是欧拉方向。事实证明，任何具有所有度的图甚至都具有欧拉方向。只需计算在这种情况下始终存在的欧拉回路，并根据该回路选择方向。

使用这个，同样的问题在这里用一个聪明的技巧解决了：只需添加一个新顶点并将其链接到所有奇数度的顶点，然后计算欧拉方向，并删除额外的顶点！