Conectividad de vertices a partir del flujo maximo
Publicado por anonymous (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:
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! :)
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
0