Grafos.
Nociones básicas
Introducción
I Definiciones y ejemplos I Tipos
de grafos I Representación
de grafos I Representación
de grafos en el ordenador I Conectividad
1.1. Introducción
El
problema es simplemente encontrar un trayecto, alrededor de una serie
de puentes, que cruce solamente una vez cada uno de ellos. El mapa de
abajo muestra la disposición de siete puentes y dos islas en la ciudad
de Königsberg.
En
1736, el matemático suizo radicado en San Petersburgo Leonhard
Euler publicó "Solutio Problematis ad Geometriam Situs
Pertinentis", un artículo en el que resolvía el problema en el caso
general. Este trabajo es considerado como el nacimiento de la Teoría de Grafos, utilizada hoy en día
en múltiples aplicaciones
La
idea de Euler fue considerar los cuatro lugares terrestres, que se deseaban
comunicar (hay 4 de ellos), como puntos de destino y, a los famosos puentes,
como trayectorias entre esos puntos. En consecuencia, el mapa de Königsberg
–en esencia matemática– puede ser entonces reducido al siguiente diagrama,
que es un ejemplo de lo que se suele llamar un grafo:
Un
grafo, es una figura cuyas líneas o curvas (llamadas aristas), conectan
puntos o vértices. En consecuencia, la trayectoria de los puentes de Königsberg
puede ser reformulada como un grafo, en el cual las aristas son recorridas
una sola vez. En la siguiente figura, los puntos rojos representan las
áreas terrestres de Königsberg y las curvas negras los puentes. Este problema,
por supuesto que puede ser resuelto mediante un estudio exhaustivo de
todas las posibles trayectorias. Pero las matemáticas se interesan en
generalizar el problema y buscar una solución sencilla y válida para todos
los posibles mapas de ciudades, e incluso objetos más generales.
En
función de la ubicación de cada uno de los vértices y de los puentes que
los conectan, Euler demostró que no existe solución al problema de la
trayectoria de los puentes de Königsberg.
Por
lo general, usamos grafos en dos situaciones. En primer lugar, ya que
un grafo es un modo muy conveniente y natural de representar las relaciones
entre objetos: representamos objetos por puntos llamados vértices y la
relación entre ellos por líneas llamadas aristas. En muchas situaciones
(problemas) una representación de este tipo puede ser suficiente para
ilustrar un problema.
Por
ejemplo una molécula química puede representarse como un grafo donde los
vértices son los átomos que la componen y las aristas, los enlaces entre
estos átomos.
Otro
ejemplo puede ser la representación de un mapa, en particular, el mapa
de Colombia, donde los vértices representan los departamentos y cada arista
une dos departamentos si estos tienen una frontera común.
En
segundo lugar, tomamos el grafo como el modelo matemático, solucionamos
el problema grafo-teórico apropiado, y luego interpretamos la solución
en términos de problema original.
La
mayor parte de los problemas de la teoría de grafo pueden ser clasificados
en:
1.
Problemas de Existencia
- El problema de los siete puentes de Königsberg: Existe una trayectoria
cerrada que cruce cada uno de los siete puentes exactamente una vez?
- El problema del Caballo de Ajedrez: Existe una
secuencia de los movimientos del caballo tal que visite cada cuadrado
de un tablero de ajedrez exactamente una vez y regresando a la posición
de partida?
- El problema de los Cuatro Colores: Puede colorearse
todo mapa con cuatro colores de modo que los países vecinos tengan colores
diferentes?
- Determinar
si un grafo dado es euleriano y construir un camino euleriano (algoritmo
de Fleury).
3.
Problemas de Enumeración
- Grafos etiquetados.
- Digrafos etiquetados.
-
Árboles etiquetados.
4.
Problemas de Optimización
-
Problema de encontrar el camino mínimo
entre dos vértices en dígrafo pesado.
-
Problema del viajante de comercio
www.astrocosmo.cl/anexos/p-p_konigsberg.htm
www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/graphIntro.htm