Organización de la clase
•
•
•
•
•
•
•
Enfoque
Introducción
Conceptos previos
Algoritmo 5.2 (versión simple)
Cleaner & Pirámides
Clean Shortest Odd Hole Detector (4.2)
Algoritmo 5.2 (versión rápida)
Enfoque
•
•
•
•
Como empezamos a leer
Como terminamos leyendo
Pregunten, pregunten y pregunten.
Entendamos primero las ideas, después
las demostraciones
Introducción
•
•
•
•
Berge Graph, definición
Berge Perfecto (conjetura fuerte)
Diferencias con el algoritmo anterior
Este algoritmo resuelve la búsqueda
general de odd-holes ?
Conceptos Previos
•
•
•
•
•
Joyas (Jewels)
Pirámides
Major
Clean
Cleaner
Joyas 1 (Jewels)
Ejes
No Ejes
v1
v2
v3
P
v4
v5
Joyas 2 (Jewels)
• Si hay una joya en un grafo  hay un O-H
• Dem:
– Si |P| es par v1-P-v4-v3-v2-v1 es un O-H
– Si |P| es impar  v1-P-v4-v5-v1 es un O-H
• Algoritmo:
– Enumerar todos los conj. de 5 vértices O(n5)
– Verificar si cumplen las condiciones O(n2) /
O(n)
Pirámides 1
|P1|  1
|P2| > 1
|P3| > 1
Pirámides 2
• Si hay una pirámide en un grafo  hay un
O-H
• Dem:
– Dos caminos Pa y Pb tienen la misma paridad
en su long.  la suma de estas es par  si le
sumamos un lado del triángulo y como no hay
cuerdas entre Pa y Pb tenemos un O-H
• Algoritmo:
– Existe un algoritmo que en O(n9) detecta si
hay o no una pirámide.
Major
Major
• Un major es un
vértice de G tal que
su conjunto de
vecinos en C no está
en un camino de 2
ejes de C.
C
Clean
• Un O-H es clean si no tiene ningún major.
Opcional
C1
C2
C3
Cleaner 1
• Si C es un O-H en G, un subconjunto
X V(G) es un cleaner para C si X
contiene a todos los vértices que son
major para C y X V(C) es un
subconjunto de un camino de 2 ejes de C
Cleaner 2
m1
|P| > 2
mi
C
Cleaner 3
m1
|P| > 2
mi
C
NO Cleaner 4
• Este conj. de
vértices no es
un cleaner
pues su
intersección
con C no es
un subconj.
de un camino
de 2 ejes
m1
|P| > 2
mi
C
Algoritmo 5.2 (versión simple) 1
• Orden O(|V(G)|12)
• Pasos
– Si G tiene pirámides
• Devolver FALSE (2.2 – O(n9))
– Si G tiene joyas
• Devolver FALSE (3.1 – O(n6))
– Corremos 5.1 y obtenemos o bien que G no es Berge o O(n5)
subconjuntos tal que si C es un SOH en G y todo major de C
tiene por lo menos 4 vecinos  uno de los subconjuntos es
cleaner para C (O(n6), próxima clase)
– Para cada subconjunto X obtenido en el paso anterior
• Enumero todos los subconjuntos Y, tales que |V(Y)| ≤ 3 (son O(n3))
• Para cada grafo G \ (X \ Y) aplicar 4.2 O(n4)
– Si G no tiene O-H se verifica el complemento y si este tampoco
tiene un O-H  G es Berge
Algoritmo 5.2 (versión simple) 2
• Tenemos n5 subconjuntos tal que si G
tenía un S-O-H C  uno de los
subconjuntos, X, es un cleaner para C 
por ser cleaner, X tiene todos los majors
de C y a lo sumo 3 nodos de C  a X le
saco los nodos de C y los nodos que
quedan los saco de G  me queda en G,
C como S-O-H y clean (pues saque todos
sus majors)  puedo aplicar el C-S-O-H
detector (algoritmo 4.2)
Cleaner & Pirámides 1
• Teorema: "m Major de C, C-S-O-H en G
sin pirámides, m tiene al menos 4 vecinos
en C
• Dem:
– Supongo que m tiene 0 o 1 vecino en C  m
no es Major ABS !!
Cleaner & Pirámides 2
m
– Supongo que m tiene
2 vecinos (separados
por un camino de más
de 2 ejes)  P1 o P2
es un camino de long.
impar  3  Pa y el
major forman un O-H
menor a C ABS !!
P1
P2
Cleaner & Pirámides 3
m
– Supongo que m
tiene 3 vecinos en
C
• i) Si 2 vecinos son
consecutivos  se
forma una pirámide
ABS !!
Cleaner & Pirámides 4
– Supongo que m
tiene 3 vecinos en
C
• ii) Sean P1, P2 y P3
los subcaminos
formados por los 3
vecinos, Pa tiene
long. impar  Pa y
el major forman un
O-H menor a C
ABS !!
m
>1
P1
>1
P2
P3
>1
Algoritmo 4.2 1
Clean Shortest Odd Hole Detector
• Orden O(|V(G)|4)
• Pasos
– Para cada u, v  V(G)
• Calcular P(u,v), camino mínimo entre u y v
– Para cada terna u, v, w  V(G)
• Ver si  P(u,v), P(v,w), P(w,u)
– Si forman un O-H
» Devolver TRUE
– Si no
» Devolver FALSE
Algoritmo 4.2 2
Clean Shortest Odd Hole Detector
• Complejidad del algoritmo 4.2
– Cálculo de todos los caminos mínimos: O(n3)
– Hay O(n3) ternas de vértices, para cada una
calculo si los caminos mínimos entre sus
vértices forman un odd hole
– O(n3) * O(n) = O(n4)
Algoritmo 5.2 (versión rápida) 1
• Orden O(|V(G)|9)
• Pasos
– Si G tiene pirámides
• Devolver FALSE (2.2 – O(n9))
– Si G tiene joyas
• Devolver FALSE (3.1 – O(n6))
– Corremos 5.1 y obtenemos o bien que G no es Berge
o O(n5) subconjuntos tal que si C es un SOH en G y
todo major de C tiene por lo menos 4 vecinos  uno
de los subconjuntos es cleaner para C O(n6)
Algoritmo 5.2 (versión rápida) 2
– Para cada X obtenido en el punto anterior
• Para cada x, y  V(G) encuentro P(x,y), el camino más corto
sin vértices internos en X. Si , sea r(x,y) su longitud.
• Para cada y1  V(G)\X y para cada camino x1-x3-x2 de G\y1
chequear los siguiente:
– r (x1, y1), r (x2, y1) existen
– r (x2, y1) = r (x1, y1) + 1 = r (x1, y2) = k
– r (x3, y1), r (x3, y2) ≥ k
• Donde y2 es el vecino de y1 en P (x2,y1)
• Si encontramos x1,x2,x3,y  Hay un OH
– Si procedemos igual con el complemento de G y no
encontramos un OH  el grafo es Berge
Descargar

Joyas (Jewels)