"'O
0
c
:J
0
:<:;
li)
.,,
..--t
c::
:l
0
~
N
"
@
~
.......
0
J::
:;
O'l
"'
·;::::
c::
0
>c::
o.
c::
0
.9
u
ü
:l
.,,
2
o.
~
"
:;
0
11
.,,
0
c:
:l
0
QJ
6.3 • Niveau des sommets d'un graphe sans circuit
Il peut être difficile de faire la fermeture transitive d'un graphe sans oublier
d'arcs. Mais en utilisant la matrice d 'adjacence d ' un graphe, et au prix de quelques
calculs matriciels, on peut déterminer la matrice d'adjacence de la fermeture transitive. Il est alors plus facile de ne pas oublier d'arcs.
Nous admettrons la propriété suivante.
Propriété 6.3
,..
Soit M la matrice d'adjacence d'un graphe à n sommets et soit M la
matrice d 'adjacence de la fermeture transitive du graphe. Alors
M = M Et) M[
2
J Et) ••. Et) M[nJ.
Exemple
o 1 o
Reprenons le graphe précédent dont la matrice d'adjacence est M = 1 0 1
0 0 0
Le graphe possède n = 3 sommets donc d'après la propriété précédente, la
matrice d'adjacence de la fermeture transitive est M = M Et> M [2J Et> M l
3
l ,
Les calculs donnent les résultats suivants :
1 0 1
M 2 =M [2J = 0 1 0
0 0 0
0 1 0
et M
3 = Ml
3
l = 1 0
0 0 0
M = M ©Ml 2 l ©M[
3
l
0 1 0
1 0 1
0 1 0
= 1 0 1 Et> 0 1 0 Et> 1 0 1
0 0 0
0 0 0
0 0 0
1 1 1
= 1 1 1
0 0 0
Connaissant maintenant la matrice d'adjacence de la fermeture transitive, il est
facile de compléter le graphe.
6.3 NIVEAU DES SOMMETS D'UN GRAPHE SANS CIRCUIT
Les graphes sans circuit ni boucle peuvent être ordonnés par niveaux.
La définition suivante va préciser la notion de niveau d'un sommet d'un graphe
orienté défini sur un ensemble S de sommets.
155