Tema 4: Planaridad

Dpto. Matemática Aplicada I – Matemática Discreta

 Tema 4: Planaridad

Introducción

Conceptos básicos
Teorema de Euler
Test de planaridad
Teorema de Kuratowsky
Teorema de Wagner

Teorema de los cuatro colores

Diseño de circuitos
 Introducción

Se desea dotar a tres casas de tres suministros diferentes: agua, gas y electricidad, ¿será
posible llevar a cabo la infraestructura necesaria sin que se crucen las conducciones de los
distintos fluidos?

Compañía de aguas

Casa A
Casa C

Casa B

Central eléctrica

Compañía de gas
 Tema 4: Planaridad

Introducción

Conceptos básicos
Teorema de Euler
Test de planaridad
Teorema de Kuratowsky
Teorema de Wagner

Teorema de los cuatro colores

Grafos planos

Una representación gráfica de un grafo en una superficie S (por ejemplo el plano)

se dice que es una inmersión en S si dos aristas no se cortan en puntos que no sean
vértices del grafo.

Inmersión en el plano

Un grafo se dice que es un grafo plano si admite una inmersión en el plano.

Grafos planos

K4 es un grafo plano K5 NO es un grafo plano ????

 Grafos planos G=(V,A) grafo plano

Caras de un grafo plano = regiones PROPIEDADES:

delimitadas por las aristas del grafo
1. Las aristas frontera de cada cara interior o acotada
v1 forman un ciclo.
v2
C1
2. Si se elimina una arista l de un ciclo, el grafo G-l
v3 cara exterior tiene una cara menos.
C5
v4 v5

C2
v7
v6 v8
C3 C4

v9

aristas puente
Aristas
aristas frontera
 Grafos planos G=(V,A) grafo plano

Caras de un grafo plano = regiones PROPIEDADES:

delimitadas por las aristas del grafo
1. Las aristas frontera de cada cara interior o acotada
v1 forman un ciclo.
v2
C1
2. Si se elimina una arista l de un ciclo, el grafo G-l
v3 cara exterior tiene una cara menos.
C5 C4
v4 v5

C2
v7
v6 v8
C3

v9

aristas puente
Aristas
aristas frontera
 Grafos planos G=(V,A) grafo plano

Caras de un grafo plano = regiones PROPIEDADES:

delimitadas por las aristas del grafo
1. Las aristas frontera de cada cara interior o acotada
v1 forman un ciclo.
v2
C1
2. Si se elimina una arista l de un ciclo, el grafo G-l
v3 cara exterior tiene una cara menos.
C5 C4 C3
v4 v5

C2
v7
v6 v8

v9

aristas puente
Aristas
aristas frontera
 Grafos planos G=(V,A) grafo plano

Caras de un grafo plano = regiones PROPIEDADES:

delimitadas por las aristas del grafo
1. Las aristas frontera de cada cara interior o acotada
v1 forman un ciclo.
v2
C1
2. Si se elimina una arista l de un ciclo, el grafo G-l
v3 cara exterior tiene una cara menos.
C5
v4 v5 3. Si una arista forma parte de un ciclo, es frontera de
dos caras exactamente.
C2
v7
v6 v8 4. En la frontera de cada cara hay al menos tres aristas.
C3 C4
5. Si G tiene c caras y a aristas: 3 c ≤ 2 a
v9
6. Si G tiene a aristas y c caras , cada una delimitada al
aristas puente menos por d aristas:
Aristas
aristas frontera dc≤2a
 Grafos planos G=(V,A) grafo plano

Fórmula de Euler:
G=(V,A) plano y conexo, con c caras, a aristas y n vértices: n+c= a+2

Inducción en a:
1) Caso inicial: Si a=1 n = 2; c = 1; a=1 ⟹n+c=a+2

2) H.I. Supongamos que es cierto para todo grafo con a-1 aristas
3) ¿Cierto para a aristas? Sea G un grafo plano conexo con a aristas, c caras y n vértices
Si G es un árbol ⟹ c = 1; n = a + 1 ⟹n+c=a+1+1=a+2
Si G NO es un árbol
Vértices + caras=aristas +2
a-1 aristas H.I.
⟹ Sea l una arista de ⟹ G-l c-1 caras Grafo G-l
⟹ n + c -1 = a -1 + 2
un ciclo n vértices
n+c=a+2 Grafo G
 Grafos planos G=(V,A) grafo plano

Fórmula de Euler (para grafos no conexos):

G=(V,A) plano con d componentes conexas, con c caras, a aristas y v vértices: n + c = a + d +1

Dem:

G1 G2 G3 Gd

n1 + c1= a1 + 2 n2 + c2= a2 + 2 n3 + c3= a3 + 2 nd + cd= ad + 2

n1+ n2+ …+ nd = n a1 + a2+…+ ad = a

c1+ c2 +…+ cd = c + (d-1)
+ = + 2 + 2 +…+ 2 = 2 d

n + c + (d-1) = a + 2d
n + c= a + d + 1
 Tema 4: Planaridad

Introducción

Conceptos básicos
Teorema de Euler
Test de planaridad
Teorema de Kuratowsky
Teorema de Wagner

Teorema de los cuatro colores

Grafos planos G=(V,A) grafo plano

Grafo plano maximal es un grafo plano tal que al añadir una arista entre dos
vértices no adyacentes cualesquiera, deja de ser plano.

v2

v3

v4

v1

grafo plano NO maximal grafo plano maximal

Si un grafo plano G=(V,A) es maximal (y tiene al menos dos caras), las caras están
limitadas por triángulos (ciclos de longitud 3).
 Grafos planos G=(V,A) grafo plano

Teorema:
Si G=(V,A) es un grafo plano maximal, con a aristas y n vértices (n ≥ 3): a = 3n - 6

Dem:

Las caras están limitadas por triángulos

⟹3c=2a
y cada arista es frontera de dos caras: ⟹ a = 3n - 6
Teorema Euler ⟹ n + c = a + 2

grafo plano maximal

Corolario: Si G=(V,A) es un grafo plano con a aristas y n vértices: a ≤ 3n - 6

Tests de planaridad Si a ≤ 3n – 6 (Pasa el test) ⇒ ???

Si a > 3n – 6 ⇒ G=(V,A) NO es plano
Grafos planos
Tests de planaridad Si a ≤ 3n – 6 (Pasa el test) ⇒ ???
Si a > 3n – 6 ⇒ G=(V,A) NO es plano

¿Es plano?

n=5
⟹ a > 3n - 6
a = 10

K5
K5 NO ES PLANO
 Grafos planos
Tests de planaridad Si a ≤ 3n – 6 (Pasa el test) ⇒ ???
Si a > 3n – 6 ⇒ G=(V,A) NO es plano

¿Es plano?

n=6
⟹ ‫ܭ‬3,3 verifica el test: a ≤ 3v - 6 ⇒ ???
a=9

‫ܭ‬3,3
Tests de planaridad
K3,3 bipartito
para grafos sin ‫ܥ‬ଷ
No contiene ‫ܥ‬ଷ ⟹ Cada cara tiene al menos 4 aristas ⟹ ૝ࢉ ≤ ૛ࢇ
⟹ ࢇ ≤ ૛࢔ − ૝
Teorema de Euler: ݊ + ܿ = ܽ + 2

K3,3 ⟹ ܽ > 2݊ − 4 ⟹ ࡷ૜,૜ NO ES PLANO

 Grafos planos G=(V,A) grafo plano

Subdivisión del grafo G es un nuevo grafo G’ obtenido insertando vértices en

algunas aristas, de manera que las subdividen.

Teorema de Kuratowski: Un grafo es plano si, y sólo si, no contiene ningún subgrafo
isomorfo a K5 ni a K3,3, ni a subdivisiones de ellos.
Teorema de Kuratowski: Un grafo es plano si, y sólo si, no contiene
ningún subgrafo isomorfo a K5 ni a K3,3, ni a subdivisiones de ellos. Aplicación
¿Es plano? u1

v3 v1
v2
d a
V1 = {u1, u2, u3}
u3
V2 = {v1, v2, v3}
u2
b c

{u1, v1} {u2, v1} {u3, v1}

{u1, v2} {u2, a, v2} {u3, c, v2}
{u1, v3} {u2, b, v3} {u3, d, v3}

El grafo de Petersen NO ES PLANO

Subdivisión de K3,3
 Grafos planos Grafo G=(V,A)

Contracción de aristas: operación en un grafo que consiste en eliminar una arista

fusionando los dos vértices extremos de la misma. De esta forma se obtiene un
nuevo grafo.

Teorema de Wagner: Un grafo es plano si, y sólo si, no contiene ningún subgrafo que
se pueda contraer a K5 o K3,3.
 Teorema de Wagner: Un grafo es plano si, y sólo si, no contiene
ningún subgrafo isomorfo a K5 ni a K3,3, ni se puede contraer a ellos. Aplicación
u1
¿Es plano?
v1

v3
v2
u2 u3

u1

v1

v3
v2
Por el teorema de Wagner,
el grafo de Petersen u2 u3
NO ES PLANO, ya que… …se puede contraer a un K3,3 …se puede contraer a un K5
 Tema 4: Planaridad

Introducción

Conceptos básicos
Teorema de Euler
Test de planaridad
Teorema de Kuratowsky
Teorema de Wagner

Teorema de los cuatro colores

Teorema de los cuatro colores : Todo grafo plano es 4-coloreable.
(K. Appel y W. Haken, 1976)