Historia
Los 7 puentes del río Pregel en Königsberg.
El origen de la teoría de grafos se remonta
al siglo XVIII con el problema de los
puentes de Königsberg, el cual consistía en encontrar un camino que
recorriera los siete puentes del río Pregel en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes
pasando una sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio
problematis ad geometriam situs pertinentis3 (La solución de un problema relativo a la geometría de la
posición) en 1736, es considerado el primer resultado 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 la teoría de grafos y la topología.
Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el
análisis de redes eléctricas publicando sus leyes de los circuitos para
calcular el voltaje y la corriente en los circuitos eléctricos, conocidas
como leyes de Kirchhoff,
considerado la primera aplicación de la teoría de grafos a un problema de ingeniería.
En 1852 Francis Guthrie planteó el problema de los cuatro colores el
cual afirma que 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 problema, que no fue resuelto hasta un siglo después
por Kenneth Appel y Wolfgang Haken en 1976,
puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de
resolverlo, los matemáticos definieron términos y conceptos teóricos
fundamentales de los grafos.
En 1857, Arthur Cayley estudió y resolvió el problema de
enumeración de los isómeros, compuestos químicos con idéntica
composición (fórmula) pero
diferente estructura molecular. Para
ello representó cada compuesto, en este
caso hidrocarburos saturados CnH2n+2,
mediante un grafo árbol donde los
vértices representan átomos y las aristas la existencia
de enlaces químicos.
El término «grafo», proviene de la
expresión graphic notation («notación gráfica») usada por primera vez
por Edward Frankland4 y posteriormente adoptada por Alexander Crum
Brown en 1884, y hacía referencia a la representación
gráfica de los enlaces entre los átomos de una molécula.
El primer libro sobre teoría de grafos fue
escrito por Dénes Kőnig y publicado en 1936.
Teoría de grafos programación
La teoría de grafos tiene sus fundamentos en las matemáticas discretas y
de las matemáticas aplicadas. Esta teoría que requiere de diferentes conceptos
de diversas áreas como combinatoria, álgebra, probabilidad, geometría de
polígonos, aritmética y topología. Actualmente ha tenido mayor influencia en el
campo de la informática, las ciencias de la computación y telecomunicaciones.
Debido a la gran cantidad de aplicaciones en la optimización de recorridos,
procesos, flujos, algoritmos de búsquedas, entre otros, se generó toda una
nueva teoría que se conoce como análisis de redes.
Composición de un
grafo
·
Aristas: Son las líneas con las que se unen los vértices de un
grafo.
·
Aristas adyacentes: 2 aristas son adyacentes si convergen en el mismo
vértice.
·
Aristas paralelas: Son dos aristas conjuntas si el vértice inicial y final
son el mismo.
·
Arista cíclicas: Es la arista que parte de un vértice para entrar en sí
mismo.
·
Cruce: Son 2 aristas que cruzan en un mismo punto.
·
Vértices: Los vértices son los elementos que forman un grafo.
Cada uno lleva asociada una valencia característica según la situación, que se
corresponde con la cantidad de aristas que confluyen en dicho vértice.
·
Camino: Se denomina camino de un grafo a un conjunto de
vértices interconectados por aristas. Dos vértices están conectados si hay un
camino entre ellos.
Representación de los grafos
Para
representar un grafo podemos usar varios tipos de estructuras:
§ Estructura de lista:
como pueden ser la lista de adyacencia donde cada vértice
tiene una lista de vértices los cuales son adyacentes a él.
ü
Lista de incidencia - Las aristas son representadas
con un vector de pares (ordenados, si el grafo es dirigido), donde cada par
representa una de las aristas.
ü Lista
de adyacencia - Cada vértice tiene una lista de vértices los cuales son
adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A
existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más
rápidas, al costo de almacenamiento extra.
ü Lista
de grados - También llamada secuencia de grados o sucesión gráfica de un grafo
no-dirigido es una secuencia de números, que corresponde a los grados de los
vértices del grafo.
§ Estructura de matriz:
como pueden ser las matrices de adyacencia donde el grafo está
representado por una matriz cuadrada M de tamaño n cuadrado, donde n es el
número de vértices.
ü Matriz de adyacencia -
El grafo está representado por una matriz cuadrada M de tamaño N2,
donde N es
el número de vértices. Si hay una arista entre un vértice x y un vértice y,
entonces el elemento Mx,y es 1, de lo contrario, es 0.
ü Matriz de incidencia -
El grafo está representado por una matriz de A (aristas)
por V (vértices), donde [vértice, arista] contiene la información de la arista
(1 - conectado, 0 - no conectado)
Si
nos fijamos, para la construcción de estructuras complejas tendremos
que utilizar otras estructuras más simples, las listas,
esto no siempre será así, ya que por ejemplo, con las estructuras jerárquicas
(en concreto algunos tipos de árboles como los binarios de búsqueda) se
utilizarán referencias o punteros. Las matrices son también estructuras de
datos más complejas que se forman mediante listas de elementos. Nosotros utilizaremos
las matrices de adayacencia, ya que estas matrices son especialmente útiles
en el caso de grafos densos. Los grafos densos son aquellos grafos que tienen
varias aristas por cada nodo.
Conceptos básicos
§ Grado
de un nodo: Número de arcos u aristas conectados al nodo.
§ Grado
de Entrada (gE) de un nodo: Número de arcos o aristas que tienen al nodo como
destino.
§ Grado
de Salida (gS) de un nodo: Número de arcos o aristas que tienen al nodo como
origen.
§ Nodo
fuente: Si cumple que GradoSalida > 0 y GradoEntrada = 0
§ Nodo
sumidero: Si cumple que GradoSalida = 0 y GradoEntrada > 0.
§ Nodo
aislado: Si cumple que GradoSalida = 0 y GradoEntrada = 0.
§ Capacidad
de un grafo: n = número de nodos de un grafo.
§ Camino
Simple entre dos nodos Vi, Vj (Vi ≠ Vj): Es aquel camino en el que no se
repite ningún nodo.
§ Excentricidad:
La excentricidad de un nodo V es el máximo de los costes de todos los caminos
de coste mínimo con destino V.
§ Nodo
centro de un grafo: será aquel nodo de mínima excentricidad.
Estos
conceptos serán aplicables al grafo que nosotros implementemos mediante los
métodos. Cada uno de estos conceptos los representaremos mediante un
método que nos permitirá añadirle funcionalidad a nuestro grafo.
Tipos de grafos
§ Grafo simple
o simplemente grafo es aquel que acepta una sola arista uniendo dos vértices
cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única
que une dos vértices específicos. Es la definición estándar de un grafo.
§ Multígrafo
o pseudografo son grafos que aceptan más de una arista entre dos vértices.
Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples
son una subclase de esta categoría de grafos. También se les llama grafos
no-dirigido.
§ Grafo dirigido
Son grafos en los cuales se ha añadido una orientación a las aristas,
representada gráficamente por una flecha
§ Grafo etiquetado Grafos
en los cuales se ha añadido un peso a las aristas (número entero generalmente)
o un etiquetado a los vértices.
§ Grafo aleatorio
Grafo cuyas aristas están asociadas a una probabilidad.
§ Hipergrafo Grafos
en los cuales las aristas tienen más de dos extremos, es decir, las aristas son
incidentes a 3 o más vértices.
§ Grafo infinito
Grafos con conjunto de vértices y aristas de cardinal infinito.
- Grafo plano: Los grafos planos son
aquellos cuyos vértices y aristas pueden ser representados sin ninguna
intersección entre ellos. Podemos establecer que un grafo es plano gracias
al Teorema de Kuratowski.
- Grafo regular: Un grafo es regular
cuando todos sus vértices tienen el mismo grado de valencia.
Problemas de teoría de grafos
Subgrafos, subgrafos inducidos y menores
Un problema común, denominado problema de
isomorfismo de subgrafos, es encontrar un grafo fijo como subgrafo
de un grafo dado. Una razón para estar interesado en esta cuestión es que
muchas propiedades de grafos son heredadas de subgrafos, lo que significa que
un grafo tiene una propiedad si y solo si todos sus subgrafos a su vez la
poseen. Desafortunadamente, encontrar subgrafos máximos de un cierto tipo suele
ser un problema NP-completo. Por ejemplo:
Encontrar el subgrafo completo más grande se
llama problema de la clique.
Un problema similar es encontrar un subgrafo inducido en un grafo dado. De nuevo, algunas
propiedades importantes son heredadas con respecto a subgrafos inducidos, lo
que significa que un grafo tiene una propiedad si y solo si todos los subgrafos
inducidos la tienen. Encontrar subgrafos inducidos máximos de un determinado
tipo es, de nuevo, un problema NP-completo. Como ejemplo:
Encontrar el subgrafo inducido más grande sin
bordes o conjunto independiente se
denomina problema del
conjunto independiente.
Otro nuevo problema es el problema del menor
contenido, que es encontrar un grafo fijo como menor de un grafo dado. Un menor
o subcontración de un grafo es cualquier grafo obtenido tomando un subgrafo y
contrayendo algunos bordes. Muchas propiedades de grafos son heredadas de
menores, lo que significa que un grafo la tiene solo si todos sus menores la
tienen también. Por ejemplo, el teorema de Wagner estipula que:
Un grafo es plano si contiene como menor ni
el grafo bipartito completo ni
el grafo completo.
Un problema de las mismas características es
el problema de la subdivisión del contenido. Una subdivisión o homeomorfismo de un grafo es cualquier grafo obtenido
subdividiendo algunos bordes. La subdivisión del contenido está relacionada con
las propiedades de los grafos tales como la "planeza". Por ejemplo,
el teorema de Kuratowski establece
que:
Un grafo es plano si contiene una subdivisión
ni el grafo bipartito ni el grafo completo.
Otro problema en la subdivisión de contenido
es la conjetura de Kelmans-Seymour:
Cada grafo de cinco vértices conectados que
no es plano contiene una subdivisión del grafo completo de cinco vértices.
Otros problemas de clases tienen que ver con
el alcance para la cual varias especies y generalizaciones de grafos están
determinadas por sus subgrafos de puntos eliminados. Por ejemplo, la conjetura
de la reconstrucción.
Ciclos
y caminos hamiltonianos
Un ciclo es una sucesión de aristas
adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa
al punto inicial. Un ciclo hamiltoniano tiene además que recorrer
todos los vértices exactamente una vez (excepto el vértice del que parte y al
cual llega).
Por ejemplo, en un museo grande, lo idóneo
sería recorrer todas las salas una sola vez, esto es buscar un ciclo
hamiltoniano en el grafo que representa el museo (los vértices son las salas, y
las aristas los corredores o puertas entre ellas).
Se habla también de Camino hamiltoniano si
no se impone regresar al punto de partida, como en un museo con una única
puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de
un tablero de ajedrez sin pasar dos veces por la misma: es un camino
hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
Hoy en día, no se conocen métodos generales
para hallar un ciclo hamiltoniano en tiempo polinómico, siendo
la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos
excesivamente costosos. Existen, sin embargo, métodos para descartar la
existencia de ciclos o caminos hamiltonianos en grafos pequeños.
El problema de determinar la existencia de
ciclos hamiltonianos, entra en el conjunto de los NP-completos.
