寻找“瓶颈边缘”中的图 [英] Finding 'bottleneck edges' in a graph

问题描述

由于随机单一方向图，我必须找到瓶颈边缘来从一个顶点到另一个。

Given a random unidirected graph, I must find 'bottleneck edges' to get from one vertex to another.

我称之为瓶颈边缘（必须有一个更好的名字！） - 假设我有以下单一方向图：

What I call 'bottleneck edges' (there must be a better name for that!) -- suppose I have the following unidirected graph:

    A
  / | \
 B--C--D
 |     |
 E--F--G
  \ | /
    H

要从A至H独立选择的道路边缘处和危险品必须始终穿过，因此使一个瓶颈。

To get from A to H independently of the chosen path edges BE and DG must always be traversed, therefore making a 'bottleneck'.

有一个多项式时间的算法呢？

Is there a polynomial time algorithm for this?

编辑：是的，名字是最小割的话是什么意思魔女瓶颈边缘

edit: yes, the name is 'minimum cut' for what I meant witch 'bottleneck edges'.

推荐答案

听起来像是你需要的最小割，边集删除，这将分离你的图成两部分的最低。

Sounds like you need minimum cut, the minimal set of edges removing which will separate your graph into two pieces.

http://en.wikipedia.org/wiki/Minimum_cut

这篇关于寻找“瓶颈边缘”中的图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！