El canto del aguila

3004597 – Estructuras de Datos – Modulo 10

Universidad Nacional de Colombia – Sede Medellín

MODULO 10
OBJETIVOS Por medio de este módulo se pretende: • Introducir el TAD Grafo e ilustrarlo con ejemplos, particularmente con los puentes de la Isla de Kueiphof.

CONTENIDO 1 Grafos: Los puentes de la Isla de Kueiphof 1.1. Usos de los grafos 1.2. Definición formal de grafo 1.3. DefinicionesBásicas A Referencias

01 - 2006

1

3004597 – Estructuras de Datos – Modulo 10

Universidad Nacional de Colombia – Sede Medellín

1

GRAFOS: LOS PUENTES DE LA ISLA DE KUEIPHOF

En la isla Kueiphof en Koenigsberg (hoy Kaliningrado, Alemania) el río Pregel que la rodea se divide en dos brazos. Sobre los brazos estaban construidos siete puentes y para los habitantes era motivo dedistracción descubrir un itinerario de manera que pudieran regresar al punto de partida, después de haber cruzado por los siete puentes pero pasando sólo una vez por cada uno de ellos. Leonardo Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos. A la figura la llamó grafo, a los puntoslos llamó vértices y a las líneas las denominó aristas. Estudió si una figura lineal se podía dibujar con un solo trazo, sin levantar el lápiz del papel y sin pasar dos veces por el mismo sitio. Un vértice se dice que es Impar si de él parten un número impar de caminos. Euler llegó a las siguientes conclusiones: 1. Es imposible si hay más de dos vértices impares. 2. Es posible cuando: a) Todos losvértices son pares y el punto de partida puede ser cualquiera. b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro.

C
5

3

A D
3

B

3

01 - 2006

2

3004597 – Estructuras de Datos – Modulo 10

Universidad Nacional de Colombia – Sede Medellín

A la isla A llegan 5 puentes; a la B llegan 3puentes; a la orilla C llegan 3 puentes y a la orilla D llegan 3 puentes, por tanto, según las conclusiones anteriores, el problema no tiene solución. Estos dibujos pueden hacerse de un solo trazo:

Estos dibujos NO pueden hacerse de un solo trazo:

1.1 USO DE LOS GRAFOS Este estudio de Euler dio origen a la teoría de los grafos, que se emplean en el estudio de los circuitos eléctricos, enproblemas de transporte (en investigación de operaciones), programación, entre otras áreas del conocimiento. El físico Kirchhoff fue el primero que usó la Teoría de Grafos en el campo de la inteligencia eléctrica cuando en 1847 usó un modelo estructural G = (V,E) considerando los lados como elementos eléctricos pasivos (resistores, capacitores e inductores) y los nodos fueron las uniones donde dos o máselementos confluyen. También Kirchhoff parece ser el primero en introducir el concepto de árbol en su estudio de árboles generadores. El matemático inglés Arthur Cayley fue el primero que usó la teoría de Grafos en el campo de la Química, cuando en uno de sus artículos sobre enumeración gráfica determinó el número de parafinas CnH2n+2 (ahora llamados alcanos) usando un modelo estructural G = (V,E)considerando los átomos como nodos y los enlaces como lados. Uno de los problemas más conocidos en la teoría de Grafos es el problema de los cuatro colores en el cual los nodos son naciones en un mapa y los lados indican las fronteras.

01 - 2006

3

3004597 – Estructuras de Datos – Modulo 10

Universidad Nacional de Colombia – Sede Medellín

El problema de los cuatro colores consistebásicamente, en que cualquier mapa puede ser coloreado solamente con cuatro colores distintos de tal manera que dos regiones adyacentes (es decir, que tienen una frontera en común y no sólo un punto) no tengan el mismo color. Este problema fue planteado por primera vez por Francis Guthrie en 1850 y resuelto recientemente en 1996 por Neil Robertson, Daniel P. Sanders, Paul Seymour y Robin...