Définitions de base

Topologiquement, un graphe est un ensemble , fini ou dénombrable, des sommets (vertex) interconnectés par un ensemble d'arêtes que l'on dénote par . On appelle bords d'une arête les sommets de qui sont connectés par l'arête . Si et sont les bords de l'arête , on note . On appelle multiplicité d'une interconnexion entre les sommets et du graphe, le nombre d'arêtes ayant et comme bords. On note

Chaque arête définissant de manière unique ses bords, on parle parfois, par abus de langage, de multiplicité d'une arête pour signifier en réalité la quantité .

Un graphe tel que , , est appelé simple. Si , on dit que l'arête est incidente au sommet . On dénote par . On dit que deux sommets et sont adjacents si .

On constate que la notion d'adjacence permet de définir une topologie sur le graphe. Cette topologie est intrinsèque à la structure du graphe et ne résulte pas d'une métrique définie éventuellement sur l'espace contenant les sommets du graphe.

Comme exeple de cette topologie intrinsèque, citons celle provenant de la ``distance SNCF'' par opposition à la topologie provenant de la distance géodésique. On appelle degré (ou nombre de coordination) d'un sommet , et on dénote , le nombre d'arêtes qui lui sont incidents

Un graphe dont tous les sommets ont le même degré est dit régulier ; plus précisément si , , le graphe est dit -régulier.

Dans certaines applications -- comme, par exemple, les graphes d'une chaîne de Markov, du réseau routier d'une ville, du réseau de canalisations etc. -- il est nécessaire d'assigner un sens de parcours à chaque arête. On parle alors de graphe orienté. Toutes les définitions précédentes restent valables si on remplace l'ensemble des bords d'une arête par la paire ordonnée .