查找图形中的最小切割边 [英] Finding minimum cut edges in a graph

问题描述

给定一个随机无向图，我必须找到瓶颈边缘（编辑：最小割边）才能从一个顶点到达另一个顶点。

Given a random undirected graph, I must find 'bottleneck edges' (edit: minimum cut edges) to get from one vertex to another.

我所说的瓶颈边缘（编辑：最小切边）-
假设我有以下无向图：

What I call 'bottleneck edges' (edit: minimum cut edges) -- suppose I have the following undirected graph:

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

从A到H不受所选路径边BE和DG的影响必须始终被遍历，因此造成了瓶颈（编辑：最小切割）。

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

是否有多项式时间算法？

Is there a polynomial time algorithm for this?

推荐答案

听起来像您需要最小限度的切割，最小限度的边缘去除，这会将您的图形分成两部分。

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屋！