Historia de Los Grafos

Historia de los Grafos
La teoría de grafos se remonta al matemático suizo Leonhard Euler en 1736, quien es

considerado el padre de esta disciplina. Su investigación se centró en el Problema de
los Puentes de Königsberg, donde la ciudad de Königsberg (actual Kaliningrado, Rusia)
tenía siete puentes que conectaban distintas áreas. El problema era si era posible
cruzar cada puente exactamente una vez y regresar al punto de origen. Euler demostró
que esto no era posible, dando lugar a lo que hoy conocemos como teoría de grafos.
Evolución de la Teoría de Grafos
 Siglo XVIII (Euler): El estudio de problemas topológicos llevó al nacimiento de

los grafos. Euler fue el primero en usar un "grafo" en su solución al problema
de Königsberg, y definió conceptos fundamentales como caminos y ciclos.
 Siglo XIX (Kirchhoff y Cayley): En 1847, Gustav Kirchhoff utilizó grafos para
analizar redes eléctricas. Al mismo tiempo, Arthur Cayley desarrolló el uso de
árboles en la teoría de grafos, aplicándolos en la química para analizar la
estructura molecular.
 Siglo XX (desarrollo en matemáticas y computación): Durante este siglo, los
grafos comenzaron a ser usados en muchas áreas, incluyendo teoría de redes,
ciencias de la computación (estructuras de datos, análisis de algoritmos), y
optimización.
 Época Moderna: Hoy en día, la teoría de grafos es una herramienta esencial en
áreas como inteligencia artificial, biología computacional, redes sociales,
criptografía, telecomunicaciones y muchos otros campos.
Puntos Importantes sobre los Grafos
 Estructura básica: Los grafos consisten en vértices y aristas que representan

objetos y relaciones.
 Conectividad: Es crucial en muchos problemas de redes y rutas; la capacidad de
conectarse a otros nodos determina si un sistema es eficiente o no.
 Tipos de grafos: Dirigidos, no dirigidos, ponderados, cíclicos y conexos.
 Aplicaciones: Desde redes sociales hasta sistemas de transporte y algoritmos de
optimización.
 Historia: Desde el problema de los puentes de Königsberg de Euler hasta las
aplicaciones modernas, los grafos han evolucionado enormemente.
Teoría de Grafos: Fundamentos
Un grafo es una estructura matemática utilizada para modelar relaciones entre

diferentes objetos. Un grafo se compone de dos conjuntos principales:
 Vértices (nodos): Son los puntos o entidades en el grafo.

 Aristas (enlaces): Son las conexiones entre esos vértices, representando
relaciones o interacciones entre ello
Tipos de Grafos
Grafo no dirigido: Las aristas no tienen dirección, es decir, la relación entre dos vértices
va en ambas direcciones.
Ejemplo: Las conexiones de amistad en redes sociales.
Grafo dirigido (dígrafo): Las aristas tienen una dirección, lo que significa que la relación
entre dos vértices va en una dirección específica.
Ejemplo: Enlaces entre páginas web (hipervínculos).

Grafo con pesos: Las aristas tienen un valor asociado (llamado peso), que podría
representar distancias, costos, tiempos, etc.
Ejemplo: Redes de transporte, donde el peso representa la distancia entre ciudades.
Grafos especiales
Arboles: estos son un grafo no dirigido sin ciclo.
Arboles con raíz: son grafos dirigidos que poseen un vértice desde el cual se puede
llegar al resto de los vértices del árbol. Normal mente cuando alguien se refiere a un
árbol se refiere a un árbol con raíz.
Grafos acíclicos dirigido: son grafos dirigidos sin ciclos. Este tipo de grafos es muy
usado para el modelado de problemas y tienen muchas aplicaciones interesantes.
Grafos bipartitos: sus vértices pueden ser separados en dos grupos, permitiendo que
cada vértice de un grupo se conecte con uno o más vértices del otro grupo. Dos
vértices de un grupo no se conectan directamente.
Representación de Grafos:
Matriz de adyacencia: filas y columnas de la matriz representan los vértices del grafo y
en cada una de las posiciones de la matriz va el peso que posee el arco que conecta a 2
determinados vértices.
Lista de adyacencia: se crea una lista para cada vértice donde se almacenan tuplas que
contienen el vértice de destino y el peso que contiene el arco que lleva a el.

Historia de Los Grafos

Cargado por

Copyright:

Formatos disponibles

Historia de Los Grafos

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Historia de Los Grafos

Cargado por

Copyright:

Formatos disponibles

Historia de los Grafos

La teoría de grafos se remonta al matemático suizo Leonhard Euler en 1736, quien es

Evolución de la Teoría de Grafos

 Siglo XVIII (Euler): El estudio de problemas topológicos llevó al nacimiento de

Puntos Importantes sobre los Grafos

 Estructura básica: Los grafos consisten en vértices y aristas que representan

Teoría de Grafos: Fundamentos

Un grafo es una estructura matemática utilizada para modelar relaciones entre

 Vértices (nodos): Son los puntos o entidades en el grafo.

Ejemplo: Las conexiones de amistad en redes sociales.

Ejemplo: Enlaces entre páginas web (hipervínculos).

Ejemplo: Redes de transporte, donde el peso representa la distancia entre ciudades.

Arboles: estos son un grafo no dirigido sin ciclo.

También podría gustarte