Ejemplos Grafos

EJEMPLO 1 SOBRE TEORIA DE GRAFOS

1. El ciclo euleriano

La ciudad de Königsberg está 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 repetir ninguna y volver a A (ciclo euleriano). Este problema fue encarado por Euler en 1736 y es el origen de la teoría de grafos.

figura 1 figura 2

EJEMPLO 2 SOBRE TEORIA DE GRAFOS

2. El ciclo hamiltoniano.

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

figura 3

Imaginemos a los vértices 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)

EJEMPLO 3 SOBRE TEORIA DE GRAFOS

3. Coloreado de mapas

La figura 4 muestra un mapa con 4 distritos A, B, C y D. Se trata de pintar cada distrito con un color de forma que dos regiones con un borde común (que no sea un punto) tengan distintos colores y queremos hacer esto usando un mínimo número de colores. La figura 5 muestra un grafo homeomorfo al mapa, en el sentido que los vértices del grafo se corresponden con las regiones del mapa y dos vértices están conectados por una rama cuando las regiones correspondientes tienen un borde común. El problema se traduce en el grafo a minimizar el número de colores al asignar un color a cada vértice de forma que cualquier rama tenga extremos de distinto color.

figura 4 figura 5

EJEMPLO 4 SOBRE TEORIA DE GRAFOS

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 está 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 número de calles que está obligado a recorrer más de una vez.

EJEMPLO 5 SOBRE TEORIA DE GRAFOS

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)

EJEMPLO 6 SOBRE TEORIA DE GRAFOS

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)

7.- Determine

...