Graphes et optimisation

Accueil > Cours > Généralités sur les graphes

Généralités sur les graphes

mardi 16 août 2005, par

Graphes orientés et non orientés

Un graphe orienté (directed graph) est caractérisé par
- un ensemble S de sommets (vertices ; un sommet : a vertex)
- un ensemble A d’arcs (edges), chaque arc ayant une origine (source) et un but (target) ; un arc a d’origine s, de but t, est généralement noté s->t. On dit alors que t est un successeur de s, et s un prédécesseur de t.

Figure 1.Un exemple de graphe orienté (noté G0 par la suite)

Si l’on ne s’intéresse pas au sens des arcs, on parlera de graphe non orienté (undirected graph), ou graphe symétrique, dont les sommets sont reliés par des arêtes, chaque arête ayant deux extrémités (éventuellement confondues).

Tout graphe orienté admet un graphe non orienté sous-jacent (ayant pour ensemble d’arêtes l’ensemble de ses arcs).

Figure 2.Graphe G1(non orienté) sous-jacent à G0

On peut restreindre un graphe (orienté ou non) à une partie de ses arcs ou arêtes (graphe partiel), ou à une partie de ses sommets (sous-graphe ou graphe induit : on ne considère que les arcs ou arêtes ayant leurs extrémités dans l’ensemble de sommets auquel on se restreint).

Figure 3.Graphe G0

G2 : G0 restreint aux arêtes c,d,e,g,i et G3 : G0 restreint aux sommets C,D,E,F
Figure 4.Graphe partiel et sous-graphe

Un graphe est dit simple s’ il existe au plus un arc (une arête, dans le cas non orienté) d’origine et de but donnés ; dans ce cas, l’ ensemble A peut être défini comme une partie de SxS(graphe d’une relation binaire), un arc étant généralement noté s->t.
Par exemple,G0 n’ est pas un graphe simple (les arcs et ont même origine et même extrémité), mais les graphes restreints G2 et G3 sont des graphes simples.

Un graphe orienté simple est dit antisymétrique si, pour aucun arc s->t, le graphe ne comporte d’arc t->s.
Par exemple,G2 est un graphe antisymétrique, mais G3 ne l’est pas (il comporte des arcs C->D et D->C ; en outre, un graphe antisymétrique ne peut comporter d’arc dont l’origine et le but sont confondus, comme E->E).

Chemins, circuits et cycles

Un chemin d’un graphe orienté est une suite d’arcs, l’origine d’un arc étant le but de l’arc précédent : désigne un chemin d’origine , de but , de longueur .

Un chemin est dit simple s’ il ne passe pas deux fois par le même arc.

Un circuit, ou cycle, est un chemin dont l’origine et le but sont confondus ; un circuit est dit élémentaire s’ il ne passe pas deux fois par le même sommet (les sommets sont deux à deux distincts, sauf l’origine et le but). Une boucle est un circuit composé d’un seul arc.

Figure 5.Le graphe

Exemples : est un chemin simple de ;est un circuit élémentaire.
Un dag (pour directed acyclic graph) est un graphe orienté sans circuit.

On parlera également de chemin, de cycle1 ou de boucle d’un graphe non orienté (ce sont les chemins, circuits ou boucles des graphes orientés admettant ce graphe pour graphe non orienté sous­jacent).
Étant donné un graphe orienté antisymétrique, tout cycle élémentaire du graphe non orienté sous­jacent, muni d’un sens de parcours, peut s’écrire de façon unique comme somme ou différence d’arcs.

Exemples : le cycledepeut s’écrire ; le cyclepeut s’écrire.

Un cycle quelconque peut s’écrire comme une somme de cycles élémentaires (il suffit d’entamer un nouveau cycle élémentaire chaque fois que l’on rencontre un sommet déjà vu).

Une base de cycles est un ensemble de cycles élémentaires tels que tout cycle puisse s’écrire, de façon unique, comme somme ou différence de cycles de la base ; on admettra que toutes les bases de cycles ont le même nombre d’éléments, qui constitue le nombre cyclomatique du graphe.

Exemple : le nombre cyclomatique deest 2 (les cycles et constituent une base).

Clôture transitive d’un graphe

La clôture transitive (ou fermeture transitive d’un graphe simple(orienté ou non) est le graphedont les sommets sont ceux de, et les arcs (ou arêtes) sont les tels qu’il existe dansun chemin du sommetau sommet.

Figure 6.Un graphe simple et sa clôture transitive

Connexité, forte connexité

On dit qu’un graphe (non orienté) est connexe s’il existe un chemin entre deux sommets quelconques de ce graphe ; la composante connexe d’un sommet est l’ensemble des sommets qui lui sont reliés.

Figure 7.Les 3 composantes connexes de

On dit qu’un graphe orienté est fortement connexe si pour tous sommets et , il existe un chemin allant de à ; la composante fortement connexe d’un sommet est l’ensemble des sommets tels qu’il existe un chemin de à et un chemin de à .

Figure 8.Les 5 composantes fortement connexes de

Arbres et arborescences

Un arbre est un graphe (non orienté) connexe sans cycle simple :

Figure 9.Arbre

Dans un arbre, deux sommets quelconques sont reliés par un et un seul chemin ; le nombre de sommets et le nombre d’arcs sont liés par la relation .

Les feuilles d’un arbre sont ses sommets de degré 1 (les sommets de degré supérieur à 1 sont appelés nuds internes).

Une forêt est un graphe non orienté dont les composantes connexes sont des arbres.

Une arborescence est un graphe orienté possédant un sommet privilégié, la racine, de façon qu’il existe un et un seul chemin de la racine à tout autre sommet. Dans une arborescence, la racine n’a aucun prédécesseur ; tout autre sommet que la racine a exactement 1 prédécesseur (son père).

On peut orienter les arêtes d’un arbre à partir de n’importe quel sommet de façon à obtenir une arborescence. Par exemple, à partir de l’arbre de la figure 9, en prenant pour racine le sommet 1, on obtient l’arborescence suivante :

Figure 10.Arborescence

En pratique, le mot arbre désigne aussi bien une arborescence qu’un arbre au sens strict (non orienté). Arbres et arborescences servent à représenter des relations dans des domaines très divers :
- informatique : arborescences de fichiers
- gestion de personnel : organigrammes hiérarchiques
- grammaire : arbres syntaxiques...