grafos

Matemáticas Discretas
Tc1003
Teoría de Grafos

Teoría de Grafos
OBJETIVOS
Unidad
Tema
Subtema
Objetivos
VIII Teoría de Grafos
7.1 Definiciones
7.2 Trayectorias y circuitos de Euler
7.3 Trayectorias y circuitos de Hamilton
7.4 Árboles
Definir, reconocer un grafo para establecer la solución de un
problema.
Reconocer Camino, Camino cerrado, Recorrido, Circuito, Camino
simple yCiclo.
Definir, distinguir un circuito de Euler y una trayectoria de Euler
Definir, distinguir un circuito de Euler y una trayectoria de
Hamilton
Definir y distinguir un árbol, árbol enraizado árboles de
expansión, notación polaca.

Introducción
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 brazosestaban construidos siete puentes y para los habitantes 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 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 estabanrepresentados 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 del papel y sin pasar dos veces por el mismo sitio.

Ngj/v2008

7.1 Teoría de grafos

204

Matemáticas Discretas
Tc1003
Teoría de Grafos
Llegó a la siguienteconclusió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 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.
(Impar es un vértice si de é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 conclusiones
anteriores, 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 a la teoría de los grafos, que se emplean en el
estudio de los circuitoseléctricos, en problemas de transporte, programación con
ordenador, etc.

Ngj/v2008

7.1 Teoría de grafos

205

Matemáticas Discretas
Tc1003
Teoría de Grafos

7.1 Teoría de grafos
La Teoría de Grafos juega un papel importante en la fundamentación
matemática de las Ciencias de la Computación. Los grafos constituyen una
herramienta básica para modelar fenómenos discretos y sonfundamentales para la
comprensión de las estructuras de datos y el análisis de algoritmos.
En matemáticas y ciencias de la computación, la teoría de grafos estudia
las propiedades de los grafos, que son colecciones de objetos llamados vértices (o
nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener
orientación (dirección asignada). Típicamente, un grafo está diseñado por una seriede puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de
Königsberg es considerado como uno de los primeros resultados de la teoría de
grafos. También se considera uno de los primeros resultados topológicos en
geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda
relación entre lateoría de grafos y la topología.
En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el
voltaje y la corriente en los circuitos eléctricos.
En 1852 Francis Guthrie planteó el problema de los cuatro colores que
plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa
de países de tal forma que dos países vecinos nunca tengan el mismo color. Este...