Tuvo su inicio formal en los años 40 con el trabajo de Hitchock, Koopmans, y finalmente Dantzing. Entre otros, L.R Ford y D.R Fulkerson han hecho aportaciones importantes. Desde el punto de vista de la teoría de matemática, se puede ir unos años atrás (1930 y más tarde), a los trabajos de Koning, Egarvary y Menger sobre gráficas lineales, considerados de importancia fundamental. En los últimos años la teoría de grafos ha sido objeto de muchos estudios e investigaciones por parte de los matemáticos, encontrando cada vez más aplicaciones en diversas áreas.

En el campo de la investigación de operaciones, la teoría de grafos desempeña un papel particularmente importante, pues muy a menudo el problema de encontrar una solución óptima puede verse como un problema de seleccionar la mejor secuencia de operaciones, dentro de un número finito de alternativas que pueden representarse como un grafo.

Métodos:

• Kruskal

• PRIM

• Algoritmo de Dijkstra

• Método generalizado de Dijkstra

• Algoritmo de Floyd

• Algoritmo de Ford y Fulkerson

• Algoritmo de flujo mínimo

• Redes con requerimientos mínimos y capacidades máximas

• Método de eliminación de circuitos negativos

• Método basado en rutas más cortas

• Método simplex para redes

• Método de la ruta crítica (CPM) hacía adelante

• Método de la ruta crítica hacia atrás.