3.1 Élé ments de la théo rie des graphes
65
© Dunod – Toute reproduction non autorisée est un délit.
Si l’on fait la somme boo léenne :
M 1
# M
324 1
# M
334 1
# M
344
et, plus géné ra le ment, M 1
# M
324 1
# c 1
# M
3k214
,
on trouve une matrice (qui, dans le cas par ti cu lier de l’exemple est entiè re ment for
mée de 1) dans laquelle la pré sence d’un 1 à l’inter sec tion de la ligne x et de la
colonne y signi fie : « il existe dans le graphe au moins un che min de lon gueur infé
rieure ou égale à k 2 1 de x vers y ».
On appelle fer me ture tran si tive d’un som met x, d’un graphe G 5 1 X, G2 ,
l’expres sion :
G 1 x2 5 5x6 x G 1 x2 x G
2
1 x2 x c x G
n21
1 x2 ,
où, pour sim pli fier, on a noté G
1
1 x2 5 G 1 x2 et G
k
1 x2 5 G1 G
k21
1 x2 2 .
G1 x2 désigne l’ensemble des des cen dants de x, c’est àdire des som mets acces
sibles depuis x par des che mins ( y compris x luimême).
Il est facile de mon trer que l’on obtient la fer me ture tran si tive de l’ensemble X
des som mets du graphe en cal cu lant la matrice (I 1
# M)
3n214
(car la lon gueur maximale des che mins élé men taires de G est : n21).
M 5 I 1
# M 1
# M
324 1
# c 1
# M
3n214 5 1 I 1
# M2
3n214
où I est la matrice boo léenne unité (qui ne comporte que des 1 dans la dia go nale et
des 0 par tout ailleurs).
En effet, en cal cul boo léen, la for mule du binôme de Newton est plus simple :
1 A 1
# B2
3n214 5 A
3n214 1
# A
3n224 # B 1
# A
3n234 # B
324 1
# c 1
# B
3n214
.
(À cause de l’idempotence de la somme boo léenne : 1 1
#
1 5 1, le tri angle de
Pas cal (des C
p
n ) a tous ses élé ments égaux à 1 en cal cul boo léen !)
Consi dé rons, par exemple, le graphe de la
figure 3.6. On a d’abord écrit M, puis en por tant des
1 dans la dia go nale, I 1
# M.
Cal cu lons 1 I 1
# M2
324
, 1 I 1
# M2
334
, puis 1 I 1
# M2
354
.
Nous obte nons :
Figure 3.6
ˆ
ˆ
ˆ
65
© Dunod – Toute reproduction non autorisée est un délit.
Si l’on fait la somme boo léenne :
M 1
# M
324 1
# M
334 1
# M
344
et, plus géné ra le ment, M 1
# M
324 1
# c 1
# M
3k214
,
on trouve une matrice (qui, dans le cas par ti cu lier de l’exemple est entiè re ment for
mée de 1) dans laquelle la pré sence d’un 1 à l’inter sec tion de la ligne x et de la
colonne y signi fie : « il existe dans le graphe au moins un che min de lon gueur infé
rieure ou égale à k 2 1 de x vers y ».
On appelle fer me ture tran si tive d’un som met x, d’un graphe G 5 1 X, G2 ,
l’expres sion :
G 1 x2 5 5x6 x G 1 x2 x G
2
1 x2 x c x G
n21
1 x2 ,
où, pour sim pli fier, on a noté G
1
1 x2 5 G 1 x2 et G
k
1 x2 5 G1 G
k21
1 x2 2 .
G1 x2 désigne l’ensemble des des cen dants de x, c’est àdire des som mets acces
sibles depuis x par des che mins ( y compris x luimême).
Il est facile de mon trer que l’on obtient la fer me ture tran si tive de l’ensemble X
des som mets du graphe en cal cu lant la matrice (I 1
# M)
3n214
(car la lon gueur maximale des che mins élé men taires de G est : n21).
M 5 I 1
# M 1
# M
324 1
# c 1
# M
3n214 5 1 I 1
# M2
3n214
où I est la matrice boo léenne unité (qui ne comporte que des 1 dans la dia go nale et
des 0 par tout ailleurs).
En effet, en cal cul boo léen, la for mule du binôme de Newton est plus simple :
1 A 1
# B2
3n214 5 A
3n214 1
# A
3n224 # B 1
# A
3n234 # B
324 1
# c 1
# B
3n214
.
(À cause de l’idempotence de la somme boo léenne : 1 1
#
1 5 1, le tri angle de
Pas cal (des C
p
n ) a tous ses élé ments égaux à 1 en cal cul boo léen !)
Consi dé rons, par exemple, le graphe de la
figure 3.6. On a d’abord écrit M, puis en por tant des
1 dans la dia go nale, I 1
# M.
Cal cu lons 1 I 1
# M2
324
, 1 I 1
# M2
334
, puis 1 I 1
# M2
354
.
Nous obte nons :
Figure 3.6
ˆ
ˆ
ˆ