miércoles, 5 de diciembre de 2018

Teoría de Grafos


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 1847Gustav 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 1857Arthur 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, también llamada teoría de gráficas, es una rama de las matemáticas y las ciencias de la computación que estudia las propiedades de los grafos. Los grafos no deben ser confundidos con las gráficas, que es un término muy amplio. Formalmente, un grafo es una pareja ordenada en la que V es un conjunto no vacío de vértices y {\displaystyle E}E es un conjunto de aristas.  Donde {\displaystyle E}E consta de pares no ordenados de vértices, tales como {x,y}{\displaystyle \in E} € E entonces se dice que x y y son adyacentes; y en el grafo se representa mediante una línea no orientada que una  dichos vértices. Si el grafo es dirigido se le llama dígrafo, se denota D, y entonces el par (x,y) es un par ordenado, esto se representa con una flecha que va de (x a {\displaystyle y} y) y se dice que (x, y) E.

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 {\displaystyle n^{2}}N2, donde {\displaystyle n}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 {\displaystyle m_{x,y}}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 simpleslas 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.