我有一个无向图，所有的顶点都是偶数度。在这个图中，有一组边必须被覆盖一次，并且除非绝对必要，否则不应该覆盖一组边。我需要在图中找到一组一条或多条路径，以便所有必需的边都被精确覆盖一次，并且所走过的不需要的边的数量被最小化。多条路径不需要遍历所需的边，但不需要的边可以使用任意数量的路径遍历。这不是一个欧拉路径，因为有可选的边缘。图边缘遍历算法，需要一些边缘，一些可选
每个单独的路径的长度由所需边缘它可以覆盖的最大数量的限制，尽管路径可以覆盖任何数目的不希望的边缘。
起点和终点不一定相同，但有一组可能的起点。
一些不需要的边缘与所需的边缘重合 - 也就是说，一对顶点可能同时具有需要的边缘和不需要的边缘（尽管每种类型之间永远不会有多于一个边缘给定的一对顶点）。
什么是一个好的算法开始？从根本上说，我正在寻找一种算法，它可以找到一条只需一次就可以遍历所需边的路径，并在可能的情况下避免不需要的边（但可以根据需要多次遍历它们）。我可以在此基础上完成剩下的工作。
您正在寻找原始图中的子图，以便它包含所有需要的边，并且包含最少的不需要的边，以使其包含欧拉路径。
已知一个图包含一个欧拉路径，当且仅当它是CONNECTED并且具有EVEN DEGREE的所有顶点（2除外）。这可以通过执行以下操作来确保：
CASE 1：
如果组分在这个子图的数量为一个（即，所有的边缘彼此连接），我们只需要保证所有顶点（除了2）甚至有学位。由于您的原始图形确实具有均匀度的所有顶点，因此可以做到这一点，但我们也要注意，为了达到这个目的，我们添加的边的数量是最小的（因为只剩下不需要的边添加）。
一个好的启发式方法是从每个奇数顶点开始，然后做一个BFS（宽度优先搜索），直到到达另一个奇数级顶点。对所有奇数顶点执行此操作，选择两个顶点之间的最大非期望路径来实现此目的，并删除此路径。现在，图表将有一个一笔画问题
（有一点需要注意的是，奇顶点这样的配对总是可能的，因为没有图可以有奇数个奇数度的顶点）
情况2：
只包含所需边的子图包含多个组件。要确保连通性，请执行以下操作 - 以具有最少数量顶点的组件获取。从每个顶点执行BFS，并选择将此组件连接到ANY OTHER组件的最小长度路径。
重复此过程，直到所有组件合并为一个组件。现在，即使岬遵循之前介绍的程序CASE 1
谢谢。我在原来的问题中忽略了一点。一些不需要的边缘与所需的边缘重合 - 也就是说，一对顶点可能同时具有需要的边缘和不需要的边缘。我仍然需要一些时间来思考你的答案，但我想知道这是否会影响到任何事情。我把它排除在外的原因是因为我在概括这个问题，但现在我不确定是否将它推广到不正确的地方，或者如果它仍然是同样的问题。 – 2012-03-21 15:43:39
你的意思是说单边既可以既需要又不需要？或者，一对端点之间可以有两条边 - 一个是需要的，另一个是不需要的？如果是第一种情况，那么这并不重要，因为即使边缘不合需要，您必须将其包含在子图中，因为它是必需的。即使是第二种情况，由于您只需要所需的边缘，所以它不会造成任何问题。就实现图形连通性而言，可以忽略不需要的边缘，并且可以包括在试图达到均匀条件时所需的边缘。 – arya 2012-03-22 03:52:07
我认为这是可以还原为旅行商问题。创建一个变换图，其中节点表示强制边，边权重表示必须遍历以从一个强制边到另一个强制边的可选边的数量。
现在的问题是要找到在这个转变图，其经过的所有节点（又名强制边缘）的最短路径。这是TSP，这是NP难。
会有一些并发症，因为你可以采取强制沿之后的路径取决于你把它的方向。您可以通过将每个强制边缘转换为两个节点来解决这个问题，每个方向一个节点。然后，TSP必须访问每对中的一个节点。
例如
A===C
|/
|/ (edges A<->B and B<->C are compulsory, A<=>C is optional)
|/
B
转化图表：
节点= {AB，BA，BC，CB}
边= {AB - > BC（成本为0），BA - > CB（成本1），CB - > BA （成本0），BC - > AB（成本1）}
这是NP难：汉弥尔顿路径问题的一个实例可以转化为你的问题的一个实例。因此，如果你知道如何解决你的问题，你就知道如何解决哈密尔顿路径问题。
要进行转换，请采用有向图并将每个顶点加倍，例如，转换为红色和蓝色顶点。对于每个以前的顶点，使所有入站边到达红色顶点，并且所有出站边离开蓝色顶点。从红色到蓝色的顶点创建一个新的边缘。显然，如果你可以解决这个图的哈密尔顿周期问题，你可以这样做原始图。
现在标注所有新的边界强制性的，所有的旧边界都是可选的。将单个红色顶点标记为可能的入口点。如果您的问题有解决方案，那么它由单一路径组成，这是原始图形的哈密顿路径。
阅读Cormen，Leiserson，Rivest - 介绍算法的详细介绍图算法。 – linello 2012-03-21 08:09:28
感谢您的建议;我在当地一家书店找到了一份。 – 2012-03-21 14:49:22