Sistemas de base datos

IIC 2252 - Matem´tica Discreta a
L. Dissett Clase 21 — Problemas en teor´ de grafos ıa

c Luis Dissett.

P.U.C. Chile, 2004

An´lisis del problema (Euler) a
El problema de los puentes de K¨nigsberg se puede expresar como sigue: ¿Tiene el o grafo de la figura un camino (o circuito) que pase por cada arista exactamente una vez?

Un circuito con esta caracter´ ıstica se llama circuitoEuleriano (en honor a Leonard Euler). Un grafo con un circuito Euleriano se dice grafo Euleriano.

1
c Luis Dissett. P.U.C. Chile, 2004

An´lisis del problema (cont.) a
Supongamos que podemos recorrer las aristas de un grafo (los puentes de K¨nigsberg) o en la forma pedida, y ordenemos el camino como sigue:

En cada v´rtice que no es ni el inicial ni el final, el camino debe salir una vez porcada e vez que entra. As´ el grado de cualquier v´rtice excepto, posiblemente, los extremos del camino debe ı, e ser par.

2
c Luis Dissett. P.U.C. Chile, 2004

An´lisis del problema (cont.) a
¿Qu´ pasa con los v´rtices extremos? e e Si los extremos no coinciden (o sea, el camino no es un circuito) entonces la primera salida desde el v´rtice inicial no es compensada por ninguna entrada.Asimismo, la e ultima entrada en el v´rtice final no es compensada por ninguna salida. ´ e As´ si el camino no es un circuito, los v´rtices inicial y final deben tener grado impar. ı, e Si el camino es un circuito, la primera salida y la ultima entrada se compensan ´ mutuamente, y el v´rtice inicial/final tiene grado par, igual que los otros v´rtices. e e

3
c Luis Dissett. P.U.C. Chile, 2004An´lisis del problema (Resumen) a
Para que un grafo sea Euleriano, no puede haber m´s que dos v´rtices de grado a e impar en el grafo. Si el grafo tiene dos v´rtices de grado impar, todo camino Euleriano debe comenzar e en uno de ellos y terminar en el otro. Si el grafo no tiene v´rtices de grado impar, todo camino Euleriano debe ser un e circuito, y puede comenzar en cualquier v´rtice. e

4
cLuis Dissett. P.U.C. Chile, 2004

Dibujos sin levantar el l´piz a
Una variante muy conocida del problema de determinar si un grafo es Euleriano es el de dibujar una figura de un solo trazo, o sea, sin levantar el l´piz del papel. a Ejemplo: ¿cu´les de las siguientes figuras pueden ser dibujadas con s´lo un trazo? a o

5
c Luis Dissett. P.U.C. Chile, 2004

Dibujos sin levantar el l´piz (cont.)a
M´s a´n: si no es posible dibujar una figura dada con un solo trazo, ¿cu´ntos trazos a u a son necesarios? Si en una figura hay 2n v´rtices de grado impar1 entonces se necesitan exactamente n e trazos para dibujarla.

1

Se puede demostrar que el n´mero de v´rtices de grado impar en un grafo siempre es par. u e

6
c Luis Dissett. P.U.C. Chile, 2004

Rutas en una red de caminos
Ungrafo puede ser usado para modelar caminos entre distintos puntos de una red caminera (o el´ctrica, o hidr´ulica, etc.). Los v´rtices son las intersecciones de caminos e a e y las aristas son los tramos de caminos entre intersecciones. Definici´n 1. o Un camino (path) es un grafo simple, cuyos v´rtices pueden ser ordenados de modo e que dos v´rtices son adyacentes sii son consecutivos en la lista. ePara cada n ≥ 2, el unico camino2 con n v´rtices es denominado Pn. ´ e Un camino en un grafo G es un subgrafo de G isomorfo a alg´n Pn. u Un problema importante (y con mucha aplicaci´n) en Teor´ de Grafos es el de hallar o ıa el camino m´s corto entre dos puntos. Por ejemplo: en Santiago, ¿cu´l es el camino a a m´s corto entre el Apumanque y el Museo Interactivo Mirador? Un sitio web que a resuelveeste problema es http://www.mapcity.cl.

2

Salvo isomorfismo.

7
c Luis Dissett. P.U.C. Chile, 2004

Ciclos
Definici´n 2. Un ciclo es un grafo con el mismo n´mero de aristas que de v´rtices, o u e cuyos v´rtices pueden ser puestos alrededor de un c´ e ırculo de modo que dos v´rtices e son adyacentes sii son aparecen consecutivamente a lo largo del c´ ırculo. Para cada n ≥ 3, el unico...