Un arbre est un graphe à la fois connexe et sans cycle.

 

Si on rajoute un arc u à un graphe, 2 cas exclusifs peuvent se produire :

 

1) Le nombre de composantes connexes diminue (-1), ce qui implique que u n'appartient à aucun cycle dans le nouveau graphe.

2) Le nombre de composantes connexes reste inchangé, ce qui implique que u appartient à un cycle du nouveau graphe, puisqu'il relie deux sommets appartenant à la même composante connexe , donc reliés par une chaîne.

 

En utilisant cette propriété, pour construire un graphe à partir de sommets isolés, par adjonction successive d'arcs, on montre aisément que :

- Un graphe connexe d'ordre n doit posséder au moins n-1 arcs.

- Un graphe sans cycle d'ordre n possède au plus n-1 arcs.

- Un arbre possède exactement n-1 arcs.

 

Théorème : Les 6 propositions suivantes sont équivalentes et caractérisent un arbre :

(1) G est connexe et sans cycle

(2) G est sans cycle avec n-1 arcs

(3) G est sans cycle et est maximal pour cette propriéte (i.e. toute adjonction d'arc crée un cycle)

(4) G est connexe avec n-1 arcs

(5) G est connexe, minimal pour cette propriété (i.e. toute suppression d'arc le rend non connexe)

(6) Tout couple de sommets du graphe est relié par une chaîne unique

 

 

Une forêt est un graphe dont les composantes connexes sont des arbres.

Une Forêt sur n sommets avec p composantes connexes possède n-p arcs.

 

Les notions précédentes ne font pas intervenir l'orientation; en la faisant intervenir, on peut définir les notions suivantes :

 

Un sommet a sera qualifié de racine s'il mène (il existe un chemin) à tous les sommets du graphe.

On peut définir de la même façon une antiracine.

Une arborescence sera un arbre doté d'une racine.

On peut définir de la même manière une antiarborescence.

 

EXERCICES