Chapitre 3 • Éléments de la théorie des graphes
64
3.1.3 Che mins de lon gueur k. Fer me ture tran si tive
Consi dé rons la matrice M du graphe de la figure 3.3. On peut se pro po ser de l’éle ver
au carré, au cube, etc. On obtient ainsi M
2
, M
3
, M
4
, c où l’élé ment (i, j) de M
k
est
le nombre de che mins de lon gueur k allant du som met i au som met j (ce que l’on peut
prou ver par récur rence sur k).
Rap pe lons que le pro duit d’une matrice A, de for mat p 3 q, par une matrice B, de
for mat q 3 r, est la matrice C 5 A # B de for mat p 3 r, telle que
c ij 5 a i1 # b 1j 1a i2 # b 2j 1 c1 a iq # b qj .
Dans un graphe de n som mets, un plus long che min élé men taire comporte, évi dem -
ment, s’il existe, n – 1 arcs. Il passe alors une fois et une seule par tous les som mets du
graphe : on l’appelle che min hamiltonien. Un che min hamiltonien qui se referme sur
lui- même est un cir cuit hamiltonien. Dans le graphe de la figure 3.3 on n’a qu’un cir cuit
hamiltonien : (A, B, C, D, E, A), alors qu’on avait plu sieurs che mins hamiltoniens.
On peut éga le ment cal cu ler les « puis sances » suc ces sives de M en uti li sant comme
loi « multiplicative » le pro duit logique et, comme loi « addi tive » la somme logique dont
nous rappelons les tables ci-dessous. Ainsi, M
[k]
sera encore une matrice boo léenne :
Dans ces condi tions, la pré sence d’un 1 à l’inter sec tion de la ligne x et de la colonne
y de M
[k]
signi fie : « il existe au moins un che min de lon gueur k entre x et y ». Dans
l’exemple choisi, on a les résul tats sui vants :
Tous les termes M
[4]
sont égaux à 1 car dans G il existe au moins un chemin de
longueur 4 de tout sommet x vers tout sommet y : le vérifier sur la Fig. 3.3.
64
3.1.3 Che mins de lon gueur k. Fer me ture tran si tive
Consi dé rons la matrice M du graphe de la figure 3.3. On peut se pro po ser de l’éle ver
au carré, au cube, etc. On obtient ainsi M
2
, M
3
, M
4
, c où l’élé ment (i, j) de M
k
est
le nombre de che mins de lon gueur k allant du som met i au som met j (ce que l’on peut
prou ver par récur rence sur k).
Rap pe lons que le pro duit d’une matrice A, de for mat p 3 q, par une matrice B, de
for mat q 3 r, est la matrice C 5 A # B de for mat p 3 r, telle que
c ij 5 a i1 # b 1j 1a i2 # b 2j 1 c1 a iq # b qj .
Dans un graphe de n som mets, un plus long che min élé men taire comporte, évi dem -
ment, s’il existe, n – 1 arcs. Il passe alors une fois et une seule par tous les som mets du
graphe : on l’appelle che min hamiltonien. Un che min hamiltonien qui se referme sur
lui- même est un cir cuit hamiltonien. Dans le graphe de la figure 3.3 on n’a qu’un cir cuit
hamiltonien : (A, B, C, D, E, A), alors qu’on avait plu sieurs che mins hamiltoniens.
On peut éga le ment cal cu ler les « puis sances » suc ces sives de M en uti li sant comme
loi « multiplicative » le pro duit logique et, comme loi « addi tive » la somme logique dont
nous rappelons les tables ci-dessous. Ainsi, M
[k]
sera encore une matrice boo léenne :
Dans ces condi tions, la pré sence d’un 1 à l’inter sec tion de la ligne x et de la colonne
y de M
[k]
signi fie : « il existe au moins un che min de lon gueur k entre x et y ». Dans
l’exemple choisi, on a les résul tats sui vants :
Tous les termes M
[4]
sont égaux à 1 car dans G il existe au moins un chemin de
longueur 4 de tout sommet x vers tout sommet y : le vérifier sur la Fig. 3.3.