Нахождение «краев узкого места» на графике - PullRequest
Новая
       28

Нахождение «краев узкого места» на графике

7 голосов
/ 28 апреля 2011

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

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

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

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

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

edit: да, название «минимальное сокращение» для того, что я имел в виду под «краями узкого места».

Ответы [ 2 ]

12 голосов
/ 28 апреля 2011

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

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

4 голосов
/ 28 апреля 2011

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

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

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) набора, являются ребрами узкого места.

...