Embed Size (px)
Citation preview
Teoría de Grafos.-Clase 2
Conexión y árboles
Aplicación 1: Problemas de ordenación.(Estructura de una compañía)
Director
Coordinador 1
Trabajador 5
Coordinador 2
Trabajador 3Trabajador 2Trabajador 1 Trabajador 4
Aplicación 2.Problemas de búsqueda(Recorrer todas las habitaciones de un laberinto)
Aplicación 3: problemas de conectividad mínima.(Reconstrucción de carreteras tras un terremoto)
Aplicación 3b: problemas de conectividad mínima.(Reconstrucción de carreteras tras un terremoto con varios costes)
37
3
84
8
2
5
2
2
Definiciones:
w
x y
vu
e2
e1
e3
e4
e6
e5e7
Definición: Una cadena (walk) de un vértice u a un vértice y es una sucesión alternante de vértices y aristas, los cuales pueden estar repetidos.
u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y
En general escribiremos u, v, w, x, u, v, y
Definiciones:
w
x y
vu
e2
e1
e3
e4
e6
e5e7
Definición: Una camino (path) de un vértice u a un vértice y es una cadena de u a y sin vértices repetidos.
u, e4, x, e6, w, e3, v, e5, y
u, x, w, v, y
w
x y
vu
e3
e4
e6
e5
Definiciones:
w
x y
vu
e2
e1
e3
e4
e6
e5e7
Definición: Una ciclo (cycle) es un camino que empieza y acaba en el mismo vértice.
u, e1, v, e5, y, e7, w, e2, u
u, v, y, w, u
w
y
vu
e2
e1
e5e7
Definiciones:
w
x y
vu
e2
e1
e3
e4
e6
e5e7
Definición: Una recorrido (trail) es una cadena sin aristas repetidas (se pueden repetir vértices). Observar que es una condición mas débil que un camino.
x, e6, w, e3, v, e1, u, e2, w, e7, y
x, w, v, u, w, y
w
x y
vu
e2
e1
e3
e6 e7
Definiciones:
w
x y
vu
e2
e1
e3
e4
e6
e5e7
Definición: Una circuito (circuito) es un recorrido con el mismo origen y final.Observar que un circuito es condición mas débil que un ciclo.
x, e6, w, e3, v, e5, y, e7, w, e2, u, e4, x
x, w, v, y, w, u, x
w
x y
vu
e2 e3
e4
e6 e7
e5
Teorema: Toda cadena u-v contiene un camino u-v
Sea u=u0, u1, u2, … , un=v una cadena de longitud n. Suponemos que u es diferente de v.
Si todos los vértice son diferentes entonces es un camino
Si hay dos vértices iguales digamos ui y uj son iguales con i diferente a j, entonces
u=u0, u1, u2, …, ui, ui+1, … uj-1, uj, uj+1, … , un=v
Eliminando los vértices desde ui hasta uj-1 tendríamos una cadena dondeestos dos vértices no están repetidos. Repitiendo el proceso hasta que no hayavértices repetidos nos daría un camino de u a v.
u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y
u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, yw
x y
vu
e2
e1
e3
e4
e6
e5e7
Definición: Un vértice u se dice que esta conectado al vértice v si existe una cadena (camino) de u a v. Un grafo se dice conexo o conectado si u esta conectado a v para todas posibles parejas de vértices u y v. Un grafo que no es conexo se dice disconexo.
Un subgrafo H de un grafo G se dice una componente de G si H es un subgrafo maximal conexo de G.
Grafo conexo Grafo disconexo con 4 componentes
Definición: Un vértice v en un grafo G se denomina vértice de corte si K(G-v) ≥ K(G)
v1
v6
v3
v4 v5
v2 v1
v6
v4 v5
v2
v1
v6
v3
v4
v2
K(G-v3)=2V3 es un vértice de corte
v1
v6
v3
v4 v5
K(G-v2)=1V2 NO es un vértice de corte
K(G-v5)=2V5 es un vértice de corte
Grafo conexo GK(G)=1
Definición: Una arista e de un grafo G se denomina puente si K(G-e) ≥ K(G)
v1
v6
v3
v4 v5
v2
Grafo conexo GK(G)=1
v1
v6
v3
v4 v5
v2
v1
v6
v3
v4 v5
v2
v5v4 es puenteK(G –v5v4)=2
v1v2 NO es puenteK(G –v1v2)=1
Teorema: Una arista e de un grafo conexo G es un puente de G si y solo si e no esta en un ciclo de G.
Sea G un grafo conexo, si e es un puente entonces no esta en un ciclo
Como G es conexo existe un camino de a1 a a2 en G. -Si el camino no contiene a uv también estarán conectados en G-e-Si el camino contiene a e=uv solo hay que cambiar e=uv por u, x, …, w, v. Por tanto G-e es conexo lo cual es una contradicción ya que G-e debería ser disconexo puesto que e=uv es un puente.
Si e no esta en un ciclo de G entonces es un puente.
Si e=uv no esta en un ciclo entonces G-e no contiene un camino de u a v ya que Si lo contuviese uniendo el vértice uv seria un ciclo. Entonces u y v no están conectados y por tanto el grafo no es conexo.
Lo probamos por reducción al absurdo. Imaginemos que “e” estuviese en un ciclo.Sea el ciclo u, v, w, … , x, u e imaginemos sin perdida de generalidad que e = uv.Entonces existe un camino en G-e que une uv que seria u, x, …, w, v.
Veamos que dos vértices cualesquiera a1 y a2 de G-e están conectados, lo cual es absurdo ya que ya que G-e debería ser disconexo porque e=uv es un puente.
Definición: Un árbol es un grafo conexo sin ciclos.
Árbol p=2 Árbol p=3Árbol p=1 Árboles p=4
Árboles p=6
Sean p1 y p2 respectivamente el orden de T1 y T2 y q1 ,q2 sus tamaños.Evidentemente, k=p1+p2 y q=q1+q2+1.Como p1 y p2 son menores que k-1 por hipótesis se cumple que q1=p1-1 y q2=p2-1Entoncesq=q1+q2+1=(p1-1)+(p2-1)+1=p1+p2-1=k-1
Teorema: Un árbol de orden p tiene tamaño p-1.
Si p=1, hemos visto que q=0.Si p=2, también hemos visto que q=1.
Suponemos que hasta orden k-1 se cumple.Lo demostramos para p=k.
Sea T un árbol de orden k. Tenemos que probar que tiene tamaño q= k-1. Como todos las aristas son puentes si quitamos una, quedarían dos componentes T1 y T2.
Ejercicio: Sean T1 =(V1,A1) y T2=(V2,A2) dos árboles tales que |A1|=17, |V2|=2|V1| . Determinar |V1|, |V2| y |A2|.
V1 es 18 ya que el tamaño de un árbol de orden p es p-1.
V2=36 ya que 2*18=36 y A2 = 35
Consecuencia. Sea G un grafo de orden p- Entonces las siguientes afirmaciones son equivalentes:(1) G es un árbol. (Conexo y sin ciclos)(2) G tiene tamaño p-1 y no tiene ciclos.(3) G es conexo y tiene tamaño p-1.
(2)->(3) Tenemos que ver que es conexo. Si no fuese conexo, tendría k árboles (ya que no tiene ciclos). Cada árbol tendría p1, p2, … , pk vértices con p1+p2+ ...+ pk=p. Aplicando el teorema anterior tendría tamañop1-1+p2-1+ ...+ pk-1=p-k. Como sabemos que tiene tamaño p-1 se tiene que k=1. Es decir una única componente y por tanto conexa.
(1)->(3) Por el teorema anterior sabemos que tiene tamaño p-1.
(3)->(1) Como ejercicio. Basta observar cual es el menor numero de aristasNecesarias para hacer un ciclo.( Para una demostración rigurosa consultar Gross)
Teorema: Todo árbol con p≥2 contiene al menos dos vértices extremos (grado 1).
∑ di ≥ 1 + 2 (p-1)= 2p -1 (1)(un vértice tiene grado 1 y los otros como mínimo tienen grado 2)
Uniendo el teorema 1 de la clase 1 y que como T es un árbol tiene p-1 aristas
∑ di=2q=2(p-1)=2p-2. (2)
Uniendo (1) y (2) tenemos 2p-2 ≥ 2p -1 que es absurdo
Vamos a probarlo por reducción al absurdo. Supondremos que no es cierto y llegaremos a una contradicción.
Sea T un árbol de orden p y tamaño q con secuencia de grados d1 ≤ d2 ≤ … ≤ dp Como T es conexo al menos cada vértice tiene grado 1 es decir di ≥ 1.
Supongamos que no contiene al menos dos vértices de grado 1. Es decir contendría o 0 o 1. Cero no puede ser ya que es conexo. Entonces tendríaque tener solo un vértice de grado 1. Entonces se d1 =1 y di ≥2 para los demás vértices. Entonces
Teorema: Si u y v son dos vértices distintos de un árbol T, entonces TContiene exactamente un camino (path) u-v.
Sabemos que existe al menos 1 ya que es conexo.Igual que antes vamos a demostrarlo por reducción al absurdo.Supongamos que existen dos caminos P y Q que unen u y v.Entonces tiene que existir un vértice ui donde el siguiente vértice en los dos caminos es diferente. De igual forma existe un vértice u n-j a partir del cual ambos tienen los mismos vértices.
u ui
un-1 vun-ju2
P
Q
a1 am
ui+1 u n-j-1
Si esto pasase, existiría un ciclo y es absurdo ya que los árboles no tienen ciclos.
Algoritmo Depth-First Search
Es un algoritmo que garantiza que de forma sistemática recorremos todos los vértices del grafo. Esta basado en el concepto de pila
L M N O P
G
Q
H JI K
FED
B C
A
Apilar
Desapilar
Pila
7
2
5
8 4
6
31
Ejemplo: Recorrer todos los vértices del siguiente grafo mediante DFS empezando en 1.
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
7
25
8 4
6
31
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
7
25
8 4
6
31
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
7
25
8 4
6
31
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0v2 - 6 v1v20 0
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1
v3
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
7
25
8 4
6
31
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1
v3
v4 7 8 v1v3v41 0
v4
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1
v3
v4 7 8 v1v3v41 0
v4
v3 - 8 v1v30 1 7
25
8 4
6
31
Actual
Asignamos Etiqueta(si actual es nuevo)
Aumentamosetiqueta(si hubo asignación de etiqueta) Pila
v1 1 2 v1
Huboasignaciónetiqueta
1
Adyacentes
v11
v2 2 3 v1v21 1 v2
v5 3 4 v1v2v51 1 v5
v6 4 5 v1v2v5v61 0v6
5
v5 - 5 v1v2v50 1
v8 5 6 v1v2v5v81 0
v8
v5 - 6 v1v2v50 0v2 - 6 v1v20 0v1 - 6 v10 1v3 6 7 v1v31 1
v3
v4 7 8 v1v3v41 0
v4
v3 - 8 v1v30 1v7 8 9 v1v3v71 0
v7
v3 - 9 v1v30v1 - 9 v10
7
25
8 4
6
31
v1
v6
7
25
8 4
6
1
v7v4
v8
v5
v2v3
3
Añade
Elimina
2 3 4 8 1 3 5 11
Algoritmo Depth-First Search
L M N O P
G
Q
H JI K
FED
B C
A
Es un algoritmo parecido al DFS que garantiza que de forma sistemática recorremos todos los vértices del grafo. Esta basado en el concepto de cola.
7
25
8 4
6
31
7
25
8 4
6
31
(1) v1
v1
7
25
8 4
6
31
(1) v1
(2) v1 v2 v3 v4 v6 v7 v8 v8v2 v3 v7v6v4
v2 v3 v4 v6 v7 v8
v1
7
25
8 4
6
31
(1) v1
v1
(2) v1 v2 v3 v4 v6 v7 v8 v8
v2 v3 v4 v6 v7 v8(3)
v2 v3 v7v6
v5
v4
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5v5
7
25
8 4
6
31
(1) v1
v1
(2) v1 v2 v3 v4 v6 v7 v8 v8
v2 v3 v4 v6 v7 v8(3)
v2 v3 v7v6
v5
v4
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5v5
(4) v3 v4 v6 v7 v8 v5 v4 v6 v7 v8 v5
7
25
8 4
6
31
(1) v1
v1
(2) v1 v2 v3 v4 v6 v7 v8 v8
v2 v3 v4 v6 v7 v8(3)
v2 v3 v7v6
v5
v4
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5v5
(4) v3 v4 v6 v7 v8 v5 v4 v6 v7 v8 v5
v4 v6 v7 v8 v5(5) v6 v7 v8 v5
7
25
8 4
6
31
(1) v1
v1
(2) v1 v2 v3 v4 v6 v7 v8 v8
v2 v3 v4 v6 v7 v8(3)
v2 v3 v7v6
v5
v4
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5v5
(4) v3 v4 v6 v7 v8 v5 v4 v6 v7 v8 v5
v4 v6 v7 v8 v5(5) v6 v7 v8 v5
v6 v7 v8 v5 v7 v8 v5(6)
(7)
(8)
v7 v8 v5 v8 v5
v8 v5v5
7
25
8 4
6
31
v1
v8v2 v3 v7v6
v5
v4
v1
v6
v7v4
v8
v5
v2v3
DFSDBS
