Download Tema 5: Emparejamientos

Fundamentos de la teoría de grafos.
3º I.T.I. de Sistemas
Mª Teresa Cáceres Sansaloni
Tema 5: Emparejamientos
• Preliminares.
• Emparejamientos máximos en grafos bipartitos.
• grafos no ponderados
• grafos ponderados, asignación óptima
• Emparejamientos máximos en grafos en general.
• grafos no ponderados
• grafos ponderados
1
Problema de los matrimonios
Problema de la asignación de tareas
Problema de los horarios
Problema de los matrimonios
Dada una reunión de hombres y mujeres, donde cada mujer
conoce a alguno/s de los hombres ¿bajo qué condiciones
puede cada mujer casarse con un hombre al que conoce
previamente?
Determinar el número máximo de mujeres de la reunión que
puede casarse con algún hombre al que conoce previamente.
Modelización del problema:
problema
Un grafo bipartito G
conjuntos partitos: el conjunto de hombre y el conjunto
de mujeres
aristas: une un vértice que corresponde a un hombre con
otro que representa a una mujer si y sólo si
ambos se conocen previamente.
El problema de los matrimonios puede expresarse en términos
de Teoría de Grafos como:
¿Bajo qué condiciones un grafo bipartito G dado
posee un subgrafo 1-regular que incluya a todos los
vértices de uno de los subconjuntos partitos (el que
representa a las mujeres)?
¿Cuál es el tamaño máximo de un subgrafo 1-regular
de un grafo bipartito?
Problema de la asignación de tareas
Dada una serie de trabajos (tareas) vacantes y otra de candidatos
para uno o más de dichos trabajos ¿bajo qué condiciones existe
una asignación ?
¿Qué asignación de candidatos a tareas permite cubrir el máximo
número de tareas?
Modelización del problema
Un grafo bipartito G
conjuntos partitos: los trabajos vacantes y los candidatos
aristas: un vértice que representa a un candidato es
adyacente a los vértices que representan las tareas
que está capacitado a realizar el candidato
El problema de la asignación de tareas puede expresarse en
términos de Teoría de Grafos como:
¿Bajo qué condiciones un grafo bipartito G dado
posee un subgrafo 1-regular que incluya a todos los
vértices de uno de los subconjuntos partitos, el que
representa a los candidatos (o bien a los trabajos)?
¿Cuál es el tamaño máximo de un subgrafo 1-regular
de un grafo bipartito?
Problema de la asignación óptima
Es otra versión del problema anterior, no se exige cubrir el
máximo número posible de trabajos vacantes sino dar una
asignación tal, que los salarios que pague la compañía produzca el
máximo beneficio.
Modelización del problema
Un grafo G bipartito ponderado. Si el candidato (C) se le
asigna la tarea (T), entonces el peso de la arista CT, w(CT), en G
es una medida del beneficio que la compañía obtendrá
contratando al candidato C para cubrir el puesto T.
El problema de encontrar una asignación de candidatos a
trabajos vacantes que produzca un beneficio máximo a la empresa
es equivalente a encontrar un subgrafo 1-regular H de G tal que la
suma de los pesos de las aristas de H sea máximo.
Definición
Un emparejamiento de un grafo G es cualquier subgrafo
1-regular de G (es decir, un subgrafo inducido por una
colección de aristas dos a dos no incidentes entre sí).
Un emparejamiento máximo de un grafo G es cualquier
emparejamiento de G de orden máximo (con el máximo
número posible de vértices).
emparejamientos (no máximos)
emparejamiento máximo
no es emparejamiento
Definición
Un emparejamiento perfecto de un (p,q)-grafo G es un
emparejamiento de tamaño p/2 (luego p ha de ser par). En el
ejemplo anterior, el emparejamiento máximo es perfecto.
Nota:
Aunque cada grafo que admita un emparejamiento
perfecto ha de ser de orden par (p/2 ha de ser natural),
NO todo grafo de orden par admite un emparejamiento
perfecto (por ejemplo, k1,2n+1 con n≥1)
Definición:
Un emparejamiento de un grafo ponderado G es cualquier
subgrafo 1-regular de G(≡ cualquier conjunto de aristas NO
incidentes dos a dos).
Un emparejamiento de peso máximo de un grafo ponderado G
es un emparejamiento de G tal que la suma de los pesos de sus
aristas sea máximo.
Nota:
Un emparejamiento
de peso máximo en un grafo
ponderado NO tiene por qué corresponder a un emparejamiento
máximo del grafo subyacente.
1
3
2
1
1
emparejamiento
de
peso
máximo
w(H)=4.
No
es
emparejamiento máximo en el
grafo subyacente.
Hay cuatro tipos de Problemas relacionados con
emparejamientos:
1.
Encontrar un emparejamiento máximo en un
grafo bipartito.
2. Encontrar un emparejamiento máximo en un
grafo general.
3. Encontrar un emparejamiento ponderado máximo en
un grafo bipartito ponderado.
4. Encontrar un emparejamiento ponderado máximo en
un grafo ponderado general.
El 4 es mas complejo y requiere tratamientos más
avanzados.
Sea M un emparejamiento de G.
Se llama arista emparejada con respecto a M a cada una de las
aristas de G que pertenecen a M y arista no emparejada con
respecto a M a las que pertenecen a G-M.
Se llama vértice emparejado con respecto a M a cada uno de los
vértices incidentes con aristas de M (vértices de M) y vértice no
emparejado (o soltero) con respecto a M en otro caso.
Se llama camino alternado de G con respecto a M a un camino de
G cuyas aristas son alternativamente emparejadas y no
emparejadas con respecto a M.
Se llama camino aumentante (o creciente) de G con respecto a
M a un camino alternado no trivial cuyos vértices extremos son
ambos solteros.
Nota: Todo camino alternado tiene longitud par y todo camino
aumentante tiene longitud impar.
Resultados técnicos:
Teorema 1:
Sean M1 y M2 dos emparejamientos de un grafo G. Sea
_
A el conjunto de _
aristas que pertenecen a M1 o a M2 pero no a
ambos (es decir, A=(M1-M2) ∪ (M2-M1)).
Sea H_ el subgrafo recubridor de G de conjunto de aristas
E(H)=A. Entonces, cada componente de H es de uno de los
siguientes tipos:
a) un vértice aislado
b) un ciclo cuyas aristas pertenecen, alternativamente,
a M1 y M2.
c) un camino no trivial cuyas aristas pertenecen,
alternativamente, a M1 y M2 y tal que cada vértice
final del camino es un vértice no emparejado con
respecto a M1 o a M2, pero no a ambos.
Demostración:
D(H) § 2 (cada vértice de H incide como mucho con una arista
de M1 y una de M2 )
Cada componente de H es o un camino o un ciclo.
(a) Camino trivial ï vértice aislado
(b) Ciclo (alternan aristas de M1 y de M2) ï Ciclo par
(c) Camino P, componente de H con la arista e=uv con u como
vértice final del camino P.
e œ E(H) Ø (e œ M1 - M2 ó e œ M2 – M1)
Entonces, u es vértice de emparejamiento de M1 y
no de M2 o viceversa, (u es vértice de emparejamiento de M2
pero no de M1)
Teorema 2: (de Berge)
Un emparejamiento M de un grafo G es máximo ⇔ no
existen caminos aumentantes de G con respecto a M.
Demostración:
(fl ) Por R.A.
Sea M un emparejamiento máximo en G y suponemos que G
contiene camino aumentante P. P tiene longitud impar.
M’ = E(P) … M;
M’’ = E(P) – M’
|M’’| = |M’| + 1 fl |(M - M’) » M’’| > |M| (contradicción)
(›) Sea M1 emparejamiento en G. No existe camino aumentante
respecto a M1. Entonces M1 es un emparejamiento máximo.
Sea M2 emparejamiento máximo en G, entonces no existe
camino aumentante con respecto a M2. Sea H subgrafo
recubridor de G con
E(H) = (M1 - M2 ) » (M2 – M1)
H contiene tantas aristas de M1 como de M2 , ya que H contiene
un número par de aristas y por tanto, tantas aristas de M1
como de M2 , veámoslo:
si H1 una componente de H será del tipo del teorema anterior
(a), (b), (c)
Si H1 es del tipo (a), (b) ⇒ E(H1)=par
Si H1 es de tipo (c) no puede ser un camino aumentante
respecto M1 o M2 (a M1 por hipótesis y a M2 porque es
máximo) ⇒ H1 es un camino alternado ⇒ E(H1)=par
Así
| M1| = | M2|
y M1 es máximo.
†
Sea G con U1, U2 Õ V(G) tal que U1 … U2 ∫ «
U1 está emparejado con U2 si existe un emparejamiento M en G tal
que:
cada arista de M es incidente con un vértice de U1 y un
vértice de U2
y cada vértice de U1 o U2 es incidente con una arista de
M.
Sea U un subconjunto no vacío de vértices de G,
N(U) = {v∈V(G) adyacentes con, al menos, un elemento de U}
(vecinos o entorno de U)
Se dice que U es no deficiente si |N(S)|¥|S| "SŒU S∫«
Teorema:
Sea G grafo bipartito, con V(G) = V1 » V2
El conjunto V1 puede estar emparejado con V2 si y sólo si
|N(S)| ¥ |S| "SŒ V1 S ∫ «
Una colección S1, S2,..., Sn, n ¥ 1, de conjuntos finitos no vacíos,
tiene un sistema de representación si existe un conjunto
{s1 , s2 ,..., sn} de elementos distintos con si œ Si , para 1§ i § n
Teorema: Una colección S1, S2,..., Sn, n ¥ 1, de conjuntos finitos no
vacíos, tiene un sistema de representación si y sólo si para cada k
(1§ k § n) la unión de cualesquiera k de estos conjuntos contiene
al menos k elementos.
Para el problema de los matrimonios: Una condición necesaria y suficiente
que garantiza que cada mujer puede casarse con un hombre al que conoce
previamente, es que cualquier subconjunto de k mujeres (1§ k § n)
colectivamente conozcan al menos a k hombres.
Emparejamiento máximo en un grafo bipartito.
Sea M un emparejamiento en G y P un camino aumentante
respecto a M
M’ = E(P) … M;
M’’ = E(P) – M’;
M1 = (M - M’) » M’’
M1 es un emparejamiento para G con |M1| = |M| + 1
M1 se obtiene aumentando M a lo largo de P
G
G
v1
v8
v1
v8
Emparejamiento máximo en un grafo bipartito.
Teorema:
Sea M un emparejamiento de G que no es máximo, v vértice suelto
respecto a M. M1 emparejamiento obtenido aumentando M por un
camino aumentante. Si G contiene un camino aumentante respecto a
M1 con v como vértice final, entonces G contiene un camino
aumentante con respecto a M que tiene v como vértice final.
Corolario:
Sea M un emparejamiento de G. Supongamos que M1, M2,..., Mk es una
secuencia de emparejamientos de G de modo que Mi (2§i§k) es
obtenido de Mi-1por un camino aumentante. Sea v un vértice suelto
respecto de M para el cual no existe un camino aumentante con v
como vértice final. Entonces G no contiene un camino aumentante
con respecto a Mi (2§i§k) que tiene v como vértice final.
Algoritmo 1
[Encuentra un emparejamiento máximo en un (p, q)-grafo bipartito con V (G) = {v1, v2, . . . , vp}
y con emparejamiento inicial M1]
P1.− i ô 1, Mô M1
P2.− Si i < p, entonces continua
Si no, STOP (ya que hemos encontrado un
emparejamiento máximo M)
P3.− Si vi está emparejado entonces iô i + 1 y ve al P2.
Si no vôvi y la cola Q se inicializa sólo con v, (Q ô {v})
P4.−
[Construye el árbol alternado enraizado en v]
P4.1.− Para j = 1, 2, . . . , p y j ≠ i, ARBOL(vj) ô F
Además, ARBOL(vi) ô V
P4.2.− Si Q =«; entonces iô i + 1 y ve al P2.
Si no, borra un vértice x de Q y continua (QôQ−{x})
P4.3.− [Determina si hay camino aumentante o extiende el árbol]
P4.3.1− Supóngase que N(x) = {y1, y2, . . . , yk}. j ô 1
P4.3.2− Si j ≤ k, entonces yô yj
Si no, ve al paso P4.2.
P4.3.3− Si ARBOL(y) = V , entonces jôj+1 y ve a P4.3.2
Si no, continua.
P4.3.4− Si y es incidente con una arista emparejada yz,
entonces ARBOL(y)ô V , ARBOL(z)ô V ,
PADRE(y)ô x, PADRE(z) ô y, QôQ + {z},
j ô j + 1 y ve al paso P4.3.2.
Si no, y es vértice no emparejado y continua.
P4.3.5− Usamos la lista PADRE para encontrar el camino
alternado P’≡ v − x en el árbol alternado. Sea P el
camino aumentante obtenido añadiendo {x, y} a P’.
P5− Aumenta M a lo largo de P para obtener un nuevo
emparejamiento M’. Sea M ← M’, i ← i + 1 y ve al P2.
Complejidad: O(pq)
Cada vez que construimos un árbol alternado, los vértices
adyacentes a cada vértice borrado de la cola Q han sido
examinados a lo sumo una vez.
Dado que ∑δ(u)=2q ⇒ para cada árbol alternado se realizan
O(q) pasos en P4.
Cada camino aumentante tiene a lo sumo p-1 aristas, así que P5
tiene complejidad O(p). Como p-1≤q, se tiene que P5 tiene
complejidad O(q).
Ya que cada vértice se elige a lo sumo una vez como raíz de un árbol
alternado, sigue que la complejidad del algoritmo completo es
O(pq).
Problema de asignación óptimo
Encontrar un emparejamiento de peso máximo en un grafo
bipartito ponderado.
G grafo bipartito ponderado con V(G) = V1» V2
Sea G’ grafo bipartito completo ponderado. G subgrafo de G’
V(G’) = U1» U2 con |U1| = |U2| = max{|V1|, |V2| } y Vi Œ Ui i=1,2
Si x œ U1; y œ U2
ï wG’(xy) = wG(xy) si xy œ E(G)
wG’(xy) = 0 en otro caso
Si M es un emparejamiento ponderado máximo de G’, entonces:
1.- M es un emparejamiento perfecto de G’
(puede haber aristas de M con peso 0)
2.- M … E(G) emparejamiento ponderado máximo de G.
Es suficiente un algoritmo para encontrar un emparejamiento
perfecto de peso máximo en grafos bipartitos completos
ponderados.
Sea G grafo bipartito completo ponderado,
ponderado con
V1 = {v1, v2, ... , vp} y V2 = {u1, u2, ... , up}
Etiquetado de vértices viable,
viable es una función { real del conjunto
de vértices tal que "v œ V1, " u œ V2 {(v) + {(u) ¥ w(vu)
Un etiquetado de vértices viable de G es:
{(v) = max{ w(vu): u œ V2 } " v œ V1
{(u) = 0
" u œ V2
Se define:
E{ ={vu œ E(G): vœV1, uœV2, {(v) + {(u) = w(vu)}
H{ subgrafo recubridor de G con conjunto de aristas E{
Teorema:
Teorema
Sea { un etiquetado de vértices viable de un grafo G bipartito
completo ponderado. Si H{ contiene un emparejamiento perfecto
M’, entonces M’ es un emparejamiento ponderado máximo de G.
Algoritmo 2 (Kuhn-Munkres)
[Algoritmo de emparejamiento ponderado máximo para grafos bipartitos
completos ponderados. Sea G un grafo bipartito ponderado completo]
P1.- [Inicializa un etiquetado viable]
P1.1- Para cada v∈V1, l(v)←max {w(vu): u∈V2} .
P1.2- Para cada u∈V2, l(u)←0.
P1.3- Sea Hl el subgrafo recubridor de G con
conjunto de aristas El.
P1.4- Sea Gl el grafo subyacente de Hl.
P2. - Se aplica el algoritmo 1 para grafos bipartitos no
ponderados para encontrar un emparejamiento
máximo M en Gl.
P3.– [Determina si se ha encontrado un emparejamiento ponderado máximo]
P3.1- Si cada vértice de V1 está emparejado con
respecto a M, entonces retorna M y STOP.
Si no, continua.
P3.2- Sea x el primer vértice no emparejado de V1.
P3.3- Se construye un árbol alternado con respecto a M
que está enraizado en x. Si se encuentra un camino
aumentante P, entonces aumentamos M a lo largo
de P y ve al paso P3.1.
Si no, sea T el árbol alternado con respecto a M y
enraizado en x que no puede ser extendido más en Gl.
P4.- Calcular ml←min{l(v)+l(u)-w(vu): v∈V1∩V(T) y u∈V2-V(T)}
Sea
l(v)-ml si v∈V1∩V(T)
l’(v)← l(v)+ml si u∈V2∩V(T)
l(v) en otro caso
P5.- Sean l←l’, construye Gl y ve a P3.3.
Complejidad del algoritmo:
algoritmo O(p4)
Cada vértice de G tiene grado p ⇒
complejidad O(p2).
el paso P1 tiene
En P2, se construye p veces un árbol alternado ⇒ la
complejidad es O(p3).
P3.1 y P3.2 tienen complejidad O(p) si mantenemos la
posición del último vértice no emparejado considerado .
Cada vez que se construye un árbol alternado en P3.3, se
realizan O(p2) operaciones.
Para cada vértice no emparejado x seleccionado en
P3.2, el paso P3.3 se realiza O(p) veces,
Así, P3.3 tiene complejidad O(p4).
P3.3 tiene complejidad O(p4).
Cada vez que volvemos a P3.3 después de la primera,
construimos un árbol alternado (O(p2)) enraizado en x
y, además una de dos:
- o encontramos un camino aumentante
- o se añaden dos vértices al árbol alternado
enraizado en x que teníamos previamente.
Puesto que un árbol alternado enraizado en x que no
contenga ningún camino aumentante tiene, como
máximo, 2p-1 vértices, volvemos al paso P3.3 como
mucho p-1 veces.
El mismo argumento prueba que P4 se realiza O(p2)
veces. Cada vez que se ejecuta P4 se realizan O(p2)
operaciones.
Puesto que P5 se realiza cada vez que se completa P4 y
que la construcción de Gl tiene complejidad O(p2), la
complejidad de P5 es O(p4).
Así, la
complejidad del algoritmo es O(p4)
Emparejamientos máximos en grafos generales
a
a
b
b
c
h
Alg. 1
g
f
d
e
c
g
f
d
e
El algoritmo 1 se pararía y nunca encontraríamos el camino
aumentante P: abcdefgh
El algoritmo 1 no permite la existencia de caminos alternados con
longitudes par unos e impar otros. Por ej., P’: abcg P’’:abcdefg son
ambos caminos a-g alternados de longitud 3 (impar) P’ y 6 (par) P’’.
La contribución más importante del algoritmo se debe a
Edmonds en 1965. Desarrolló el método llamado “la flor
menguante”.
Actualmente
se
han
descrito
diversas
modificaciones a dicho procedimiento. Nuestra descripción sigue
fielmente el trabajo de Pape y Conradt de 1980.
Sea G grafo general con v vértice sin emparejar (soltero)
respecto del emparejamiento M.
Construimos un árbol alternado enraizado en v. (Todos los
caminos desde v son alternados respecto a M en G)
Si u es un vértice soltero adyacente a v, añadir (vu) a M
En otro caso, todos los vértices adyacentes a v están
emparejados.
v en Nivel 0
u1, u2, … , uk vértices adyacentes a v en Nivel 1
Sean uivi œ M para 1§ i § k.
vi en Nivel 2
(Es posible vi = uj, entonces uiuj œ M y
Supongamos que estamos en el Nivel m
vj = ui)
(m par)
Para cada vértice x en el nivel m examinamos los vértices y
adyacentes con x en G.
Si xy ΠM o y = v no hacer nada.
Si xy œ M, y π v,
Si y es no emparejado (soltero) entonces el camino
alternado v-x seguido de xy es un camino aumentante
respecto a M.
Si y está emparejado yz œ M hay tres casos:
1.- y pertenece a algún nivel impar del árbol
alternado
( no extender el árbol yz ya está explorado)
2.- y pertenece a algún nivel par del árbol alternado
(determinar si y es antecesor de x, si lo es no hacer
nada y si no lo es, entonces añadir xy, yz, y en
el nivel m + 1, z en el nivel m + 2
3.- y no pertenece al árbol alternado, entonces añadir
xy, yz, y en el nivel m + 1, z en el nivel m + 2.
La construcción del árbol alternante termina por:
9se encuentra un camino aumentante
9después de un nivel m par, no se puede añadir niveles
según las reglas anteriores.
Ejemplo.
c
d
a
a no emparejado respecto a M.
Construimos un árbol alternado
enraizado en a. Al finalizar se verá
que existe un camino aumentante a-z.
b
u
z
y
x
v
w
En el nivel 0 se sitúa a. En el nivel 1 sus
adyacentes, b,c,d y se unen con a. Como los tres
están emparejados, se llevan sus parejas al nivel
2 y se unen con los vértices del nivel 1. b
Obsérvese que los vértices c y d están
emparejados entre sí, así que aparecen en los
niveles 1 y 2.
Como c y d no tienen más adyacentes
pero el vértice u es adyacente a y, v, w y
(además de b que es antecesor), se añaden y,
v, w al nivel 3 del árbol y sus parejas x, w, v
al nivel 4, incluyendo las aristas de M que los x
unen. De nuevo se repiten vértices de los
niveles 3 y 4 (luego aristas)
Como los adyacentes a x son y, w y ambos están
en un nivel impar, no se hace nada. Lo mismo
ocurre con v. Adyacentes a w son x y v, wx∉M y x
está emparejado, xy∈M, x está en nivel par, x no
antecesor de w, añadir wx, xy, x en el nivel 5 e y
en el nivel 6. Con v, wv ∈M, no se hace nada.
a
c
d nivel 1
d
u
nivel 0
c nivel 2
w v
nivel 3
v w
nivel 4
x
nivel 5
y
nivel 6
z
nivel 7
Sea ahora el vértice y del nivel 6, y es adyacente a u, x, z, tanto u como x
son antecesores suyos, sólo resta el vértice z, yz ∉M y z no emparejado,
hemos encontrado el camino aumentante.
M el emparejamiento
Q cola cuyos vértices pertenecen a un nivel par, y sus aristas
incidentes aun no han sido estudiadas.
Listas de tamaño p:
PAREJA describe el emparejamiento actual.
PAREJA(vi)=vj si (vivj) œ M ;
PAREJA(vi)=0 si vi es SOLTERO
NIVEL con valor lógico verdadero T o falso F
NIVEL(w) = F si w es la raíz o está en nivel impar
NIVEL(w) = T en otro caso
Inicialmente, NIVEL (v) =F si v raíz ,
NIVEL (w) = T " w œ V(G) w ∫ v
ABUELO para determinar si un vértice es antecesor
ABUELO(w) = u si w es de nivel par y existe un camino
uvw en el árbol tal que vw œ M.
Variable SOLTERO , número de vértices sin emparejar.
Inicialmente SOLTERO = p - 2|M|
Modo de actuar para extender el árbol alternado:
Eliminar x de Q
Considerar todas las aristas incidentes xy con
NIVEL(y) = T
Si y no emparejado, añadir.
Si y emparejado,
si es antecesor de x ABUELO(x) =y, seguir
si no es antecesor: sea PAREJA(y)=z,
añadir y, z, aristas xy, yz al árbol,
añadir z a Q,
ABUELO(z) =x, NIVEL(y)=F
Algoritmo 3 (Emparejamiento máximo en un (p,q) grafo G)
[Sea un (p,q) grafo G, con V(G)={v1, v2, ... , vp}, dado un emparejamiento M (puede ser «)
definido por el vector PAREJA(vi)=vj si (vivj) œ M; PAREJA(vi)=0 si vi es SOLTERO]
P1.- SOLTERO ≠ p - 2 |M| ,
i≠1
P2.- Si SOLTERO < 2, parar, M emparejamiento máximo. Fin
En otro caso, continuar.
P3.- Si i < p entonces continuar;
Si no, retorna M emparejamiento máximo. Fin.
P4.- Si PAREJA( vi) ∫ 0, entonces i≠ i + 1, ir a P3;
En otro caso, vi raíz del árbol alternado, continuar.
P5.- [Inicializar NIVEL y Q para la nueva raíz vi]
NIVEL(vj) ≠ T para 1§ j § p , j ∫ i
NIVEL(vi) ≠ F, Q ≠ {vi}
[P6-P9 construye un árbol alternante con raíz vi. Si se encuentra camino alternante se
mejora el emparejamiento]
P6.- Si Q = «, i ≠ i + 1 , volver P3;
en otro caso, Q ≠ Q – {x}
P7.- [Determina si se expande el árbol alternado en x]
7.1.- Sea N(x) = {w1, w2, ... , wk}, j ≠ 1
7.2.- Si j > k, volver P6; en otro caso, y ≠ wj
7.3.- Si NIVEL(y) = F, j ≠ j + 1, volver P7.2;
en otro caso NIVEL(y) = T continuar.
7.4.- Si PAREJA(y) = 0 ir a P8; en otro caso, ir a P9.
P8.- [Mejora del emparejamiento
y actualización de PAREJA]
8.1.- PAREJA(y) ≠ x
8.2.- SIGUIENTE ≠ PAREJA(x)
8.3.- PAREJA(x) ≠ y
8.4.- Si SIGUIENTE = 0, ir P8.7; si no, continuar
8.5.- x ≠ ABUELO(x) , PAREJA( SIGUIENTE) ≠ x
8.6.- y ≠ SIGUIENTE volver P8.2
8.7.- SOLTERO ≠ SOLTERO -2, i ≠ i + 1 , ir P2
P9.- [Determinar si y es antecesor de x, para extender o no el árbol alternado.]
9.1.- Si x = vi, ir P9.5; si no continuar.
9.2.- u ≠ ABUELO(x)
9.3.- Si u = y, j ≠ j + 1 , volver P7.2; si no continuar
9.4.- Si u ∫ vi, u ≠ ABUELO(u) ir P9.3;
En otro caso continuar, y no es antecesor de x
9.5.- NIVEL(y) ≠ F, Q ≠ Q » {PAREJA(y)}
9.6.- ABUELO(PAREJA(y)) ≠ x
9.7.- j ≠ j + 1 , volver P7.2
Ejemplo:
1
4
2
3
10
5
6
PAREJA:
7
2
3
4
5
6
7
8
9
10 11
3 5 1 0 2 8 9 6 7 0 0
11
8
1
9
SOLTERO=3
Primer vértice no emparejado, 4.
Construimos el árbol alternado.
(a)
1
4
NIVEL
2
Q
1
4
5
6
7
8
9
10 11
T F T F T T T T T T T
4
4 5
4
2
3
3
ABUELO
5
(b)
2
5
1
NIVEL
2
3
4
5
6
7
8
9
T F F F T F F T T T T
ABUELO
6
7
8
9
5
Q
10 11
4
4 5 1 8 9
5 5
(c)
4
2
1
NIVEL
2
3
4
5
6
7
8
9
T F F F T F F F F T T
5
3
1
9
7
6
7
8
9
ABUELO
5
4 9 8 5 5
8
6
Q
10 11
4 5 1 8 9 7 6
(d)
4
1
2
NIVEL
2
3
4
5
6
7
8
9
10 11
T F F F F F F F F F T
5
3
1
6
7
8
9
ABUELO
5 7
4 9 8 5 5
8
9
Q=«
7
6
10
El vértice 5 es adyacente a 7, no
se añade pues 5 es antecesor de 7.
11
1
PAREJA:
SOLTERO=1
2
3
4
5
6
7
8
9
10 11
3 4 1 2 7 10 5 9 8 6 0
Complejidad: O(p2q)
La complejidad total de los pasos 2, 3, 4 es O(p).
Realizamos el paso 5 cuando un vértice es considerado la
raíz de un árbol alternado. Como el paso 5 sólo actualiza las p
entradas de la lista NIVEL y actualiza la cola Q, requiere
complejidad O(p). Como cada vértice de G es a lo más una vez raíz
de un árbol alternado, el paso 5 requiere O(p2).
Pasos 6-9. Cuando un vértice v es seleccionado para ser raíz
de un árbol alternado, cada vértice de G aparece a lo más una vez
en la cola para el árbol alternado. Supongamos que z se añade a la
cola durante la construcción del árbol. El vértice v es soltero
respecto de M. Puesto que v aparece sólo una vez en Q (como
primer elemento), podemos suponer z≠v. Entonces, existe un vértice
x de G tal que el camino x,y,z pertenece al árbol alternado. Además,
esta aparición de z en el árbol alternado es en un nivel par, pues y
aparece en un nivel impar del árbol a lo más una vez, de donde sigue
que z aparece a lo más una vez en la cola Q.
Para cada vértice x que es borrado de la cola en el paso 6,
cada vértice y adyacente a x es examinado a lo más una vez en el
paso 7. Chequeamos los valores de NIVEL(y) para como mucho δ(x)
vértices y adyacentes a x.
Si NIVEL(y)=T entonces se chequea el paso 7.4 y es
realizado exactamente uno de los pasos 8 ó 9. El paso 8 cambia las
aristas de un camino aumentante y aumenta el emparejamiento
inicial. Como cada camino de G contiene a lo más p-1 aristas, el paso
8 tiene complejidad O(p). El paso 9 también tiene complejidad
O(p), la mayor parte del tiempo consumido es para determinar si y
aparece en el camino v-x del árbol alternado. Así, el número de
veces que se realiza el paso 8 o el 9 para cada raíz de un árbol
alternado es a lo más ∑δ(x)=2q.
Así, el tiempo estimado en los pasos 7-9 para una raíz
fijada de un árbol alternado es O(pq). Como cada vértice es a lo
más una vez raíz, la complejidad del algoritmo es O(p2q).