Arbres et arborescences
151
b) si est sans cycle et connexe,
d'où
En conclusion la définition I entraîne bien la définition II.
Définition I Définition II
De la même façon, nous donnerons une troisième définition d'un arbre :
Définition III
Un arbre est un graphe
connexe, comportant n sommets avec
et dont le
nombre d
' arêtes est égal à
.
On a : Définition II Définition III
En effet, si est sans cycle
Si par ailleurs
, on a
, et est connexe.
Définition IV
Un arbre est un graphe
avec
sans cycle et où l'on créerait un cycle et
un seul en réunissant par une arête deux sommets non adjacents.
On a
Définition III Définition IV
En effet, si
, et
on a
; si par ailleurs on ajoute une
arête, ni ni ne changent; le nouveau graphe G' est tel que
possède donc un cycle et un seul.
Définition V
Un arbre est un graphe
, avec
, connexe, tel que la suppression d'une arête
le rendrait non connexe.
Définition IV Définition V
En effet, si est sans cycle,
. Si on fait
(addition d'une arête)
la définition IV donne pour le nouveau graphe
Soit
soit
. d'où
. Mais si
n'était pas
connexe, on pourrait avoir dans certains cas
.
Donc, est connexe. Par ailleurs si on supprime une arête à , comme
; alors
et on a toujours
(ce n'est pas en supprimant une arête qu'on créera un cycle); alors
d'où
. Le graphe est bien non connexe.