grafos

Grafos
Hacia el año 1735 la ciudad de Konigsberg situada en lo que era la Prusia Oriental
(hoy la ciudad se llama Kaliningrado y pertenece a Rusia) estaba dividida en cuatro
zonas determinadas por el río Preel que al cruzar la ciudad se divide formando dos
islas. Las diversas zonas se comunicaban mediante siete puentes tal como se observa
en la figura siguiente.

Imagen 1: Königsberg enlos tiempos de Euler; aparecen señalados (en rojo) los siete puentes.
Fuente: http://www-gap.dcs.st-and.ac.uk/~history/Miscellaneous/Konigsberg.html

Se cuenta que los habitantes realizaban paseos tratando de encontrar una forma de
caminar por la ciudad cruzando cada puente exactamente una vez y regresando al
punto donde habían comenzado. Intente ayudar, junto con compañeros y amigos, a
loshabitantes de esta ciudad a determinar una posible ruta para realizar el paseo con
las condiciones indicadas.

Conceptos clave








Grafo
Vértice
Arista
Grado de un vértice
Grafo Eureliano
Grafo Hamiltoniano
Topología

Objetivos






Conocer el concepto de grafo y su uso en diversas situaciones.
Determinar si un grafo dado es euleriano.
Conocer elconcepto de grafo hamiltoniano y reconocer algunos grafos de este
tipo.
Determinar si dos grafos dados son isomorfos.
Determinar si un grafo es plano.

1

Sinopsis
La teoría de grafos es parte de una rama de las matemáticas conocida como
Topología; esta es una “geometría de posición”. En ella, consideraciones tales como
distancias, ángulos, colinealidad, entre otros, no juegan ningún papel. Loimportante
es la posición relativa entre los diversos puntos y conjuntos.
Los elementos constituyentes de un grafo son sus vértices y aristas. Las relaciones
particulares entre ellos determinan diversas características que hacen de los grafos
herramientas útiles como medio de diversión, de investigación matemática y de
aplicaciones de esta disciplina.
Muchos problemas cotidianos y deaplicación profunda de las matemáticas pueden
resolverse a través de modelos representados mediante grafos.

Topología y grafos: breve reseña histórica
A finales del siglo XVII, el matemático suizo Leibniz intentó enunciar las propiedades
geométricas básicas de las figuras, sin recurrir a magnitudes. Sus ideas no tuvieron
repercusión en las matemáticas; sin embargo, en ellas se encontraba elgermen de lo
que ahora se conoce como Topología.
Se considera que el punto de partida de esta rama de las matemáticas es el famoso
problema de los puentes de Koenigsberg, que está planteado al comienzo de este
tema.
Así, dicho problema, aparentemente banal, reviste una gran importancia en
matemáticas puesto que su solución representó el inicio de una fecunda rama que
tiene numerosas aplicacionesen diferentes áreas del conocimiento. En efecto, el
matemático suizo Leonhard Euler (1707 – 1783), presentó en el año 1735, de un
modo novedoso, la solución al famoso problema.

2

Imagen 2. Leonhar Euler. Nació en Suiza en 1707, murió en
1783. Fuente: http://plus.maths.org/issue42/features/wilson/

La primera publicación relacionada con conceptos topológicos apareció en 1848 y fueescrita por Johann B. Listing (1806-1882) quien fue alumno de Gauss en 1834 y
posteriormente profesor de física en Gotinga. Aunque el propio Gauss no publicó nada
acerca de la Topología, fue una gran influencia en los trabajos de Listing puesto que
estaba a favor del estudio de las propiedades básicas de las figuras geométr icas.
El primero que formuló de manera apropiada la naturaleza de lasideas topológicas fue
Möbius, ayudante de Gauss en 1813. Otros grandes matemáticos ligados con el
desarrollo de la Topología son Riemann, Klein y Poincaré. Este último publicó en 1905
una obra titulada Análisis situs, que constituye el primer trabajo sistemático y general
en Topología que contenía los aspectos, definiciones y teoremas básicos de lo que se
conoce como Topología combinatoria....