Teoría de Grafos.-clase 5
Grafos Planares & Coloración
El problema de las 3 casas y los 3 suministros
Definición: Un grafo que puede ser dibujado en el plano sin que sus aristas se
intersecten se denomina planar. Un grafo que es dibujado en el plano sin que
ninguna de sus aristas se intersecten se denomina plano.
Grafo planar
Grafo plano
Las áreas que permanecen conexas cuando las aristas son eliminadas se
denominan regiones. Todo grafo plano tiene exactamente una única región
no acotada llamada la región exterior. Los vértices y aristas incidentes con una
región R se denominan la frontera de R.
G tiene 5 Regiones.
Observación: p=8
q=11
r=5
p+r-q=2
Región Exterior
Teorema: (Formula de Euler). Si G es un grafo conexo plano con p vértices,
q aristas y r regiones, entonces
p-q+r=2
Procedemos por inducción.
Si q=0. Entonces G= K1 por lo que r=1, p=1,q=0 y 1+1-0=2 se cumple.
Suponemos que se cumple para q=k-1. Sea G un grafo de tamaño p con r regiones
y se cumple que p+r-k-1=2
Lo probamos para un grafo G de k aristas con p vértices y r regiones.
Si G es un árbol se tiene que q=p-1 y r=1. Entonces p+1-p+1=2 y se cumple.
Si G no es un árbol entonces tiene un ciclo. Eliminamos una arista de ese
ciclo con lo que G-e tiene orden p, tamaño k-1 y r-1 regiones. Entonces como
q=k-1 sabemos que es cierto y se tiene que:
p+r-1 – (k-1)=2 o lo que es lo mismo
p+r-k=2 que es lo que queríamos probar.
Definición: Un grafo plano se dice maximal si para cualquier par de vértices u,v
no adyacentes de G, el grafo G+uv no es planar.
Teorema: Si G es planar maximal (p,q) con p≥ 3. Entonces q=3p-6.
Si dibujamos G de forma que sea plano con r regiones entonces cada
región es un triangulo. Si no:
Si sumamos todas las aristas de todos los triángulos de forma independiente,
tendríamos 3r. Como cada arista toca dos regiones, este numero seria 2q.
Es decir 3r=2q o r=2q/3. Por el teorema de Euler:
p-q+r=2 => p=q-r+2 => p=q-2q/3+2 => p=q/3+2
=> q=3p-6
Consecuencia: Si G es planar (p,q) con p≥ 3. Entonces q ≤ 3p-6.
Si G es maximal, entonces por el teorema anterior q=3p-6.
Si no es maximal, añadimos aristas hasta que sea maximal planar (p’,q’).
Entonces p=p’ q < q’. Con lo que q < q’ =3p’-6=3p-6.
Teorema: Todo grafo planar tiene un vértice de grado 5 o menos
Sea G un grafo planar con p ≥ 7 ya que de otra forma todos los vértices
tendrían grado 5 o menos.
Por la consecuencia anterior q ≤ 3p-6 o lo que es lo mismo 2q ≤ 6p-12
Como ∑ v i =2q ≤ 6p-12 . Entonces no todos los vértices pueden tener grado 6
ya que sino seria mayor que 6p-12.
Teorema: Los grafos K5 y K3,3 son no planares.
K5 tiene orden 5 y q=10. Entonces 3p-6 =9 < q.
Entonces vimos anteriormente que no puede ser planar
En este caso se cumple la formula. Se necesita una forma diferente.
(reducción al absurdo)
Supongamos que fuese planar. Entonces se debería cumplir la
formula de Euler. Por tanto, 6-9+r=2 implica que r=5.
Como es bipartito cada región debería tener 4 aristas.
Si sumamos el numero de aristas de las regiones tenemos que N≥4r.
Por otro lado, como K3,3 no tiene puentes toda arista esta en 2 regiones
Entonces N=2q=18 => 4r ≤ 18 o lo que es lo mismo r menor que 3,5.
Lo cual es absurdo y por tanto planar.
Definición: Una subdivisión de un grafo G es un grafo obtenido insertando vértices
de grado2 en las aristas de G.
Teorema de Kuratowski: Un grafo es planar si y solo si no contiene un subgrafo
isomorfo a K5 o a K3,3 o a una subdivisión de K5 o a K3,3 .
Algoritmo para ver si un grafo es planar:
1.- Encontrar un ciclo que contenga todos los vértices del grafo
2.-Dibujar las aristas que no han sido usadas dentro y fuera del grafo
sin que se intersecten.
Ejemplo:
a
b
c
d
e
f
g
h
Ejemplo:
a
b
c
d
e
f
g
h
a
f
c
h
e
b
g
d
Ejemplo:
a
b
c
d
e
f
g
h
a
f
c
h
e
b
g
d
Ejemplo 2:
Planar
No Planar
Coloración
Hámster
León
León
Conejo
Tigre
Hurón
Hurón
Hámster
Conejo
Tigre
Definición: Un conjunto de vértices S en un grafo se dice independiente si ningún
par de vértices de S son adyacentes. Un conjunto independiente S se dice
independiente maximal si S no es un subconjunto de algún otro conjunto
independiente de vértices de S.
Conjunto Independiente
Conjunto Independiente maximal
Definición: El número de vértices del mayor conjunto independiente maximal de S
se denomina el numero de independencia de G y se representa por β(G)
β(G)= 4
Definiciòn: Un clique en un grafo G es un subconjunto completo maximal de G.
El orden máximo de un clique es el numero de clique y se representara por w(G).
Se cumple que w(G)= β(Gc).
w(G)=4
Definiciòn: Un conjunto S de vértices de un grafo G se dice que es un conjunto
dominador si todo vértice que no esta en S es adyacente a algún vértice de S.
El número de dominación σ(G) es el numero de vértices del conjunto dominador mas
pequeño.
σ(G)=2
Teorema: Para cualquier grafo G, σ(G) ≤β(G)
Sea S un conjunto de vértices independientes de G con cardinal β(G).
Como G no tiene un conjunto de vértices independientes mayor, todo los demás
vértices tienen que ser adyacentes a algún vértice de S. Por tanto S es también
un conjunto de dominación. Por tanto σ(G) ≤ |S| ≤ β(G)
Observación: No hay una forma automática de determinar el numero de independencia,
clique o dominación,
Definición: Una coloración de un grafo G es una asignación de colores (o números)
a los vértices de G de forma que vértices adyacentes tenga distintos colores.
Si n colores han sido usados se denomina un n-coloración. El mínimo número de colores
λ(G) necesario para hacer una coloración se denomina el número cromático de G.
λ(G)=4
Teorema: Un grafo es un 2-colorable si y solo si es bipartito.
Teorema: Sea G un grafo conexo con grado máximo Δ. Entonces
(i) w(G) ≤ λ(G) ≤ Δ +1
(ii) λ(G) ≤ Δ si y solo si G no es ni completo ni tiene un ciclo impar.(Brooke)
Observación: Esta cota superior puede diferir bastante. Por ejemplo, si G es K1000,2
la cota seria 1001 mientras que el numero de coloración es 2.
Algoritmo de coloración : no necesariamente usa el menor numero de colores
1. i=1
2. c=1
Mientras i < p
chivato=0;
Mientras chivato == 0
-Ordenar los colores adyacentes a vi en orden no decreciente
y formar la lista Li .
-Si c no aparece en Li asignar c a vi y chivato=1
si no c=c+1
i=i+1
v1 (0)
(1)
v5 (0)
(0) v7
i=1, c=1
L1= v5 (0) v7(0)
(0) v8
v4 (0)
(0) v2
v6 (0)
v3
(0)
v1 (1)
v5 (0)
(0) v7
i=2, c=1
L2= v3 (0) v4(0) v8(0)
(0) v8
v4 (0)
(0)
(1) v2
v6 (0)
v3
(0)
v1 (1)
v5 (0)
(0) v7
i=3, c=1
L3= v2 (1) v6(0)
(0) v8
v4 (0)
(1) v2
v6 (0)
v3
(0)
v1 (1)
v5 (0)
(0) v7
i=3, c=2
L3= v2 (1) v6(0)
(0) v8
v4 (0)
(1) v2
v6 (0)
v3
(0)
(2)
v1 (1)
v5 (0)
(0) v7
i=4, c=2
L4= v2 (1) v5(0) v6(0)
(0) v8
v4 (0)(2)
(1) v2
v6 (0)
v3
(2)
v1 (1)
v5 (0)
(0) v7
i=5, c=2
L5= v1 (1) v4(2) v8(0)
(0) v8
v4
(1) v2
(2)
v6 (0)
v3
(2)
v1 (1)
v5 (0)
(3)
(0) v7
i=5, c=3
L4= v1 (1) v4(2) v8(0)
(0) v8
v4
(1) v2
(2)
v6 (0)
v3
(2)
v1 (1)
v5
(0) v7
(3)
i=6, c=3
L6= v3 (2) v4(2)
(0) v8
v4
(1) v2
(2)
v6 (0) (3)
v3
(2)
v1 (1)
v5
(3) v7
(3)
i=7, c=3
L7= v1 (1) v8(0)
(0) v8
v4
(1) v2
v6
v3
(2)
(2)
(3)
v1 (1)
v5
(3) v7
(4) v8
v4
(1) v2
v6
v3
(2)
(3)
(2)
(3)
Ejemplo 2:
v1 (1)
v5 (0)
(0) v7
(0) v8
v4 (0)
(0) v2
v6 (0)
v3
(0)
Ejemplo 2:
v1 (1)
v5 (0)
(0) v7
(0) v8
v4 (0)
(1) v2
v6 (0)
v3
(0)
Ejemplo 2:
v1 (1)
v5 (0)
(0) v7
(0) v8
v4 (0)
(1) v2
v6 (0)
v3
(2)
Ejemplo 2:
v1 (1)
v5 (0)
(0) v7
(0) v8
v4 (2)
(1) v2
v6 (0)
v3
(2)
Ejemplo 2:
v1 (1)
v5 (3)
(0) v7
(0) v8
v4 (2)
(1) v2
v6 (0)
v3
(2)
Ejemplo 2:
v1 (1)
v5 (3)
(0) v7
(0) v8
v4 (2)
(1) v2
v6 (3)
v3
(2)
Ejemplo 2:
v1 (1)
v5 (3)
(3) v7
(0) v8
v4 (2)
(1) v2
v6 (3)
v3
(2)
Ejemplo 2:
v1 (1)
v5 (3)
(3) v7
(4) v8
v4 (2)
(1) v2
v6 (3)
v3
(2)
Ejemplo 2: (una mejor solucion)
v1 (2)
v5 (1)
(1) v7
(2) v8
v4 (2)
(1) v2
v6 (1)
v3
(2)
Descargar

Diapositiva 1