通过有向图的所有顶点是否存在路径? [英] Does a path exist through all vertices of a directed graph?

问题描述

给出有向图G，是否存在一条穿过G中所有顶点的路径(不一定是简单路径)?

我首先需要检查非循环图和强连接图中发生的情况，然后使用强连接组件的图为通用图找到解决方案.

到目前为止，我已经发现，对于一个强连接的图，总会有一条路径.对于非循环图，如果有多个源，则路径将永远不存在.另外，如果存在一个D out大于1的顶点，则路径将永远不存在.

问题是，我不确定最后一个是否正确，如果不正确，则我的算法是错误的.

解决方案

最后一个假设不正确，例如，看一下图G = (V,E)，其中E = {(v_i,v_j) | i < j }显然是DAG.因此找到最大的强连接组件不会改变图形.另外-该图具有哈密顿路径，但是d_out(v_1) > 1 [假设|V| > 3].

但是-您走在正确的轨道上.

高级伪代码算法:

在图中找到最大的强连接组件- 结果图是DAG.
1. 对生成的图 ¹ 使用拓扑排序.
2. 检查排序后的排序是否创建了哈密尔顿路径
3. 如果是-返回true，否则返回false

声明:

当且仅当DAG表示时，存在具有所有顶点的路径 图的MSCC具有哈密顿路径

索赔证明:
<-
如果存在哈密顿路径-那么对于每个MSCC而言，这样的路径都是微不足道的-该路径穿过所有顶点，然后到达表示我们在MSCC的哈密顿路径中选择的边缘的外边缘图形.
->
如果存在这样的路径，则将其设为v0->v1->...vm.
让我们表示V_i v_i所在的最大强连接组件.
现在，对于原始图形v0->v1->...->vm中的路径，MSCC图形 ² 中也存在一个路径:V_0->V_1->...->V_m.
请注意，如果V_i在上述路径中出现两次[或多次]-两次出现是彼此相邻的，否则找到的MSCC不会达到最大值，因为如果V_i->V_k->...->V_i是可行的路径-则V_i和V_k为不是最大的，因为您可以将它们组合成一个更大的SCC.
现在，对于每个V_i，将其所有出现的位置都折叠为一个，您将获得一条路径-每个V_i最多出现一次(我们刚刚说明了原因)，并且恰好出现了一次(因为每个v_i仍在原始路径上，我们并未完全删除MSCC-只是将其收起].
因此-生成的路径是MSCC图中的哈密顿路径.

建议算法的正确性证明:
由于我们显示了且仅当原始图中存在请求的路径时，MSCC图中的哈密顿路径才存在-然后:
->
该算法返回true->该算法在DAG中找到一个汉密尔顿路径->在Dag中有一个汉密尔顿路径[脚注1]->原始图中有一条路径要求.
<-
该算法返回了false->该算法未在DAG中找到汉密尔顿图案-> DAG中没有汉密尔顿路径[脚注1]->原始路径中没有所请求的路径./p>

Q.E.D.

---

1:在DAG​​中，如果存在哈密顿路径，并且存在哈密顿路径，则存在唯一的拓扑排序-这是拓扑排序中顶点的顺序.因此，在DAG中-查找汉密尔顿路径很容易.
2:实际上，这是一个稍微的修改，V_i->V_i并不是MSCC图上的真正优势，但是现在让我们将其表示为一个.

Given G, a directed graph, is there a path (not necessarily a simple path) that goes through all the vertices in G?

I first need to examine what happens in an acyclic graph and in a strongly-connected graph, and then to find a solution for a general graph, using the graph of the strongly connected components.

So far I have figured out that for a strongly connected graph there is always a path. For an acyclic graph, if there is more than one source a path will never exist. Also, if there is a vertex for which D out is greater than 1, a path will never exist.

The problem is, I'm not sure that last one is right, and if it's wrong, my algorithm is wrong.

解决方案

The last assumption is not true, for example have a look at the graph G = (V,E), where E = {(v_i,v_j) | i < j } The graph is obviously a DAG. so finding the maximal strongly connected component won't change the graph. Also - the graph has a hamiltonian path, however d_out(v_1) > 1 [assuming |V| > 3].

However - you are on the right track.

Algorithm in high level pseudo code:

1. find Maximal Strongly Connected Components in the graph - the resulting graph is a DAG.
2. Use topological sort on the resulting graph¹.
3. Check if the ordered sorting creates a hamiltonian path
4. if it is - return true, else return false

Claim:

A path with all vertices exists if and only if the DAG representing the MSCC of the graph has hamiltonian path

Proof of claim:
<-
if there is a hamiltonian path - then such a path is trivial, for each MSCC - the path goes through all vertices, and then to the out edge that is representing the our edge that was chosen in the hamiltonian path in the MSCC graph.
->
If such a path exists, let it be v0->v1->...vm.
Let's denote V_i the maximal strongly connected component in which v_i lays.
Now, for the path in the original graph v0->v1->...->vm, there is also a path in the MSCC graph²: V_0->V_1->...->V_m.
Note that if V_i appears twice [or more] in the above path - the two occurances are adjacent to each other, otherwise the MSCC found is not maximal because if V_i->V_k->...->V_i is feasible path - then V_i and V_k are not maximal, since you can unite them into one bigger SCC.
Now, for each V_i collapse all occurances of it into one, and you get yourself a path - where each V_i appears at most once [we just showed why], and exactly one [since every v_i was on the original path and we did not remove MSCC's completely - just collapsed them].
Thus - the generated path is a hamiltonian path in the MSCC graph.

Proof of correctness of the suggested algrotithm:
Since we showed hamiltonian path in MSCC graph exists if and only if there exists a requested path in the original graph - then:
->
The algorithm returned true -> The algorithm found a Hamiltonian path in the DAG -> There is a Hamiltonian Path in the Dag [foot-note 1] -> There is a path as requested in the original graph.
<-
The algorithm returned false -> The algorithm did not find a Hamiltonian pat in the DAG -> There is no hamiltonian path in the DAG [foot-note 1] -> There is no path as requested in the original path.

Q.E.D.

---

1: in a DAG, there is a unique topological sort if there exists a hamiltonian path, and if there is a hamiltonian path - it is the order of the vertices in the topological sort. Thus, in a DAG - finding a hamiltonian path is easy.
2: Actually, it is a bit modification, V_i->V_i is not really an edge on the MSCC, graph but for now let's denote it as one.

这篇关于通过有向图的所有顶点是否存在路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！