Tarea Mate

Cap´ ıtulo 4: Grafos Clase 3: Grafos planares y Colorabilidad de Grafos
Matem´tica Discreta - CC3101 a Profesor: Pablo Barcel´ o

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

1 / 18

Problema de las utilidades

Se tienen 3 casas y 3 utilidades (gas, aceite y agua) como se muestra en la figura.

¿Se puede conectar cada utilidad a cada casa de modo que las conexiones nose crucen?

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

2 / 18

Grafos planares

Este problema est´ relacionado con la siguiente noci´n: a o

Definition
Un grafo G es planar si puede ser dibujado en el plano sin que sus arcos se intersecten.

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

3 / 18

Grafos planares

Este problema est´ relacionado conla siguiente noci´n: a o

Definition
Un grafo G es planar si puede ser dibujado en el plano sin que sus arcos se intersecten. Por tanto, el problema anterior se reduce a verificar si K3,3 es planar.

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

3 / 18

Ejercicios

Ejercicio: Demuestre que el siguiente grafo es planar.

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4:Grafos a

4 / 18

Ejercicios

Ejercicio: Demuestre que el siguiente grafo es planar.

Ejercicio: Responda la pregunta inicial, i.e. ¿es K3,3 planar?

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

4 / 18

Ejercicios

Ejercicio: Demuestre que el siguiente grafo es planar.

Ejercicio: Responda la pregunta inicial, i.e. ¿es K3,3 planar? Ejercicio: Demuestre que K5 noes planar.

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

4 / 18

Regiones de un grafo

La representaci´n planar de un grafo divide al plano en regiones, o incluyendo una ilimitada (la exterior).

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

5 / 18

Regiones de un grafo

La representaci´n planar de un grafo divide al plano en regiones, o incluyendouna ilimitada (la exterior). Por ejemplo,

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

5 / 18

F´rmula de Euler o

Euler demostr´ que todas las representaciones planares de un grafo o simple planar tienen la misma cantidad de regiones:

Teorema
Sea G = (V , E ) un grafo simple que es conexo y planar. Sea r el n´mero de regiones en una representaci´n planar de G .Luego, u o r = |E | − |V | + 2

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

6 / 18

F´rmula de Euler o

Euler demostr´ que todas las representaciones planares de un grafo o simple planar tienen la misma cantidad de regiones:

Teorema
Sea G = (V , E ) un grafo simple que es conexo y planar. Sea r el n´mero de regiones en una representaci´n planar de G . Luego, u o r = |E |− |V | + 2 A continuaci´n demostraremos este teorema. o

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

6 / 18

Demostraci´n o
Asumamos una representaci´n planar de G . o Construiremos una secuencia G1 , G2 , . . . , G|E | de subgrafos de G , agregando un arco en cada paso, de tal forma que:
◮ ◮

G1 se compone de un arco arbitrario de G ; Gn+1 se obtiene desde Gn agregandoun arco cualquiera que no est´ en Gn , y que sea incidente a un v´rtice en Gn . e e

Note que esta definici´n es correcta pues el grafo es conexo. o Claramente, cada grafo Gj es planar, j ∈ [1, |E |], y G|E | = G .
P. Barcel´ o – Matem´tica Discreta - Cap. 4: Grafos a 7 / 18

Demostraci´n o
Demostraremos por inducci´n que para todo j ∈ [1, |E |], o Gj = (Vj , Ej ) satisface rj = |Ej | − |Vj |+ 2, u o donde rj es el n´mero de regiones en la representaci´n planar de Gj . El caso base es trivial, pues G1 tiene solo una regi´n, dos nodos y o un arco. Considere ahora el grafo Gj+1 , para j ∈ [1, |E | − 1], y sea {v , v ′ } el arco agregado para construir Gj+1 desde Gj . Analizaremos dos casos a continuaci´n. o

P. Barcel´ o

–

Matem´tica Discreta - Cap. 4: Grafos a

8 / 18...