Définition
Un arbre est un graphe connexe qui n’a pas de cycle.
les arbres à six sommets
Caractérisation d'un arbre. Soit G un graphe ayant n sommets. Les propriétés
suivantes sont équivalentes :
i) G est un arbre ;
ii) pour tous sommets a,b différents, il existe un unique chemin d’origine a et d’extrémité b ;
iii) G est connexe et possède n−1 arcs.
Démonstration.
a
b
u
v
C 1
C 2
Il suffit de raisonner dans le cas n 3. Supposons que G est un arbre. Alors G est connexe
donc entre deux sommets a et b différents, il existe au
moins un chemin d’origine a et d’extrémité b ; supposons
qu’il existe deux tels chemins C 1 et C 2 ; considérons le
premier sommet u de C 1 qui est aussi sur C 2 mais dont le
successeur sur C 1 n’est pas sur C 2 (u existe car C 1 = C 2 ).
Soit v le sommet suivant sur C 1 qui soit aussi sur C 2 . Les
parties de C 1 et C 2 entre u et v forment alors un cycle, contrairement à l’hypothèse que G
est un arbre.
Cela montre que (i) implique (ii). Réciproquement, si G possède la propriété (ii), il est évidemment
connexe et sans cycle. On a donc équivalence entre (i) et (ii).
Pour démontrer que (i) implique (iii), raisonnons par récurrence sur le nombre de sommets. On
peut trouver dans G un chemin s 1 , s 2 , . . . , s n de longueur maximum. Supposons que a est
un sommet adjacent à s n ; si a était différent de tous les s i , on pourrait prolonger le chemin
en ajoutant a ; si a était l’un des sommets s 1 , . . . , s n−2 , le graphe contiendrait un cycle ; le
seul sommet adjacent à s n est donc s n−1 . En supprimant le sommet s n et l’arc
s n−1 , s n , on
obtient un graphe G
ayant n−1 sommets et p−1 arcs, où p est le nombre d’arcs de G. Le
graphe G
n’a pas de cycle et est encore connexe, donc G
est un arbre. Par hypothèse de
récurrence, G
possède n−2 arcs, donc on a l’égalité p−1 = n−2, ou encore p = n−1.
Il reste à montrer que (iii) implique (i). On raisonne à nouveau par récurrence sur le nombre
de sommets. Supposons que G est connexe et possède n − 1 arcs. Puisque G est connexe, les
sommets ont des degrés d 1 , . . . , d n strictement positifs. L’égalité d 1 + d 2 + · · · + d n = 2(n − 1)
montre que les degrés ne peuvent pas être tous strictement supérieurs à 1, donc il existe au
moins un sommet a de degré 1. En supprimant de G le sommet a et l’unique arc qui y
passe, on obtient un graphe G
ayant n−1 sommets et n−2 arcs. Ce graphe G
est encore
connexe, il a un arc de moins que le nombre de sommets, donc c’est un arbre, par hypothèse
de récurrence. Un éventuel cycle de G doit passer par a, ce qui n’est pas possible car le degré
de a est égal à 1. Le graphe G n’a donc pas de cycle.
On a souvent besoin de pondérer les arcs : par exemple, si les arcs d’un graphe
représentent des liaisons aériennes, on pourra attribuer à chaque arc le temps ou le
coût de transport correspondant.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 79
Un arbre est un graphe connexe qui n’a pas de cycle.
les arbres à six sommets
Caractérisation d'un arbre. Soit G un graphe ayant n sommets. Les propriétés
suivantes sont équivalentes :
i) G est un arbre ;
ii) pour tous sommets a,b différents, il existe un unique chemin d’origine a et d’extrémité b ;
iii) G est connexe et possède n−1 arcs.
Démonstration.
a
b
u
v
C 1
C 2
Il suffit de raisonner dans le cas n 3. Supposons que G est un arbre. Alors G est connexe
donc entre deux sommets a et b différents, il existe au
moins un chemin d’origine a et d’extrémité b ; supposons
qu’il existe deux tels chemins C 1 et C 2 ; considérons le
premier sommet u de C 1 qui est aussi sur C 2 mais dont le
successeur sur C 1 n’est pas sur C 2 (u existe car C 1 = C 2 ).
Soit v le sommet suivant sur C 1 qui soit aussi sur C 2 . Les
parties de C 1 et C 2 entre u et v forment alors un cycle, contrairement à l’hypothèse que G
est un arbre.
Cela montre que (i) implique (ii). Réciproquement, si G possède la propriété (ii), il est évidemment
connexe et sans cycle. On a donc équivalence entre (i) et (ii).
Pour démontrer que (i) implique (iii), raisonnons par récurrence sur le nombre de sommets. On
peut trouver dans G un chemin s 1 , s 2 , . . . , s n de longueur maximum. Supposons que a est
un sommet adjacent à s n ; si a était différent de tous les s i , on pourrait prolonger le chemin
en ajoutant a ; si a était l’un des sommets s 1 , . . . , s n−2 , le graphe contiendrait un cycle ; le
seul sommet adjacent à s n est donc s n−1 . En supprimant le sommet s n et l’arc
s n−1 , s n , on
obtient un graphe G
ayant n−1 sommets et p−1 arcs, où p est le nombre d’arcs de G. Le
graphe G
n’a pas de cycle et est encore connexe, donc G
est un arbre. Par hypothèse de
récurrence, G
possède n−2 arcs, donc on a l’égalité p−1 = n−2, ou encore p = n−1.
Il reste à montrer que (iii) implique (i). On raisonne à nouveau par récurrence sur le nombre
de sommets. Supposons que G est connexe et possède n − 1 arcs. Puisque G est connexe, les
sommets ont des degrés d 1 , . . . , d n strictement positifs. L’égalité d 1 + d 2 + · · · + d n = 2(n − 1)
montre que les degrés ne peuvent pas être tous strictement supérieurs à 1, donc il existe au
moins un sommet a de degré 1. En supprimant de G le sommet a et l’unique arc qui y
passe, on obtient un graphe G
ayant n−1 sommets et n−2 arcs. Ce graphe G
est encore
connexe, il a un arc de moins que le nombre de sommets, donc c’est un arbre, par hypothèse
de récurrence. Un éventuel cycle de G doit passer par a, ce qui n’est pas possible car le degré
de a est égal à 1. Le graphe G n’a donc pas de cycle.
On a souvent besoin de pondérer les arcs : par exemple, si les arcs d’un graphe
représentent des liaisons aériennes, on pourra attribuer à chaque arc le temps ou le
coût de transport correspondant.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 79