Algoritmia - Conectividad de vertices a partir del flujo maximo

   
Vista:

Conectividad de vertices a partir del flujo maximo

Publicado por Alejandro (3 intervenciones) el 10/08/2013 00:23:33
Hola,

he encontrado el siguiente algoritmo para calcular la conectividad entre dos vértices de un grafo a partir del flujo máximo del grafo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CONNECTIVITY(G, x, y):
     if (x,y) € E OR (y,x) € E then
          k(x,y)=|V|-1
     else then
          for each vertex v∈V-{x,y} do	             // Replace v with two vertices v_1 and v_2
               create new vertices v_1 and v_2
               create new edge (v_1,v_2)
               for each edge (u,v)∈E do	             // Replace the incoming edges
                    create new edge (u,v_1)
                    delete edge (u,v)
               for each edge (v,u)∈E do	             // Replace the outgoing edges
                    create new edge (v_2,u)
                    delete edge (v,u)
               delete vertex v
          for each edge (u,v)∈E do
               c(u,v)=1
          k(x,y)=maxFlow(G,x,y)



Alguien me podría explicar por que esto es posible? Es decir, por que se puede calcular la conectividad de entre dos vértices a partir del flujo máximo aplicando este algoritmo?

Muchas gracias de antemano! :)
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder