Graphe

Intuitivement, un graphe est un schéma constitué par un ensemble de points et par un ensemble de flèches reliant chacune deux de ceux-ci. Les points sont appelés les sommets du graphe et les flèches les arcs du graphe.

De façon plus formalisée Claude Berge définit un graphe G comme la donnée du couple (X, U), où X et U désignent respectivement, un ensemble de points x1, x2,…, xn appelé ensemble de sommets, et une famille u1, u2,…, um d’éléments du produit cartésien :

X ‘ X = (x, y) / x Î X, y Î X

L’élément u = (x, y) est appelé arc allant du sommet x vers le sommet y.

Tous les graphes sont orientés, mais on peut raisonner sur des arcs non orientés appelés arêtes lorsque le problème à traiter ne nécessite pas d’orientation particulière. Dans ce cas les concepts et propriétés des graphes restent valables puisqu’ils est toujours possible de considérer les arêtes comme deux arcs orientés en sens inverse.

Ainsi, les nœuds des réseaux peuvent être représentés par les sommets d’un graphe et les liaisons par les arcs.

A chaque graphe est associée une matrice carré (n ‘ n) non nécessairement symétrique. Dans chaque case (x, y) on porte la valeur 1 si un arc relie x à y, la valeur 0 dans le cas contraire. Cette matrice est appelée matrice de connexité.

Pour la théorie des graphes la position des sommets et la forme des arcs n’importe pas. Seul importe de savoir comment les sommets sont reliés. Cependant, nombres d’applications de cette théorie en «analyse spatiale» font ressortir l’importance des coordonnées géographiques associées à chacun des sommets et, par là même, l’importance des «distances» qui les séparent. Ainsi, la position des sommets dans les représentations graphiques qui en découlent n’est généralement pas aléatoire.

De même, la théorie des graphes ne dit rien sur la nature des liaisons représentées par les arcs. Tout au plus, le nombre d’arcs reliant x à y peut être porté dans la matrice de connexité à la place de la valeur 1 mentionnant la seule possibilité de relation. Or, en analyse spatiale et plus généralement en recherche opérationnelle, l’obtention de nombreux résultats nécessite de prendre en compte des informations concernant les liaisons représentées par le graphe.

Pour ce faire, à chaque arc du graphe peuvent être associées plusieurs valeurs spécifiques en rapport avec le phénomène représenté. Il peut s’agir de la distance – temps dans le cas des réseaux de transport ou d’une valeur caractérisant l’importance des relations hiérarchiques dans le cas des réseaux sociaux. Les graphes correspondant seront appelés graphes valués.

voir aussi :
flux