Arbres

On appelle arbre tout graphe connexe, sans cycles.

Un graphe sans cycles mais non connexe est appelé une forêt.


Un arbre
Une forêt

Théorème 5

Les affirmations suivantes sont équivalentes pour tout graphe G = (V, E) à n sommets.

  1. G est un arbre,
  2. G est sans cycles et connexe,
  3. G est sans cycles et comporte n-1 arêtes,
  4. G est connexe et comporte n-1 arêtes,
  5. chaque paire {u, v} de sommets distincts est reliée par une seule chaîne simple (et le graphe est sans boucles).

Théorème 6

Tout arbre fini avec au moins deux sommets comporte au moins deux sommets pendants ou feuilles, c'est-à-dire des sommets incidents avec une seule arête.

Exercices

Exercice 1
Démontrez le théorème 5. Pour cela, utilisez le théorème 1.
Exercice 2
Démontrez le théorème 6.
Exercice 3
Combien d'arbres différents existe-t-il avec 5 sommets ? avec 6 sommets ? avec 7 sommets ?

Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés!
Mot de passe :

Didier Müller, 8.2.03