Una estructura combinatoria formada por un conjunto de vértices (nodos) y un conjunto de aristas (pares u ordenados de vértices) utilizada para representar relaciones discretas, conectividad e interacciones.

Principio

La adyacencia codifica relaciones binarias: la presencia, dirección y peso de las aristas capturan la arquitectura de las conexiones; conceptos de teoría de grafos (caminos, componentes, ciclos, cortes) formalizan la conectividad independientemente del embebido.

Demostración

Una red social donde los vértices representan personas y las aristas ponderadas la frecuencia de comunicación: las componentes revelan comunidades desconectadas, los algoritmos de camino más corto identifican introducciones con mínimo número de saltos y las medidas de centralidad muestran nodos influyentes.

Aplicación incorrecta

Interpretar un grafo como un objeto geométrico con propiedades métricas basándose únicamente en posiciones de nodos sin usar los datos de aristas, o tratar un multigrafo como grafo simple perdiendo la información de multiplicidad que afecta al flujo o la capacidad.

Consecuencia

Un modelado correcto mediante grafos permite algoritmos de enrutamiento, agrupamiento, emparejamiento y flujo; las propiedades espectrales de matrices de grafo (adyacencia, Laplaciano) posibilitan particionado, modelado de difusión y análisis de estabilidad.

Inversión

Reemplazar aristas discretas por conexiones continuas (una variedad o un continuo métrico) invierte el modelo relacional discreto en un dominio continuo donde los algoritmos combinatorios ya no se aplican directamente.

Límite

Cubre grafos simples, dirigidos, ponderados y multigrafos, pero excluye hipergráfos (aristas que conectan subconjuntos arbitrarios), complejos simpliciales de orden superior y nubes de puntos puramente geométricas salvo que se definan aristas.

Tensión semántica

Tensión entre 'grafo' y 'red': grafo enfatiza la estructura combinatoria, red suele implicar contexto aplicacional y posibles dinámicas o métricas; también hay tensión con la matriz de adyacencia (representación algebraica) y con el hipergrafo (relaciones de orden superior).

Síntesis

Un grafo es la abstracción discreta de la conectividad por pares: una estructura mínima (vértices más aristas) que admite análisis combinatorio, algebraico y algorítmico para modelar y resolver problemas sobre relaciones y flujo.