152
Recherche opérationnelle
Définition VI
Un arbre est un graphe
, avec
, tel qu'il existe une chaîne et une seule entre
toute paire de sommets.
Définition V Définition VI
En effet, si G est connexe, il existe une chaîne entre deux sommets quelconques, mais il
n'en existe qu'une, car dans le cas contraire, la suppression d'une arête ne créerait pas
nécessairement deux composantes connexes.
Enfin, on a l'application :
Définition VI Définition I
En effet est connexe puisqu'il existe une chaîne entre chaque paire de sommets, mais
comme cette chaîne est unique, il n'y a pas de cycle.
En conséquence la suite d'implications :
montre que les six
définitions proposées sont équivalentes.
7.2. PROBLEMES SUR LES ARBRES
On rencontre souvent dans la pratique les problèmes suivants :
Problème 1
Soit un graphe
. Trouver un graphe partiel de qui soit un arbre (on sait qu'un
graphe partiel de G est obtenu en supprimant un certain nombre d'arêtes de ).
La méthode à utiliser est donnée par la démonstration du résultat suivant :
Un graphe
admet un graphe partiel qui soit un arbre si et seulement si il est
connexe. En effet, s'il n'est pas connexe, aucun des graphes partiels n'est connexe, et
donc G n'admet pas d'arbres partiels.
S'il est connexe, cherchons une arête dont la suppression ne donne pas un nouveau
graphe non connexe ; si une telle arête n'existe pas, c'est que est déjà un arbre, d'après
la définition V. Si une telle arête existe, supprimons-la. Ensuite, on cherche à éliminer
une nouvelle arête, etc. Si nous ne pouvons plus supprimer d'arête, c'est qu'on a obtenu
un arbre partiel, toujours d'après la définition V.
Par exemple, si on prend le graphe :
B
A
E
D
C
1
2
3
6
7
4
5
8
9