4.7 Notions d’arbre et d’arbo res cence
145
© Dunod – Toute reproduction non autorisée est un délit.
4.7.1 Arbre. Défi ni tion et prop rié tés élé men taires
Étant donné un graphe non orienté de n som mets 1 n > 22 , on obtient un arbre en
« connec tant » tous les som mets sans for mer de cycle (c’est- à-dire en reliant les
som mets deux à deux par des arêtes). Par dé finition, un arbre est un graphe connexe
et sans cycle.
Un arbre com porte n 2 1 arêtes. En effet, G est connexe entraîne p 5 1 ; G est
sans cycle entraîne V(G) 5 0, d’ou V 5 m 2 n 1 1 et m 5 n 2 1.
Une défi ni tion équi va lente d’un arbre est qu’il consti tue un graphe connexe de
n 2 1 arêtes. En effet p 5 1 et m 5 n 2 1 entraîne V(G) 5 m 2 (n 2 1) 1 1 5 0 :
donc G est sans cycle.
Une prop riété qui nous sera utile pour les appli ca tions (cf. les pro grammes de
tran sport) est que l’addi tion à un arbre d’une arête entre deux som mets (en par ti cu -
lier, deux som mets non- adjacents dès que n > 3) crée un cycle et un seul. En effet, si
l’on relie par une arête sup plé men taire les deux som mets d’un arbre on crée un cycle
unique : ces deux som mets, dans l’arbre, étant reliés par une chaîne unique, l’addi -
tion d’une arête crée alors un cycle et un seul. En effet V(G) 5 0 ; l’ajout d’une arête
se tra duit par : m r 5 m 1 1 et V(Gr) 5 V(G) 1 1 5 1.
Il est aisé de prou ver que dans un arbre deux som mets quel conques x et y sont
reliés par une chaîne unique : s’il n’exis tait pas de chaîne entre x et y le graphe ne
serait pas connexe (or un arbre est connexe par défi ni tion). S’il exis tait plu sieurs
chaînes entre x et y, on pour rait alors exhi ber au moins un cycle (or un graphe est
sans cycle par défi ni tion).
Dans l’exemple de la figure 4.35, l’addi tion de
l’arête [D, P] crée un cycle et un seul :
[D, C, B, E, G, H, L, P, D].
Dans l’arbre, D et P sont reliés par une chaîne
unique :
[D, C, B, E, G, H, L, P].
4.7.2 Arbo res cence
Dans un graphe G 5 (X, U), on nomme « racine », tout som met à par tir duquel part
au moins un che min vers tout autre som met. Un graphe peut com por ter 0 ou 1 ou plu -
sieurs racines ; ainsi dans un graphe for te ment connexe, tout som met est une racine ;
dans un « réseau de tran sport » (cf Flot 4.4.1) la source est une racine, alors unique.
On définit une « arbo res cence » comme un graphe qui, sans son orien ta tion, est
un arbre et, avec son orien ta tion, com porte une racine.
Cette racine est unique (sinon si r et rr étaient deux racines dif fé rentes, par r et
r’ pas se rait un cir cuit et le graphe sans l’orien ta tion com por te rait un cycle, ce qui
Figure 4.35
145
© Dunod – Toute reproduction non autorisée est un délit.
4.7.1 Arbre. Défi ni tion et prop rié tés élé men taires
Étant donné un graphe non orienté de n som mets 1 n > 22 , on obtient un arbre en
« connec tant » tous les som mets sans for mer de cycle (c’est- à-dire en reliant les
som mets deux à deux par des arêtes). Par dé finition, un arbre est un graphe connexe
et sans cycle.
Un arbre com porte n 2 1 arêtes. En effet, G est connexe entraîne p 5 1 ; G est
sans cycle entraîne V(G) 5 0, d’ou V 5 m 2 n 1 1 et m 5 n 2 1.
Une défi ni tion équi va lente d’un arbre est qu’il consti tue un graphe connexe de
n 2 1 arêtes. En effet p 5 1 et m 5 n 2 1 entraîne V(G) 5 m 2 (n 2 1) 1 1 5 0 :
donc G est sans cycle.
Une prop riété qui nous sera utile pour les appli ca tions (cf. les pro grammes de
tran sport) est que l’addi tion à un arbre d’une arête entre deux som mets (en par ti cu -
lier, deux som mets non- adjacents dès que n > 3) crée un cycle et un seul. En effet, si
l’on relie par une arête sup plé men taire les deux som mets d’un arbre on crée un cycle
unique : ces deux som mets, dans l’arbre, étant reliés par une chaîne unique, l’addi -
tion d’une arête crée alors un cycle et un seul. En effet V(G) 5 0 ; l’ajout d’une arête
se tra duit par : m r 5 m 1 1 et V(Gr) 5 V(G) 1 1 5 1.
Il est aisé de prou ver que dans un arbre deux som mets quel conques x et y sont
reliés par une chaîne unique : s’il n’exis tait pas de chaîne entre x et y le graphe ne
serait pas connexe (or un arbre est connexe par défi ni tion). S’il exis tait plu sieurs
chaînes entre x et y, on pour rait alors exhi ber au moins un cycle (or un graphe est
sans cycle par défi ni tion).
Dans l’exemple de la figure 4.35, l’addi tion de
l’arête [D, P] crée un cycle et un seul :
[D, C, B, E, G, H, L, P, D].
Dans l’arbre, D et P sont reliés par une chaîne
unique :
[D, C, B, E, G, H, L, P].
4.7.2 Arbo res cence
Dans un graphe G 5 (X, U), on nomme « racine », tout som met à par tir duquel part
au moins un che min vers tout autre som met. Un graphe peut com por ter 0 ou 1 ou plu -
sieurs racines ; ainsi dans un graphe for te ment connexe, tout som met est une racine ;
dans un « réseau de tran sport » (cf Flot 4.4.1) la source est une racine, alors unique.
On définit une « arbo res cence » comme un graphe qui, sans son orien ta tion, est
un arbre et, avec son orien ta tion, com porte une racine.
Cette racine est unique (sinon si r et rr étaient deux racines dif fé rentes, par r et
r’ pas se rait un cir cuit et le graphe sans l’orien ta tion com por te rait un cycle, ce qui
Figure 4.35