En la lingüística, un grafo es la unidad abstracta que comprende el conjunto de grafías de una letra. La palabra tiene origen griego y significa “dibujo” o “imagen”.

Para las matemáticas y las ciencias de la computación, un grafo es el principal objeto de estudio de la teoría de grafos. De esta forma, un grafo se representa gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (aristas). Los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.

Los especialistas consideran que el primer resultado de la teoría de grafos fue la respuesta de Leonhard Euler sobre el problema de los puentes de Königsberg, en 1736. Este trabajo también se considera como uno de los primeros resultados topológicos en geometría.

Los grafos pueden ser simples (cuando sólo una arista une dos vértices cualesquiera) o complejos. Los grafos simples están formados por dos conjuntos: el conjunto V de vértices o nodos y el conjunto de pares de vértices que se llaman aristas o arcos y que señalan qué nodos están relacionados.

Por otra parte, un grafo es conexo si cada par de vértices está conectado por un camino. Por ejemplo: para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

En cambio, un grafo es fuertemente conexo si cada par de vértices está conectado por, al menos, dos caminos disjuntos.

Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices, mientras que un grafo es bipartito si sus vértices son la unión de dos grupos de vértices, bajo una serie de condiciones.

Definiciones relacionadas:
1. Definición de vértice
2. Definición de nodo