给定边加权无向图和两个顶点s和t，权重是非负的 . 最短偶数路径问题是找到具有偶数边缘的s，t路径P，其总权重尽可能小 . 如何将最短均匀路径问题减少到最小权重完美匹配问题
从给定的图形开始，想象将节点绘制为蓝色，并将其称为Gblue . 它有节点，包括sblue和tblue，以及无向边缘，如ablue < - > bblue .
制作图表的副本，将其节点绘制为绿色并将其称为Ggreen .
现在重新连接所有边缘，以便ablue < - > bblue和agreen < - > bgreen（具有相同的重量）变为ablue < - > bgreen和agreen < - > bblue（具有相同的重量） .
在这个组合图中，每个边都在蓝色节点和绿色节点之间，因此每个路径在蓝色和绿色之间交替 . 因此，sblue中具有偶数步数的每条路径都将以绿色节点结束 .
现在在这个组合图上，寻找从sblue到tgreen的最小权重路径 .
最后，删除下标 .
1 回答
从给定的图形开始，想象将节点绘制为蓝色，并将其称为Gblue . 它有节点，包括sblue和tblue，以及无向边缘，如ablue < - > bblue .
制作图表的副本，将其节点绘制为绿色并将其称为Ggreen .
现在重新连接所有边缘，以便ablue < - > bblue和agreen < - > bgreen（具有相同的重量）变为ablue < - > bgreen和agreen < - > bblue（具有相同的重量） .
在这个组合图中，每个边都在蓝色节点和绿色节点之间，因此每个路径在蓝色和绿色之间交替 . 因此，sblue中具有偶数步数的每条路径都将以绿色节点结束 .
现在在这个组合图上，寻找从sblue到tgreen的最小权重路径 .
最后，删除下标 .