如何通过添加最少平行边将非欧拉路径转换为欧拉路径？

首先明确核心逻辑：我们要让图满足欧拉路径的存在条件——因为欧拉路径恰好遍历每条边一次，添加平行边就对应让原边被遍历两次（原边+平行边各走一次），刚好符合「每条边至少1次、至多2次」的要求。

基础前提 #

欧拉路径的判定（针对连通无向图，不连通的话每个分量单独处理）：

• 所有节点度数都是偶数 → 存在欧拉回路（起点终点相同的欧拉路径）
• 恰好2个节点度数是奇数 → 存在欧拉路径（从一个奇度数节点出发，到另一个结束）

添加一条平行边会让它的两个端点度数各+1，也就是翻转这两个节点的度数奇偶性。我们的目标就是用最少的这种翻转，把图的奇度数节点数调整到0或2。

具体步骤 #

1. 统计奇度数节点数量，记为k（图论的基本结论：图中奇度数节点的数量必为偶数）。
2. 根据k值执行对应操作：
   • 若k=0：无需添加任何边，直接走欧拉回路即可，每条边仅遍历1次。
   • 若k=2：无需添加任何边，直接走欧拉路径（从一个奇度数节点出发，到另一个奇度数节点结束），每条边仅遍历1次。
   • 若k>2：
     • 核心是将这些奇度数节点两两配对，每完成一对配对，就通过添加平行边让这两个节点的度数变为偶数。
     • 优先选择直接有边相连的奇节点对，给这条边加一条平行边——一次操作就能让两个奇节点变偶，减少2个奇节点，仅需添加1条边，效率最高。
     • 如果两个奇节点之间没有直接边，就找它们之间的最短路径，通过给路径上的边添加平行边间接完成配对：比如路径u-a-v，给u-a加平行边（翻转u和a的奇偶性），再给a-v加平行边（翻转a和v的奇偶性），最终u和v的奇偶性翻转，a的奇偶性不变，相当于完成u和v的配对，此时添加2条边，效果等价于直接给u-v加边（若存在的话）。
     • 要实现添加边数最少，本质是找到奇节点间的最短路径配对方案，把总路径长度压缩到最小。

注意事项 #

• 原图中同一节点间的多条路径不影响策略，只需关注节点度数的奇偶性和配对时的最短路径。
• 每条原边最多添加一条平行边，确保对应边的遍历次数不超过2次。

内容的提问来源于stack exchange，提问作者Vipul Rajan