找到所有*顶点*在两个顶点之间的所有简单路径中无向图 [英] Find all *vertices* on all simple paths between two vertices in an undirected graph

问题描述

枚举以任意的曲线图的两个顶点之间的所有简单路径需要指数时间一般，因为可能存在的顶点之间的简单路径的指数数。但怎么样，如果我们只关心在顶点的是在两个端顶点之间至少有一个简单的路径？

Enumerating all simple paths between two vertices in an arbitrary graph takes exponential time in general, because there may be an exponential number of simple paths between the vertices. But what about if we're only interested in the vertices that are on at least one simple path between the two end vertices?

这就是：给定一个无向图和两个不同的顶点，有一个多项式时间的算法，找出每个顶点是在两个顶点之间至少有一个简单的路径这是不是？一样的连接;死角和死胡同囊被排除在外。分支和连接路径，然而，是允许的。

That is: Given an undirected graph and two distinct vertices, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path between the two vertices? This is not the same as connectivity; dead-ends and cul-de-sacs are excluded. Branching and joining paths, however, are permissible.

我发现，这是很容易写一个算法看起来像它解决了这个问题，但无论是失败在某些情况下，还是需要指数的运行时间在病理情况。

I've found that it's very easy to write an algorithm which looks like it solves this problem, but either fails in some case, or takes exponential running time in pathological cases.

更普遍的：给定两个不相交集图形顶点的，是有一个多项式时间的算法发现它躺在一个简单的路径从顶点一组在另一组顶点的所有顶点？

（请原谅我，如果有一个非常明显的解决了这一点。这当然感觉应该有。）

(Forgive me if there's a really obvious solution to this. It certainly feels like there should be.)

推荐答案

下面是一个线性时间的确定性的解决方案。插入你的两个端点顶点之间的边缘（我们姑且称之为A和B），如果这样的优势已经不存在，将您的问题转化为寻找一个最大顶点集信息v趴在任何简单的循环a和b的问题。可以说服自己，这样的一组对应于包含a和b不能通过除去任何它的节点（也称为双连通分量）被断开的最大子图。 本页面介绍Hopcroft和的Tarjan的概念和经典的线性时间（DFS为主）算法来识别所有双连通分支（你只需要一个包含A和B）。

Here is a linear-time deterministic solution. Inserting an edge between your two end vertices (let's call them a and b), if such an edge doesn't already exist, turns your problem into the problem of finding a maximum set of vertices v that lie on any simple cycle through a and b. You can convince yourself that such a set corresponds to the maximal subgraph containing a and b that cannot be disconnected by removal of any of its nodes (also called biconnected component). This page describes the concept and the classic linear-time (DFS-based) algorithm of Hopcroft and Tarjan to identify all biconnected components (you only need the one containing a and b).

您对两套（我们姑且称之为A和B）可以降低对第一个问题通过创建一个新的顶点与边缘A中的所有顶点，之间的简单路径的第二个问题一个顶点b相边的所有顶点B，然后解决您的第一个问题为a和b。

Your second question about simple paths between two sets (let's call them A and B) can reduced to the first question by creating a new vertex a with edges to all vertices in A, and a vertex b with edges to all vertices in B, and then solving your first question for a and b.

这篇关于找到所有*顶点*在两个顶点之间的所有简单路径中无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！