Teoría De Grados

LOS SIETE PUENTES DE LA ISLA KUEIPHOF
La isla Kueiphof en Koenigsberg (Pomerania) el río que la rodea se divide en
dos brazos.
Sobre los brazos estaban construidos siete puentes y para loshabitantes era
motivo de distracció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 cadauno 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 puntos los 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 delpapel y sin pasar dos veces por el mismo sitio.

Llegó a la siguiente conclusión:
1. Es imposible si hay más de dos vértices impares.
2. Es posible cuando:
a) Todos los vértices son pares y elpunto 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.
(Impar es un vértice side él parten un número impar de caminos).
A la isla A llegan 5 puentes; a la B llegan 3 puentes; a la orilla C llegan 3
puentes y a la orilla D llegan 3 puentes, por tanto, según las conclusionesanteriores, el problema no tiene solución.
Ejemplos:
Estos dibujos pueden hacerse de un solo trazo:
Estos no pueden hacerse en las condiciones exigidas:
Este estudio de Euler dio origen ala teoría de los grafos, que se emplean en el
estudio de los circuitos eléctricos, en problemas de transporte, programación con
ordenador, etc.
La Teoría de Grafos juega un papel importante enla fundamentación
matemática de las Ciencias de la Computación. Los grafos constituyen una
herramienta básica para modelar fenómenos discretos y son fundamentales para la
comprensión de las...