用最少数量的简单路径覆盖无向图的所有边 [英] Cover all the edges of an undirected graph with fewest number of simple paths

问题描述

给定一个非直接图G，我想用最少的简单路径覆盖所有的边。

例如，对于这样的图表，

  BE 
 | | 
 A  -  C  -  D  -  F  -  G 
  

A - C - D - F - G，B - C - D - F - E 是最佳解决方案，而 A- -C - D - F - G，B - C，E - F 不是。

任何算法？

解决方案

，发现一条路径是否足够是哈密顿路径问题，它是 NP-Hard ，对于这些问题还没有已知的多项式算法。

这会给您带来2个选项：

1. 使用可能未被优化的启发式解决方案。 [示例算法附带]


2. 使用指数解决方案，例如 a>

对于选项1，您可以尝试一个贪婪的解决方案：

<$
选择任意2连接未覆盖的顶点v1，v2
如果没有匹配：
选择一个任意的不是覆盖的顶点
添加从该顶点开始的任意路径
else：
选择从v1到v2的最长的简单路径[可以在BFS / DFS中找到]
添加此路径

对于选项2，一个天真的回溯解决方案将是

  1。找到P = {所有可能的路径} 
 2.创建S = 2 ^ P // P的功率集合b $ b 3.在S中选择s使得对于s中的每个s'：| s | < = | s'|并且s，s'都覆盖了所有的顶点。 
  

注意这个解决方案是 O（2 ^（n！）），所以尽管它是最优的，但并不实际。

Given an undirectd graph G, I want to cover all the edges with fewest simple paths.

For example, for a graph like this,

   B     E
   |     |
A--C--D--F--G

A--C--D--F--G, B--C--D--F--E is an optimum solution, whereas A--C--D--F--G , B--C , E--F is not.

Any algorithms?

解决方案

as said by @RafalDowgird in comments, finding if one path is enough is the Hamiltonian Path Problem, which is NP-Hard, and there is no known polynomial algorithm for these problems.

This leaves you with 2 options:

1. Use heuristical solution, which might not be optimized. [example algorithm attached]
2. use exponential solution, such as backtracking

for option one, you could try a greedy solution:

while (graph is not covered):
   pick arbitrary 2 connected not covered vertices v1,v2
   if there are none matching: 
       choose an arbitrary not covered vertex
       add an arbitrary path starting from this vertex
   else:   
       choose the longest simple path from v1 to v2 [can be found with BFS/DFS]
       add this path

for option two a naive backtracking solution will be

1. find P={all possible paths}
2. create S=2^P //the power set of P
3. chose s in S such that for each s' in S: |s| <= |s'| and both s,s' cover all vertices.

note that this solution is O(2^(n!)), so though it is optimal, it is not practical.

这篇关于用最少数量的简单路径覆盖无向图的所有边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！