CURSO SOBRE TEORIA DE GRAFOS

CURSO SOBRE TEORIA DE GRAFOS

Contenido

Apunte 1 – Introducción

Apunte 2 – Arboles

Apunte 3 – Más sobre arboles

Apunte 4 – Caminos en un grafo

Apunte 5 – Flujo en un grafo

Apunte 6 – Conectividad

Anexo a 6 – Teorema de Menger

Apunte 7 – Planaridad

Anexo a 7 – Teorema de Kuratowski

Apunte 8 - Colorabilidad

Marzo 2007

1. Ejemplos de Problemas

2. Definiciones

3. Algunos Teoremas

4. Optimizacion Combinatoria

1. Ejemplos de problemas

1.1 El ciclo euleriano

La ciudad de Königsberg esta atravesada por un rio que tiene 2 islas y 7 puentes como muestra la figura 1. Se pregunta si es posible partir del sector A y, haciendo una caminata, pasar por cada puente una sola vez volviendo al punto de partida. En el grafo de la figura 2 el problema se traduce en partir de A y recorrer las 7 ramas sin repertir ninguna y volver a A (ciclo euleriano). Este problema fue encarado por Euler en 1736 y es el origen de la teoria de grafos.

figura 1 figura 2

1.2 El ciclo hamiltoniano.

A un dodecaedro, cuerpo solido regular con doce caras pentagonales, se la ha quitado una cara y se lo ha äplastado en el plano como muestra la figura 3

figura 3

Imaginemos a los vertices de esta figura como ciudades y a las aristas como tramos de caminos entre dos ciudades. Se pregunta si hay un camino formado de tramos que partiendo de una ciudad visite todas las ciudades una sola vez volviendo a la ciudad de partida (ciclo hamiltoniano)

1.3 Coloreado de mapas

La figura 4 muestra un mapa con 4 districtos A, B, C y D. Se trata de pintar cada districto con un color de forma que dos regiones con un borde comun (que no sea un punto) tengan distintos colores y queremos hacer esto usando un minimo numero de colores. La figura 5 muestra un grafo homeomorfo al mapa, en el sentido que los vertices del grafo se corresponden con las regiones del mapa y dos vertices estan conectados por una rama cuando las regiones correspondientes tienen un borde comun. El problema se traduce en el grafo a minimizar el numero de colores al asignar un color a cada vertice de forma que cualquier rama tenga extremos de distinto color.

figura 4 figura 5

1.4 El recorrido del cartero

Imaginemos un grafo que representa el mapa de las calles de un barrio. Una calle va de una esquina a la otra. En una esquina esta ubicada una oficina de correos. Un cartero sale de la oficina de correos y tiene que recorrer todas las calles y volver a la oficina. Se plantea el problema de un recorrido que minimice el numero de calles.que esta obligado a recorrer mas de una vez.

1.5 El problema del caballo en el juego de ajedrez

Consideremos un tablero de ajedrez. y un caballo. Se pregunta si es posible que el caballo parta de un casillero y visite todos los otros 63 casilleros una solo vez volviendo al punto inicial. (ciclo hamiltoniano)

1.6 El problema de cruzar el rio

Tenemos 3 misioneros y 3 caníbales y un bote para cruzar el rio. El bote tiene capacidad para 2 personas a lo sumo. Se trata que los 6 individuos crucen el rio de forma que en ningún momento haya más caníbales que misioneros en cualquiera de los dos márgenes del rio. Indiquemos con (i,j) el hecho que haya i misioneros y j caníbales en un dado margen. Entonces (i,j)(i-1, j-1) significa una posible transición, es decir, cruzan el rio un misionero y un caníbal. A continuación (i-1, j-1) (i, j-1) significa que volvió el misionero solo. Imaginemos que dibujamos todos los pares (i,j) como puntos en el plano (ij) y unimos por flechas los pares que representan transiciones posibles. Se trata de hallar una sucesión de flechas consecutivas que parta de (3,3) y termine en (0,0)

2. Definiciones

2.1 Multígrafo

Sea E={a,b,c,...} un cjto de elementos que llamamos ramas y V= {A,B,C,...} un cjto de elementos que llamamos vertices. Una asignación de cada rama a un par de vertices lo llamamos un multígrafo. Por ejemplo, la figura 2 muestra un multígrafo

E= { a1 , a2 , a3 , a4 , a5 , a6 , a7 } (los puentes)

V= { A , B , C , D } (los distritos)

a1(A,B) a5 (A,D)

a2(A,B) a6 (B,D)

a3(B,C) a7 (C,D)

a4(B,C)

Un camino es una sucesión alternada de vertices y ramas u1, e1, u2, e2, u3, ..., un, en, en+1 tales que ei=(ui, ui+1) y ei  ei+1 (1i  n)

figura 6

c

La figura muestra un grafo con dos vertices A y B y 4 ramas a, b , c y d (a y d son rulos) Un posible camino es AaAbBdB que une A y B. .Un camino se dice cerrado o ciclo si el vertice inicial coincide con el final, por ejemplo, AcBbA. Un camino se dice euleriano si pasa por todos las ramas una y sola una vez, p.ejemplo, AaAbBdBcA es un ciclo euleriano. Un multígrafo se dice conexo si para todo par de vertices existe un camino que los une. El grado de un vértice es el numero de ramas que inciden sobre el. En el multígrafo de figura 6 A y B tienen grado 4.

Teorema (Euler)

Un multígrafo conexo tiene un ciclo euleriano sii todos sus vertices tienen grado par.

Demostración: Ver mas abajo.

2.2 grafo (simple)

Un grafo es un multígrafo que tiene a lo sumo una rama entre dos vertices y no tiene rulos. Los conceptos de camino, ciclo, euleriano, conexo y grado coinciden con los mas arriba definidos. Además decimos que un camino o ciclo es ha miltoniano si pasa por todos los vertices una y solo una vez.. Si un par de puntos tiene una rama que los une decimos que son adyacentes,

Un grafo G lo representamos mediante (V,E) donde V es el conjunto de vertices y EVxV es el cjto de ramas.Si un grafo tiene V=n vertices el maximo numero de ramas es E . Asi, un grafo con 4 vertices tiene a la sumo 6 ramas. Al grafo que tiene 4 vertices y 6 ramas lo designamos con K4. La figura 7 muestra una representacion de K4 (izquierda)

figura 7

K4 K4 – (2,3) K4 – {1}

Un subgrupo se obtiene de un grafo restandole parte de sus elementos. Por ejemplo si a K4 le restamos la rama (2,3) obtenemos el subgrafo del medio de la figura 7 y si le restamos el vertice 1 resulta el subgrafo de la derecha

Un grafo es bipartito si V esta dividido en 2 partes no vacias U y W y EUxW. Si m=U  y n=W  entonces el maximo numero de ramas es mxn. Si tiene mxn ramas entonces el grafo bipartito se dice completo y se escribe Km n . En la figura 8 (izquierda) representamos K2 3

figura 8

K2 3 Arbol

Un arbol es una grafo conexo que no tiene ciclos. También se puede caracterizar un arbol diciendo que desde cualquier vertice hay un solo camino para llegar a otro vertice. Un arbol es un grafo bipartito conexo.

2.3 grafo dirigido o digrafo

Un grafo dirigido o digrafo es un conjunto de vertices tambien llamados nodos V y un subconjunto E de pares de vertices de V llamados arcos donde el par se considerada dirigido, es decir, si AV y BV entonces (A,B) y (B,A) son arcos distintos. Si (A,B) es un arco entonces llamamos a A la cola y a B la punta de (A,B), Si V = n entonces el maximo numero de arcos que el digrafo puede tener es n(n-1). Un camino dirigido en un grafo G dirigido es una sucesion de vertices tal que si xn y xn+1 son dos vertices sucesivos entonces (xn , xn+1) es arco del grafo. Un camino es una sucesion de vertices tal que si xn y xn+1 son vertices sucesivos entonces (xn , xn+1) o (xn+1 , xn ) pertenece a E. Un digrafo es fuertemente conexo si cualquier par de vertices se puede unir por un camino dirigido

.

figura 9: Un digrafo fuertemente conexo

...