...... Algo algo algo algo

.....
























CURSO SOBRE TEORIA DE GRAFOS




Contenido




Apunte 1 – Introduccion

Apunte 2 – Arboles
Apunte 3 – Mas sobre arboles
Apunte 4 – Caminos en un grafo
Apunte 5 – Flujo en un grafo
Apunte 6 – ConectividadAnexo 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 deKö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 porEuler 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 decaminos 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 uncolor 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 yvolver 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. (ciclohamiltoniano)

1.6 El problema de cruzar el rio
Tenemos 3 misioneros y 3 canibales y un bote para cruzar el rio. El bote tiene capacidad para 2 personas a lo sumo. Se trata que los 6 individuos cruzen el rio de forma que en ningun momento haya mas canibales que misioneros en cualquiera de los dos margenes del rio. Indiquemos con (i,j) el hecho que haya i misioneros y j canibales en un dado margen.Entonces (i,j)((i-1, j-1) significa una posible transicion, es decir, cruzan el rio un misionero y un canibal. A continuacion (i-1, j-1) ((i, j-1) significa que volvio 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 un sucesion de flechas consecutivas que...