156
Recherche opérationnelle
arriver ne sont pas toujours simples, et ne conduisent pas forcément à l'optimum : on
aura plutôt affaire à des heuristiques.
7.3. ARBORESCENCES – DEFINITION
7.3.1. Définitions préalables
a) Graphes quasi fortement connexes
Un graphe orienté
est quasi fortement connexe si, pour toute paire de
sommets
, il existe un sommet du graphe d'où partent des chemins reliant
et
.
Remarque : un graphe quasi fortement connexe est évidemment connexe si on le
désoriente. Un graphe fortement connexe est quasi fortement connexe, la réciproque
n'étant pas vraie.
b) Racine d'un graphe
Un sommet d'un graphe
est une racine si, pour tout sommet
de , il
existe un chemin reliant
.
Théorème : la condition nécessaire et suffisante pour qu'un graphe
admette
une racine est qu'il soit quasi fortement connexe.
En effet, si admet une racine, il est évidemment quasi fortement connexe. D'autre part,
supposons quasi fortement connexe. Considérons les sommets de , soit
Il existe un sommet d'où l'on peut aller en et un sommet d'où l'on peut aller en
et ; un sommet
d'où l'on peut aller en
et . Un sommet
d'où l'on peut
aller en
et
. En reprenant en sens inverse, on voit que de
on peut aller en
tous les sommets du graphe :
est donc une racine.
7.3.2. Arborescences. Définition
Comme pour les arbres, il existe de nombreuses définitions des arborescences. Nous
retiendrons essentiellement les trois définitions suivantes :
Définition I : une arborescence est un graphe (on supposera toujours que
) quasi
fortement connexe et sans cycle, si on le désoriente.
Définition II : une arborescence est un graphe quasi fortement connexe de
arcs.
Définition III : une arborescence est un graphe qui est un arbre si on le désoriente et
qui a une racine.
Il est évident que ces trois définitions sont équivalentes :
En effet, Définition I
Définition II, car si
est quasi fortement connexe, il est
connexe; comme il est sans cycle, c'est un arbre, qui a
arêtes (voir les définitions
des arbres).