Grafo

Intuitivamente, un grafo es un esquema constituido por un conjunto de puntos y un conjunto de flechas, cada una de las cuales vincula a dos puntos entre sí. Los puntos se denominan vértices y las flechas, arcos del grafo.
Expresado de un modo más formal, Claude Berge define a un grafo como el dato de la pareja (X, U), donde X y U designan respectivamente a un conjunto de puntos x1, x2,…, xn, llamado conjunto de vértices, y una familia u1, u2,… um de elementos del producto cartesiano: X’X = (x, y) / x Î X, y Î X.
El elemento u = (x, y) se denomina arco, y va desde el vértice x hasta el vértice y.
Todos los grafos están orientados, pero se puede razonar sobre los arcos no orientados, llamados aristas, cuando el problema a tratar no requiere de una orientación particular. En ese caso, los conceptos y propiedades de los grafos son válidos, puesto que siempre es posible considerar las aristas como arcos orientados en el sentido inverso.
De este modo, los nudos de las redes «» pueden ser representados por los vértices de un grafo y los enlaces por las aristas.
Una matriz cuadrada (n ’ n), no necesariamente simétrica, está asociada a cada grafo. En cada caso (x, y) se coloca el valor 1 si un arco vincula a x con y, el valor 0 en el caso contrario. Esta matriz se denomina matriz de conexidad.
Según la teoría de grafos, no interesa la posición de los vértices y la forma de los arcos. Solo interesa saber cómo están enlazados los vértices. Sin embargo, numerosas aplicaciones de esta teoría en análisis espacial ponen en evidencia la importancia de las coordenadas geográficas asociadas a cada uno de los vértices y, por lo mismo, la importancia de las distancias que los separan. Por esta razón, la posición de los vértices en las representaciones gráficas no es normalmente aleatoria.
Del mismo modo, la teoría de grafos no dice nada sobre la naturaleza de los enlaces representados por los arcos. Como máximo, le número de arcos que conectan x e y puede colocarse en la matriz de conexidad en lugar del valor 1, mencionando la única posibilidad de relación. Ahora bien, en análisis espacial y en particular en investigación operativa, la obtención de numerosos resultados requiere tener en cuenta informaciones concernientes a los enlaces representados por el grafo.
Para esto, a cada arco del grafo pueden asociarse varios valores específicos en relación con el fenómeno representado. Puede tratarse de la distancia-tiempo en el caso de redes de transporte o de un valor que caracteriza la importancia de las relaciones jerárquicas en el caso de redes sociales. Los grafos que corresponden se denominan grafos de valorización.

Ver también: «flujos»

Laurent Chapelon