Teoría de grafos(graficas) y Relaciones
ÁRBOLES
VÍDEO SUGERIDO: Árboles | 12/42 | UPV
ÁRBOL GENERADOR DE MÍNIMO COSTE - ÁRBOL DE PESO MÍNIMO
VÍDEO SUGERIDO:Árboles | 12/42 | UPV
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).
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.
- 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.
ÁRBOLES DIRIGIDOS CON RAIZ (ARBORESCENCIAS)
VIDEO SUGERIDO:Árboles dirigidos con raíz | 13/42 | UPV
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.
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.
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
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
CARACTERIZACIÓN
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
Sea g un grafo no dirigido G=(V,E) con IVI>1.
- 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.
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..
UN POCO DE HISTORIA
VÍDEO SUGERIDO:Aplicaciones de la Teoría de Grafos a la Vida Real (I) | UPValenciaX on edX | Course About Video
- 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.
Subtopic
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.
VÍDEO SUGERIDO: Grafo - camino, cadena, ciclo
COROLARIO
Una gráfica 𝐺 es conexa si y sólo si para cualquier par de vértices 𝑢, 𝑣 ∈ 𝑉(𝐺) existe una 𝑢𝑣-trayectoria en 𝐺.
CLASIFICACIÓN
Un camino cerrado 𝑊 en el que todos los vértices son diferentes excepto el vértice inicial se llama un ciclo.
Un camino 𝑊 que no repite vértices se llama trayectoria (camino elemental).
Un camino 𝑊 que no repite aristas se denomina paseo (camino sencillo).
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:
TEOREMA
Sea 𝐺 una gráfica y sean 𝑢, 𝑣 ∈ 𝑉(𝐺), entonces existe un 𝑢𝑣-camino en 𝐺 si y sólo si existe una 𝑢𝑣-trayectoria en 𝐺.
GRÁFICAS
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.
GRAFOS
SEGUNDO VÍDEO SUGERIDO:Grafos etiquetados
VÍDEO SUGERIDO: S2.2- Caminos, cadenas y ciclos | | UPV
GRAFOS ETIQUETADOS
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.
GRAFO NO DIRIGIDO
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.
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.
