Ticker

6/recent/ticker-posts

Header Ads Widget

Cours Théorie des Graphes2 : Arbres


2eme partie du cours 



partie 1 Cours Théorie des graphe

Partie 3 Théorie des graphes


Cour TG : Réseaux de flots


On appelle arbre tout graphe connexe sans cycle. Un graphe sans cycle mais non connexe est
appelé une forêt.
Une feuille ou sommet pendant est un sommet de degré 1.

Théorème
Les affirmations suivantes sont équivalentes pour tout graphe G à n sommets.
1. G est un arbre,
2. G est sans cycle et connexe,
3. G est sans cycle 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 boucle).

Les arbres de six sommets comportent
Théorème
Tout arbre fini avec au moins deux sommets comporte au moins deux sommets pendants.
Exercice
Combien d’arbres différents existe-t-il avec 5 sommets ? Avec 6 sommets ? Avec 7 sommets ?