Encontrar 'bordes de cuello de botella' en un gráfico

Question

Dado un gráfico aleatorio unidireccional, debo encontrar 'bordes de cuello de botella' para pasar de un vértice a otro.

Lo que llamo 'cuello de botella bordes' (! Que debe haber un nombre mejor para eso) - supongamos que tengo el siguiente gráfico unidirected:

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

para ir de A a H de forma independiente de los elegidos los bordes de camino BE y DG siempre deben atravesarse, por lo tanto, forman un "cuello de botella".

¿Hay un algoritmo de tiempo polinomial para esto?

editar: sí, el nombre es 'corte mínimo' para lo que quise decir bruja 'cuello de botella'.

Answer 1

Suena como que necesita un corte mínimo, el conjunto mínimo de bordes eliminando lo que separará su gráfico en dos partes.

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

Answer 2

Lo que se busca es un cut. Dado un gráfico, un corte es un conjunto de bordes que divide los vértices en dos subconjuntos disjuntos.

Suponiendo que está tratando de obtener el corte más pequeño posible, este es el clásico problema min-cut. Aquí hay una versión de pseudo código del algoritmo Ford-fulkerson, reelaborado para su caso (gráficos no ponderados no ponderados). Estoy bastante seguro de que debería funcionar, pero no estoy seguro de ser el más eficiente/idiomático aquí.

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 

---

Por ejemplo, en su caso BFS nos daría la ruta A-B-E-H. Después de eliminar estos bordes, todavía podríamos encontrar la ruta A-D-G-H. Después de eliminar estos bordes, el gráfico se divide en los vértices que se pueden volver a obtener {A, B, C, D} y los ilegibles {E, F, G, H}. Los bordes que tienen un vértice de cada conjunto (B-E y D-G) son los bordes del cuello de botella.