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 1
Coordinador 2
Trabajador 2
Trabajador 3 Trabajador 4 Trabajador 5
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)
3
3
7
2
8
4
8
2
2
5
Definiciones:
u
v
e1
e2
e4
e6
x
u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y
e3
w e7
e5
En general escribiremos u, v, w, x, u, v, y
y
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.
Definiciones:
u
v
e1
e2
e4
e6
x
u, e4, x, e6, w, e3, v, e5, y
e3
w e7
u, x, w, v, y
e5
u
v
y
e3
e4
e6
x
e5
w
y
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.
Definiciones:
u
v
e1
e2
e4
e6
x
u, e1, v, e5, y, e7, w, e2, u
e3
w e7
e5
u, v, y, w, u
u
e1
y
v
e2
w e7
e5
y
Definición: Una ciclo (cycle) es un camino que empieza y acaba en el mismo
vértice.
Definiciones:
u
v
e1
e2
e4
e6
x
x, e6, w, e3, v, e1, u, e2, w, e7, y
e3
w e7
e5
x, w, v, u, w, y
u
y
e2
e6
x
v
e1
e3
w e7
y
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.
Definiciones:
u
v
e1
e2
e4
e6
x
x, e6, w, e3, v, e5, y, e7, w, e2, u, e4, x
e3
w e7
e5
x, w, v, y, w, u, x
u
y
v
e2
e3
e4
e6
x
e5
w e7
y
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.
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 donde
estos dos vértices no están repetidos. Repitiendo el proceso hasta que no haya
vértices repetidos nos daría un camino de u a v.
u
v
e
1
e2
e3
e4
e6
x
w e7
u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y
e5
y
u, e1, v, e3, w, e6, x, e4, u, e1, v, e5, y
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
Grafo conexo G
K(G)=1
v1
v2
v2
v3
v4
K(G-v3)=2
V3 es un
vértice de corte
v4
v5
v5
v6
v6
v1
K(G-v2)=1
V2 NO es un
vértice de corte
v1
v3
v4
v2
v3
v5
v6
K(G-v5)=2
V5 es un
vértice de corte
v4
v6
Definición: Una arista e de un grafo G se denomina puente si K(G-e) ≥ K(G)
v1
v3
v5v4 es puente
K(G –v5v4)=2
v1
Grafo conexo G
K(G)=1
v2
v2
v4
v5
v3
v6
v4
v5
v6
v1
v1v2 NO
es puente
K(G –v1v2)=1
v2
v3
v4
v5
v6
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
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.
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.
Definición: Un árbol es un grafo conexo sin ciclos.
Árbol p=1
Árbol p=2
Árbol p=3
Árboles p=6
Árboles p=4
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.
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-1
Entonces
q=q1+q2+1=(p1-1)+(p2-1)+1=p1+p2-1=k-1
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.
(1)->(3) Por el teorema anterior sabemos que 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ño
p1-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.
(3)->(1) Como ejercicio. Basta observar cual es el menor numero de aristas
Necesarias 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).
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ía
que tener solo un vértice de grado 1. Entonces se d1 =1 y di ≥2 para los demás
vértices. Entonces
∑ 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
Teorema: Si u y v son dos vértices distintos de un árbol T, entonces T
Contiene 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.
P
a1
am
u
u2
un-j
ui
ui+1
Q
un-1
v
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
A
Pila
B
D
C
E
F
H
L
M
I
N
O
G
J
P
Apilar
K
Q
Desapilar
Ejemplo: Recorrer todos los vértices del siguiente grafo mediante DFS empezando en 1.
6
7
2
3
1
5
8
4
Actual
v1
Asignamos
Etiqueta
(si actual
es nuevo)
1
Hubo
asignación
etiqueta
1
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
2
Pila
v1
Adyacentes
v1
1
6
2
5
8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
6
2
5
8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
6
2
5
8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v6
6
2
5
8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v6
6
2
5
8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
5
1
6
v1v2v5v8
0
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
5
-
1
0
6
6
v1v2v5v8
v1v2v5
0
0
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
v2
5
-
1
0
0
6
6
6
v1v2v5v8
v1v2v5
v1v2
0
0
0
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
v2
v1
5
-
1
0
0
0
6
6
6
6
v1v2v5v8
v1v2v5
v1v2
v1
0
0
0
1
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
v1
1
1
2
v1
1
v2
2
1
3
v1v2
1
v2
v5
3
1
4
v1v2v5
1
v5
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
v2
v1
v3
5
6
1
0
0
0
1
6
6
6
6
7
v1v2v5v8
v1v2v5
v1v2
v1
v1v3
0
0
0
1
1
v3
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v2
2
1
3
v1v2
1
v5
3
1
4
v1v2v5
1 v4
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
v2
v1
v3
5
6
1
0
0
0
1
6
6
6
6
7
v1v2v5v8
v1v2v5
v1v2
v1
v1v3
0
0
0
1
1
v4
7
1
8
v1v3v4
0
v1
v3
v2
v5
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v2
2
1
3
v1v2
1
v5
3
1
4
v1v2v5
1 v4
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
v2
v1
v3
5
6
1
0
0
0
1
6
6
6
6
7
v1v2v5v8
v1v2v5
v1v2
v1
v1v3
0
0
0
1
1
v4
7
1
8
v1v3v4
0
v3
-
0
8
v1v3
1
v1
v3
v2
v5
v6
6
2
5
8
v8
7
3
1
4
Actual
Asignamos
Etiqueta
(si actual
es nuevo)
Hubo
asignación
etiqueta
Aumentamos
etiqueta
(si hubo
asignación
de etiqueta)
Pila
Adyacentes
v1
1
1
2
v1
1
v2
2
1
3
v1v2
1
v5
3
1
4
v1v2v5
1 v4
v6
4
1
5
v1v2v5v6
0
v5
-
0
5
v1v2v5
1
v8
v5
v2
v1
v3
5
6
1
0
0
0
1
6
6
6
6
7
v1v2v5v8
v1v2v5
v1v2
v1
v1v3
0
0
0
1
1
v4
7
1
8
v1v3v4
0
v3
v7
8
0
1
8
9
v1v3
v1v3v7
1
0
v3
v1
-
0
0
9
9
v1v3
v1
v1
v3
v2
v5
v7
v6
6
2
5
8
v8
7
3
1
4
v1
6
2
5
7
v2
v3
1
3
8
4
v5
v4
v7
v6
v8
Algoritmo Depth-First Search
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.
A
Elimina
B
D
C
E
F
H
L
M
I
N
O
G
J
P
Añade
K
Q
2
3
4
8
1
3
5
11
6
7
2
5
8
3
1
4
6
7
2
5
3
1
8
4
v1
(1)
v1
6
7
2
5
3
1
8
4
v1
(1)
v1
(2)
v1
v2 v3 v4 v6 v7 v8
v2
v3
v4
v6
v7
v8
v2 v3 v4 v6 v7 v8
6
7
2
5
3
1
8
4
v1
(1)
v1
(2)
v1
(3)
v2 v3 v4 v6 v7 v8 v5
v2 v3 v4 v6 v7 v8
v2
v5
v3
v4
v6
v7
v8
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5
6
7
2
5
3
1
8
4
v1
(1)
v1
(2)
v1
(3)
v2 v3 v4 v6 v7 v8 v5
(4)
v3 v4 v6 v7 v8 v5
v2 v3 v4 v6 v7 v8
v2
v5
v3
v4
v6
v7
v8
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5
v4 v6 v7 v8 v5
6
7
2
5
3
1
8
4
v1
(1)
v1
(2)
v1
(3)
v2 v3 v4 v6 v7 v8 v5
(4)
v3 v4 v6 v7 v8 v5
v4 v6 v7 v8 v5
(5)
v4 v6 v7 v8 v5
v6 v7 v8 v5
v2 v3 v4 v6 v7 v8
v2
v5
v3
v4
v6
v7
v8
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5
6
7
2
5
3
1
8
4
v1
(1)
v1
(2)
v1
(3)
v2 v3 v4 v6 v7 v8 v5
(4)
v3 v4 v6 v7 v8 v5
v4 v6 v7 v8 v5
(5)
v4 v6 v7 v8 v5
v6 v7 v8 v5
(6)
v6 v7 v8 v5
(7)
v7 v8 v5
(8)
v8 v5
v2 v3 v4 v6 v7 v8
v2
v5
v3
v4
v6
v7
v8
v2 v3 v4 v6 v7 v8
v3 v4 v6 v7 v8 v5
v7 v8 v5
v8 v5
v5
6
7
2
5
8
3
1
4
v1
v1
v2
v3
v2
v3
v4
v6
v5
v5
v4
v7
v6
DFS
v8
DBS
v7
v8
Descargar

Diapositiva 1