# data[].attributes.attachment_caption
Los 7 puentes del río Pregel en Königsberg

# data[].attributes.headline
El origen de la teoría de grafos se remonta al siglo XVlll 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 (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.

# data[].attributes.subject
El origen de la teoría de grafos se remonta al siglo XVlll 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 (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.

# data[].attributes.headline
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.

# data[].attributes.subject
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.

# data[].attributes.body
Mapa coloreado con 4 colores.

# data[].attributes.headline
Este problema famoso relativo a los grafos trata acerca de la cantidad de colores que son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color. Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. El mapa siguiente muestra que tres colores no bastan: si se empieza por el país central (a) y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de (a) alternan dos colores. Llegando al país ℎ se tiene que introducir un cuarto color. Lo mismo sucede en (i) si se emplea el mismo método. Sin embargo,si el mapa tiene forma de toroide, el teorema afirma que con cuatro colores siempre es posible realizar la coloración con las características requeridas.

# data[].attributes.subject
Este problema famoso relativo a los grafos trata acerca de la cantidad de colores que son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color. Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. El mapa siguiente muestra que tres colores no bastan: si se empieza por el país central (a) y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de (a) alternan dos colores. Llegando al país ℎ se tiene que introducir un cuarto color. Lo mismo sucede en (i) si se emplea el mismo método. Sin embargo,si el mapa tiene forma de toroide, el teorema afirma que con cuatro colores siempre es posible realizar la coloración con las características requeridas.

# data[].attributes.body
Grafo dual asociado al mapa con una 4
vértice coloración.

# data[].attributes.body
Son las líneas que unen los vértices de un grafo.

# data[].attributes.body
Dos aristas son adyacentes si convergen en el mismo vértice.

# data[].attributes.body
Dos aristas son paralelas si los vértices iniciales y finales son el mismo vértice

# data[].attributes.body
Aristas que parten de un vértice para entrar en el mismo.

# data[].attributes.body
Es una arista cuyos extremos inciden sobre el mismo vértice.

# data[].attributes.body
Punto donde dos aristas se cruzan.

# data[].attributes.body
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.

# data[].attributes.body
Los vértices son adyacentes si están unidos mediante una arista.

# data[].attributes.body
Es un vértice de grado cero.

# data[].attributes.body
Es un vértice de grado 1.

# data[].attributes.body
Se denomina camino a un conjunto de vértices interconectados por aristas. Dos vértices están conectados si hay un camino entre ellos.

# data[].attributes.body
Una de las aplicaciones más importantes y más usadas de los grafos en los mapas, es para determinar e intentar disminuir el tiempo y camino en recorridos entre sitios distintos.

# data[].attributes.body
Algoritmo De Flody Y Warshall:
El algoritmo de Floyd y Warshall, permite hallar la ruta más corta en grafos dirigidos ponderados.

Obtiene la mejor ruta entre todo par de nodos.

Trabaja con la matriz 'D' inicializada con las distancias directas entre todo par de nodos.

La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de 'i' a 'j' a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red.

Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.

Matriz 'Sn' que entrega el nodo intermedio para llegar desde un nodo 'i' a un nodo 'j' del grafo.

# data[].attributes.attachment_link.authors[].name
Universitat Politècnica de València - UPV

# data[].attributes.attachment_link.title
S3.6- Algoritmo de Floyd-Warshall |  | UPV

# data[].attributes.body
El algoritmo de flujo máximo consiste en interpretar el grafo como una red de flujo de algún material.

Cada arco (vértice) puede ser considerado como un conducto de cierta capacidad.

Este algoritmo es de gran utilidad para reducir las congestiones entre ciertos puntos de partida y destino de una red, por ejemplo sistemas de vías públicas, transporte de petróleo desde la refinería hasta los centros de almacenamiento, distribución de energía eléctrica  a través de los de una red de alumbrado público.

# data[].attributes.headline
Existen dos tipos de grafos básicos los cuales son:

# data[].attributes.subject
Existen dos tipos de grafos básicos los cuales son:

# data[].attributes.body
Grafo Dirigido:  V un conjunto finito no vacio, y sea la relación binaria E ⊆ V xV, el par ordenado (V, E) es un grafo
dirigido sobre V, o digrafo, donde V es el conjunto de vertices o nodos y E es su conjunto de aristas.
Escribimos G = (V, E) para denotar tal digrafo.

# data[].attributes.body
Es Cuando no importa la dirección de las aristas, la estructura G = (V, E), donde E es ahora un conjunto de
pares no ordenados sobre V, es decir el conjunto de aristas representa una relación simétrica binaria, donde
si Vj y Vk son vertices cualesquiera del conjunto de vertices V de un grafo, (Vj, Vk) ∈ E −→ (Vk, Vj) ∈ E.

# data[].attributes.body
A. Grafos de Cadena: son un tipo de grafo híbrido formado por aristas dirigidas y no dirigidas.

B. Grafo simple: Es aquel que acepta una sola arista uniendo dos vértices cualesquiera, esto quiere decir, que una arista cualquiera es la única que une dos vértices específicos.

C. Multigrafo o Pseudografo: Es el que acepta más de una arista entre dos vértices, estas aristas se llaman múltiples o lazos

# data[].attributes.body
https://www.youtube.com/watch?v=blg6FdDLlS0

# data[].attributes.body
En este tipo de aplicación de los grafos se pueden realizar cálculos de costos; en este caso, la arista del grafo puede representar cosas como: la distancia en kilómetros, el precio de un tiquete de avión o el costo de expandir una red telefónica entre los dos puntos que representan los vértices de los extremos.

La aplicación consiste en encontrar la forma más rápida o barata de ir de una ciudad a otra o de crear una red telefónica, o el punto más adecuado para instalar un hospital en una ciudad.

Cuando dos vértices no están conectados se dice que el coste entre ellos es infinito ( ∞).

# data[].attributes.attachment_link.title
Camino de costo mínimo en grafos - Algoritmo de Dijkstra

# data[].attributes.body
En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

# data[].attributes.body
Los grafos pueden ser considerados formalmente como diagramas o dibujos (representación diagramática), o bien algebraicamente como un par de conjuntos (representación algebraica).

# data[].attributes.body
Geométricamente, un grafo G es un conjunto de puntos en el espacio, algunos de los cuales están unidos entre sí mediante líneas.

Un grafo puede representar una multitud de situaciones posibles de la vida real. Podría simbolizar por ejemplo, un mapa de carreteras, donde los puntos representarían pueblos o ciudades y las líneas las carreteras que unen las ciudades entre sí. En este caso, el grafo nos informaría de las posibles comunicaciones que existen entre las ciudades. Pero este mismo grafo también podría esquematizar un circuito eléctrico, una molécula química, etc.

# data[].attributes.body
Algebraicamente un grafo G se define como un par ordenado:
G=(V,E)-(V(G),E(G))
Donde V es un conjunto no vacío de puntos en el espacio topológico, también conocidos como vértices o nodos, y E es un conjunto de pares no ordenados de elementos distintos de V, denominados lados, líneas o aristas.

Para poder representar algebraicamente un grafo es necesario que esté etiquetado, es decir, que los vértices se distingan unos de otros mediante etiquetas, las cuales pueden ser números o letras.

# data[].attributes.body
Aplicaciones de los Grafos. (s. f.). https://sites.google.com/site/aplicaciongrafos/

Matemáticas Discretas. (s. f.). https://sites.google.com/site/matematicasmoralesgalindo/

colaboradores de Wikipedia. (2023, 15 febrero). Teoría de grafos. Wikipedia, la enciclopedia libre. https://es.m.wikipedia.org/wiki/Teoría_de_grafos

Tomé, C. (2017, 24 mayo). Tras más de un siglo de aventura. . . ¿un ordenador resuelve el problema? Cuaderno de Cultura CientÃfica. https://culturacientifica.com/2017/05/24/teorema-los-cuatro-colores-3-tras-mas-siglo-aventura-ordenador-resuelve-problema/

# data[].attributes.body
Valentina Acosta
Nicolas Cortes
Yonatan Charary
Juan Borda