Please enable JavaScript.
Coggle requires JavaScript to display documents.
LA TEORIA DE GRAFOS - Coggle Diagram
LA TEORIA DE GRAFOS
HISTORIA
LOS PUENTES DE KONIGSBERG En 1736 Leonhard Euler hace una publicacion com parte de los principios de la topologia, en esta ciudad tenia 7 puentes que conectaba a la isla (ahora kaliningrado) en prusia era idear una caminata por la ciudad cruzando cada puente solo una vez Euler demostro que no era posible. 
LEYES DE KIRSHHOFF En 1847 se publica las leyes de kirshhoff para analisis de redes electricas la primera aplicacion a la teoria de grafos.
LOS CUATRO COLORES Planteado por Francis Guthrie en 1852 consistia en colorear un mapa con 4 colores diferentes, donde dos regiones vecinas tenian que tener colores diferentes entre si.
ENUMERACION DE ISOMEROS 1857 por medio de la teoria de grafos se resuelve la enumeracion de isomeros por Arthur Cayley
TERMINO GRAFO 1878 Silvester acuña el termino grafo, trazando una analogia entre invariantes cuanticas y co-variantes.
PRIMER LIBRO 1936 se hace la publicacion del primero libro escrito por ene Konig judio hungaro APSP(All Pair Shortest Path) en 1953 se hace el calculo por primera vez por medio de una serie lineal de multiplicaciones de matrices gracias a Shimbel.
ALGORITMO SSSP En 1956 publica su algoritmo para calcular el "Camino mas corto de una sola fuente' este mismo año colaboro con Bellmor Ford para calcular grafos con ponderacion negativa igual SSSP.
DIJKSTRA En 1959 aparece el algoritmo Dijkstra muy popular usado en el encamininamiento de paquetes de routers en geografia, rutas de trafico etc.
FLOYD-WARSHALL En 1962 se describe este algoritmo que presenta la solucion de una matriz de distancias, programacion dinamica (On^3) en 1969 Peter's Loubal publica un algoritmo para calculo de grafos dinamicos On^2.
ALGORITMO-JOHNSON Este algoritmo resolveria algoritmos ponderados On^2 Log+nm con arcos negativos parecido al de Floyd 4 años despues se publica una vercion de Dijkstra usando monticulos de Fibonacci complejidad O(m Log Logn +L) donde L es el peso maximo entre todos los arcos (Arturo, 2018) Fredman & Tarjan
-
-
-
-
-
-
GRAFOS EN LA ACTUALIDAD
Hoy en dia e manejan grafos para la resolucion de problemas que van desde las ciencias sociales hasta las naturales
Ciencias Sociales donde los nodos son los actores sociales y sus arista son los vinculos entre ellos lo cual se calcula la importancia o el peso del nodo asi como su direccion e intencidad.
Control de Produccion se proyectan redes de ordenadores, diseño de modulos modernos y proyectar sistemas fisicos, los grafos son usados para la medicion en el caso de enfermedades cerebrales que puede visualizar la topologia cerebral lo que puede describir una red neuronal de forma grafica.
MAPAS CONCEPTUALES
TOPOLOGIA RED DE COMPUTADORES
ISOMEROS
PLANO DE ESTACIONES DE METRO
AUTOPISTAS
QUE ES UN GRAFO los grafos estan representados por un grupo de puntos llamados nodos y se interconectan entre si llamadas aristas un par de ellos conforma un vertice y la suma de todos ellos forman un grafo lo que se llama orden, el concepto de grado corresponde al numero de arcos un bucle es un nodo apuntando asi mismo
CAMINO en un grafo no se repite ninguna arista o vertice en su recorrido
Arbol Binario es un nodo que tiene dos nodos subyacentes y estos mismos tienen ma nodos llamados subarboles que conectan a un nodo raiz, por esta razon no son vacios ya que continen una raiz.
ARBOL BINARIO PESO MINIMO Este se obtiene de un grafo contexto el cual no tiene ciclos el resultado es obtener un arbol de maximo alcance y su peso es minimo es decir la suma de sus aristas es minima