Chapitre 7 Arbres et arborescences
Dans les chapitres précédents, nous avons défini un certain nombre de concepts
fondamentaux de la théorie des graphes; puis nous avons donné les moyens de résoudre
les problèmes concernant la notion de chemin dans un graphe, et en particulier les
problèmes de chemin de valeur minimale.
Dans ce chapitre, nous allons examiner des classes de graphes particuliers, que l'on
rencontre très fréquemment dans les applications : les arbres et les arborescences.
7.1. ARBRES – DEFINITION
Nous nous plaçons ici dans le cas des graphes non orientés
où
est
l'ensemble des sommets et l'ensemble de arêtes. Il s'agit de multigraphes (cf. chap I)
dans la mesure où deux sommets quelconques peuvent être reliés par plusieurs arêtes.
Dans ces conditions, une définition possible d'un arbre est la suivante :
Définition I
Un arbre est un graphe
connexe, sans cycles, comportant au moins deux
sommets.
En fait, dans de nombreux cas, d'autres définitions équivalentes sont susceptibles d'être
utilisées :
Définition II
Un arbre est un graphe
sans cycle, comportant n sommets avec
et dont le
nombre d'arêtes est égal à
Démontrons que la définition I entraîne la définition II. Pour cela nous introduirons les
notations suivantes pour caractériser le graphe :
: nombre de sommets
: nombre d'arêtes
: nombre de composantes connexes du graphe (voir chap I).
puis nous définirons un nombre remarquable, dit nombre cyclomatique par :
Dans les chapitres précédents, nous avons défini un certain nombre de concepts
fondamentaux de la théorie des graphes; puis nous avons donné les moyens de résoudre
les problèmes concernant la notion de chemin dans un graphe, et en particulier les
problèmes de chemin de valeur minimale.
Dans ce chapitre, nous allons examiner des classes de graphes particuliers, que l'on
rencontre très fréquemment dans les applications : les arbres et les arborescences.
7.1. ARBRES – DEFINITION
Nous nous plaçons ici dans le cas des graphes non orientés
où
est
l'ensemble des sommets et l'ensemble de arêtes. Il s'agit de multigraphes (cf. chap I)
dans la mesure où deux sommets quelconques peuvent être reliés par plusieurs arêtes.
Dans ces conditions, une définition possible d'un arbre est la suivante :
Définition I
Un arbre est un graphe
connexe, sans cycles, comportant au moins deux
sommets.
En fait, dans de nombreux cas, d'autres définitions équivalentes sont susceptibles d'être
utilisées :
Définition II
Un arbre est un graphe
sans cycle, comportant n sommets avec
et dont le
nombre d'arêtes est égal à
Démontrons que la définition I entraîne la définition II. Pour cela nous introduirons les
notations suivantes pour caractériser le graphe :
: nombre de sommets
: nombre d'arêtes
: nombre de composantes connexes du graphe (voir chap I).
puis nous définirons un nombre remarquable, dit nombre cyclomatique par :