Блог

Учитывая случайный неориентированный граф, я должен найти «ребра узкого места» (редактировать: минимальные обрезанные ребра), чтобы перейти от одной вершины к другой.

То, что я называю «ребрами узкого места» (редактировать: минимальные обрезанные ребра) — предположим, у меня есть следующий неориентированный граф:

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

Чтобы добраться от A до H независимо от выбранного пути, ребра BE и DG всегда должны быть пройдены, что создает «узкое место» (редактировать: минимальный разрез).

Существует ли для этого алгоритм полиномиального времени?

Похоже, вам нужен минимальный разрез, минимальный набор ребер, удаление которых разделит ваш график на две части.

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

То, что вы ищете, — это разрез. Для данного графа разрез представляет собой набор ребер, который разбивает вершины на два непересекающихся подмножества.

Предполагая, что вы пытаетесь получить наименьший возможный разрез, это классическая проблема с минимальным разрез. Вот псевдокодовая версия алгоритма Форда-фулкерсона, переработанная для вашего случая (неориентированные, невзвешенные графики). Я почти уверен, что это должно сработать, но я не уверен, что я здесь самый эффективный / идиоматичный.

 reorganize your graph into a directed graph,
  with two directed edges (u->v, v->u) for each original edge (u-v)

while there is a path P from A to H:
  (hint: use breadth first search to find paths - long story here)
  //augment the path P:
  for each edge (u->v) in P:
    remove (u->v) from the graph and add (v->u) to it
    (if v->u isn't there already)

Label all vertices as reacheable or not reacheable from A.

The bottleneck edges is the set of edges
  that connect a reacheable and a unreacheable vertex
  

Например, в вашем случае BFS выдала бы нам путь A-B-E-H. После удаления этих ребер мы все равно смогли бы найти путь A-D-G-H. После удаления этих ребер граф разбивается на достижимые вершины {A, B, C, D} и недостижимые {E,F, G, H}. Ребра, которые имеют вершину из каждого набора (B-E и D-G), являются ребрами с узким местом.