Teoría de grafos(graficas) y Relaciones
GRAFOS
GRAFO DIRIGIDO
CONCEPTO
Un grafo dirigido conocido también como dígrafo consta de un conjunto de vértices y aristas donde cada arista se asocia de forma unidireccional a través de una flecha con otro.
Las aristas dependiendo de su salida o ingreso reciben la calificación de entrante o saliente, la condición común, es que siempre tienen un destino hacia un nodo.
GRAFO NO DIRIGIDO
CONCEPTO
Los grafos no dirigidos son aquellos que constan un conjunto de vértices que están conectados a un conjunto de aristas de forma no direccional.
Esto significa que una arista puede indistintamente recorrerse desde cualquiera de sus puntos y en cualquier dirección.
GRAFOS ETIQUETADOS
CONCEPTO
Esta clasificación es denominada como grafos etiquetados o grafos dirigidos con pesos. Este tipo de grafos concentran aristas que pueden poseer información adicional donde podemos reflejar nombres, costos, valores u otros datos.
Estos grafos también son denominados como redes de actividad y el número asociado al arco, se le denomina factor de peso. Este grafo es el que más comúnmente utilizamos para representar situaciones de la vida real.
VÍDEO SUGERIDO: S2.2- Caminos, cadenas y ciclos | | UPV
SEGUNDO VÍDEO SUGERIDO:Grafos etiquetados
GRÁFICAS
CONCEPTO
Muchas situaciones de la vida real pueden ser esquematizadas por medio de diagramas construidos por puntos (vértices o nodos) y líneas (aristas o arcos) que conectan algunos pares de vértices, aunque eventualmente alguna línea puede unir un vértice consigo mismo.
Estos esquemas, que facilitan la comprensión del problema a resolver, aparecen frecuentemente en disciplinas dispares y bajo nombres diversos, tales como: redes (en ingeniería y economía), sociogramas (en psicología), organigramas (en economía y planificación), etc.
CAMINOS
Si se piensa a los vértices de una gráfica como ciudades y a las aristas como carreteras, un camino corresponde a un viaje que comienza en cierta ciudad, pasa por varias ciudades y termina en alguna ciudad.
TEOREMA
Sea 𝐺 una gráfica y sean 𝑢, 𝑣 ∈ 𝑉(𝐺), entonces existe un 𝑢𝑣-camino en 𝐺 si y sólo si existe una 𝑢𝑣-trayectoria en 𝐺.
CONEXIDAD
Cadena: toda sucesion finita alterna de vertices y aristas( resp. Arcos).
Cadena cerrada: a toda cadena en la que los vertices inicial y final coinciden.
Camino: a toda cadena en la que no se repiten ni vertices, ni aristas(resp. Arcos).
Ciclo: cadena en la que no se repite ninguna arista (resp. Arcos)., ni vertice a escepcion del inicial y el final.
Longitud de la cadena: Numero de aristas (resp. Arcos) que la conforman.
Longitud de la cadena, Longitud de la cadena, Longitud del camino y Longitud del ciclo: son los espacios (uecos) entre los vertices como lo explican en el siguiente video:
CLASIFICACIÓN
Un camino 𝑊 que no repite aristas se denomina paseo (camino sencillo).
Un camino 𝑊 que no repite vértices se llama trayectoria (camino elemental).
Un camino cerrado 𝑊 en el que todos los vértices son diferentes excepto el vértice inicial se llama un ciclo.
COROLARIO
Una gráfica 𝐺 es conexa si y sólo si para cualquier par de vértices 𝑢, 𝑣 ∈ 𝑉(𝐺) existe una 𝑢𝑣-trayectoria en 𝐺.
VÍDEO SUGERIDO: Grafo - camino, cadena, ciclo
UN POCO DE HISTORIA
- en 1736 .El trabajo de Leonhard Euler, , sobre el problema de los puentes de Königsberg
- 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:
- Este problema permaneció abierto mucho tiempo, hasta que en los años 70 fue resuelto por Kenneth Appel y Wolfgang Haken.
- 1857. Arthur Cayley resolvió el problema de la enumeración de isómeros (ej: alcohol etílico) por medio de grafos.
- 1878. El término grafo es acuñado por Silvester en un artículo publicado en Nature. Donde traza una analogía entre invariantes cuánticos y co-variantes.
- 1936. Se publica el primer libro de Teoría de Grafos, escrito por el matemático judío húngaro Dénes König.
- 1953. Se introduce por primera vez el cálculo de APSP por Shimbel. Quien descubrió que puede ser resuelto por una serie lineal de multiplicaciones en matrices.
- 1956.Se describe el primer modelo para resolver problema del camino más corto, el cual es uno de los problemas más populares de esta ciencia.
- 1959. Aparece el algoritmo Dijkstra.
- 1962. Se describe el algoritmo de Floyd-Warshall para el problema de APSP.
- 1967. El primer algoritmo para cálculos de APSP en grafos dinámicos se publica por Peter S. Loubal con una complejidad algorítmica de O(n^2).
- 1969. Se publica el libro de Frank Harary.
- 1977 – 1981. Se publica el algoritmo de Johnson el cual calcula el APSP para grafos ponderados con arcos negativos, es muy parecido al algoritmo de Floyd-Warshall.
- 1984. Se implementa el algoritmo de Dijkstra con una cola de prioridad implementada por un montículo de Fibonacci.
- 1991. Ausiello continuó con el análisis de grafos dinámicos con un algoritmo para grafos enteros de arco no mayores a un valor constante C.
- 1996. El famoso algoritmo de Ramalingam y Reps fue publicado, también para grafos dinámicos y posee una complejidad de O(m n).
- 1999. El algoritmo de Thorup sale a la luz con un algoritmo de complejidad O(m n) para el cálculo de APSP en grafos no dirigidos.
- 2004. El italiano científico de la computación Giuseppe F. Italiano publica un algoritmo para grafos dinámicos con una complejidad algorítmica de O(n^2 \log^3 n).
- 2014. Se propone un nuevo algoritmo para grafos dirigidos por Khopkar con una complejidad algorítmica de O(n^2). Resulta uno de los algoritmos más usados.
- 2017. Slobbe propone un algoritmo más eficiente que los anteriores para grafos dinámicos en escenarios de peor caso.
VÍDEO SUGERIDO:Aplicaciones de la Teoría de Grafos a la Vida Real (I) | UPValenciaX on edX | Course About Video
APLICACIONES EN LA ACTUALIDAD
- Logística
- Traductores de idiomas
- Diseño de redes
- Optimización en investigación operativa
- Desarrollo de sensores en robótica
- Genética
- Estudio de las redes sociales
- Química
- Biología molecular
- Ciencias de la computación
- El modelo matemático para manipular un robot
- El área didáctica y lúdica
- También se han modelado laberintos y en los últimos años se ha creado una relación estrecha entre la Teoría de gráficas y la papiroflexia..
VÍDEO SUGERIDO:Aplicaciones de la Teoría de Grafos a la Vida Real (I) | UPValenciaX on edX | Course About Video
ÁRBOLES
CONCEPTO
- Un grafo no dirigido G se dice que es un árbol si es conexo y aciclico.
- Existe un tipo importante de gráficas que gracias a su simplicidad tienen muchas aplicaciones –en la práctica y dentro de la Teoría de gráficas misma-, las cuales reciben el nombre de árboles.
- Un árbol es una gráfica conexa que no contiene ciclos.
CARACTERIZACIÓN
Sea g un grafo no dirigido G=(V,E) con IVI>1.
a) G es un árbol
b) G es simple y existe un único camino entre cada par de vértices
c) G es aciclico y card(E) ”Numero de aristas”=card(V) ”Numero de vértices” =-1
d) G es conexo y card(E) ”Numero de aristas”=card(V) ”Numero de vértices” =-1
ÁRBOLES DIRIGIDOS CON RAIZ (ARBORESCENCIAS)
CONCEPTO
Sea G un grafo dirigido G =(V,E)
Se dice que G es unn arbol con raiz V_0 si es un grafo aciclico tal que todos los vertices a excepción de V_0tienen grado de tiene uno y V_0 grado de entrada ceroentrada
PROPIEDADES
- Sea G= (V,E) un grafo dirigido con raíz V_0
- Sea G=(V,E) grafo subyacente de G
Se verifica que:
1.- existe un camino y solo uno desde V_0 a cada uno de los demás vértices.
2. - IEI=IVI-1
3. - G es aciclico
4. – G es conexo
5. – G es árbol
RELACIONES
- Cuando una relación es al mismo tiempo reflexiva, simétrica y transitiva se dice que es una relación de equivalencia.
- Cuando una relación es simultáneamente reflexiva, anti-simétrica y transitiva se le llama un orden parcial.
EJEMPLOS DE RELACIONES
La relación de adyacencia entre los vértices de una gráfica 𝐺 definida por las aristas en 𝐴(𝐺) es una relación simétrica y no reflexiva.
La relación “estar conectado con” sobre el conjunto de vértices de una gráfica 𝐺 es una relación de equivalencia.
En un árbol 𝑇 con raíz 𝑟, la relación 𝑅 definida como (𝑢, 𝑣) ∈ 𝑅 si 𝑢 ∈ 𝑟𝑇𝑣 es un orden parcial.
VIDEO SUGERIDO:Árboles dirigidos con raíz | 13/42 | UPV
ÁRBOL GENERADOR DE MÍNIMO COSTE - ÁRBOL DE PESO MÍNIMO
- Sea G un grafo no dirigido conexo ponderado G=(V,E).
- Se llama árbol generador de G a todo subgrafo generador que sea conexo y aciclico.
- Se llama árbol generador de mínimo coste de G a todo árbol generador de G cuyo coste sea menor o igual que el de cualquier otro árbol generador de G.
- El árbol generador de mínimo coste de un grafo dado G no tiene por que ser único.
ALGORITMO DE KRUSKAL
- Sea G no dirigido ponderado
- El algoritmo de kruskal proporciona un árbol generador de mínimo coste
- Si los pesos son distintos 2 a 2 el árbol generador de mínimo coste es único.
CUESTIÓN
- Si los pesos son distintos el árbol generador es único.
- El que los pesos se repitan no obliga a que existan arboles generadores del mínimo coste distintos(puede ser único o puede no ser único).
VÍDEO SUGERIDO:Árboles | 12/42 | UPV
VÍDEO SUGERIDO: Árboles | 12/42 | UPV