Mapa mental

TEORÍA DE LOS GRAFOS

César García Espanhol

Conteúdo do mapa

Inicio
- Es una ciencia matemática que estudia los Grafos. Estas son estructuras matemáticas para modelar relaciones por pares entre objetos. Un grafo se compone de vértices, nodos o puntos que están conectados por aristas, arcos, bordes o líneas. Existen varios tipos de grafos y muchos problemas propuestos para esta ciencia.
  - 1973
    - El problema de los Siete Puentes de Königsberg es considerado como el primer artículo de la historia en la teoría de grafo, publicado por Leonhard Euler. Sí, el mismo de los algoritmos. Esta también hace parte de los principios de la Topología. El artículo puede encontrarse originalmente en latín con este enlace.
  - 1857
    - Arthur Cayley resolvió el problema de la enumeración de isómeros (ej: alcohol etílico) por medio de grafos. Para ello representó cada compuesto, en este caso hidrocarburos saturados CnH2n+2, mediante un grafo árbol donde los nodos representan átomos y los arcos la existencia de enlaces químicos
  - 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. APSP son las siglas en inglés de All pairs Shortest Path, traduce “Caminos más cortos entre todos los pares “.
  - 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 . Además, se habla por primera vez de este tipo de comportamiento en los grafos.
  - 1996
    - El famoso algoritmo de Ramalingam y Reps fue publicado, también para grafos dinámicos y posee una complejidad de .
  - 2017
    - Slobbe propone un algoritmo más eficiente que los anteriores para grafos dinámicos en escenarios de peor caso. Los resultados de sus pruebas comparan su algoritmo con métodos como los de Khopkar y Ramlingam y resulta ser mucho más rápido. Su complejidad también es de . (Arturo 2020)
      - Herramientas para la manipulación de Grafos
        Gephy
        Graphviz
        SigmaJs
        Cytoscape
        Jung
        Igraph
        Linkurious
        TIPOS GRAFOS
        Grafo Nulo
        también llamado grafo vacío, es un grafo en el que no hay aristas entre ninguno de sus vértices.
        Grafo Conectado
        un grafo en el que hay una ruta de aristas entre cada par de vértices en el grafo. El grafo de Juan es un grafo conectado, ya que hay una manera de llegar desde cada ciudad del mapa a cualquier otra ciudad.
        Grafo Desconectado
        un grafo en el que la ruta de las aristas no siempre conecta todos los vértices.
        Grafo Bipartido
        un grafo que se puede dividir en dos conjuntos de vértices de modo que las aristas solo vayan entre conjuntos, no dentro de ellos.
        Grafo Ponderado
        un grafo en el que se asignan pesos o valores numéricos a cada una de las aristas. El grafo de Juan es también un grafo ponderado, donde las distancias entre las ciudades son los pesos de los bordes.
        Grafo Dirigido
        un gráfico en el que las aristas están dirigidas por flechas, lo que indica que la relación, representada por la arista, solo se aplica de un vértice al otro, pero no al revés. En otras palabras, si una arista dirigida tiene una flecha de A a B, A está relacionada con B, pero B no está relacionada con A.
        Grafo no Dirigido
        un grafo cuyas aristas no están dirigidas. El grafo de Juan es un grafo no dirigido, porque las rutas entre ciudades van en ambos sentidos.
        Grafo simple
        un grafo no dirigido en el que hay como máximo una arista entre cada par de vértices, y no hay bucles, que es una arista desde un vértice hacia sí mismo.
        Multi-Grafo
        Un grafo en el que hay múltiples aristas entre cualquier par de vértices o hay aristas desde un vértice hacia sí mismo, también llamado bucle.
        Grafo Plano
        un grafo que se puede dibujar para que todas las aristas del grafo no se crucen entre sí. (Cervantinos. 2018)
        MÉTODOS
        CAMINOS
        En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lo tanto, cada vértice tiene dos aristas incidentes.
        Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su recorrido.
        Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último. La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.
        Camino euleriano Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es dual a la de camino hamiltoniano.
        Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final.
        Ciclo euleriano Un ciclo euleriano en un grafo es un ciclo que usa cada arista una y sólo una vez.
        Un ciclo hamiltoniano pasa por todos los vértices exactamente una vez, regresando al punto de partida. (Pablo 2018)
        ARBOLES
        Por últimos tenemos que hablaros de los diagramas en árbol que son las formas más poderosas y efectivas de representar un grafo. Dentro de ellos nos podemos encontrar árboles de búsqueda binarios de los que es importante saber cómo funcionan y cómo hacen que las visualizaciones sean más interpretables. Pero antes de todo eso, hemos de tomarnos un momento para comprender qué son los árboles en este contexto.
        Sin Ciclo
        Los elementos de un árbol se llaman nodos. (A, B, C, D y E) son los nodos en el árbol anterior. El primer nodo (o el nodo superior) de un árbol se conoce como nodo raíz, mientras que el último nodo (nodo C, D y E en el ejemplo anterior) se conoce como nodo hoja. Todos los nodos restantes se conocen como nodos secundarios (nodo B en nuestro caso).
        ARBOL DE PESO MINIMO
        Un árbol de peso mínimo es aquel que obtenemos en un grafo conexo y sin ciclos. Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es mínima.
        Pasos: Se inicia en cualquier nodo. Seleccionar la arista de menor costo adyacente al nodo. Se busca la arista de menor costo de los nodos ya analizados adyacente que no genere ciclos. Kruskal (Glotón): Pasos: Ordenar aristas de menor peso a mayor peso Se selecciona la arista de menor peso sin generar ciclos. Se detiene cuando se tengan n-1 aristas. (Optimización 2020)