Graphes et arbres
Arbre
Un arbre est un graphe simplement connexe, non orienté, sans cycles (et donc forcément sans boucles1), dans lequel nous ne pouvons retrouver qu'une seule chaîne pour relier deux sommets distincts.
Le graphe d'un arbre comporte toujours exactement n-1 arêtes2.
Racine d'un graphe
La racine r dans le cas d'un graphe orienté est le sommet à partir duquel nous pouvons accéder à chaque autre sommet du graphe : ∀ y : M[r,y]=1. Ce sommet (racine) est dit ascendant à tout autre sommet.
Arborescence
Nous appelons arborescence un graphe orienté qui possède une racine et pour lequel nous avons pour chaque sommet un seul chemin depuis la racine.
Arbre et arborescence
Les concepts d'arbre et d'arborescence ne sont pas figés. Dans certains cas nous aurons besoin de passer d'une notion à l'autre.
Nous pouvons orienter un arbre à partir d'un sommet. Dans ce cas nous pouvons avoir une arborescence.
Nous pouvons considérer une arborescence comme un graphe non orienté, et dans ce cas nous avons un arbre.
Lorsque nous ne pouvons ajouter une arête ou un arc d'un graphe à un de ses sous-graphes sans perdre le caractère d'arbre ou d'arborescence, nous pouvons dire que le sous-graphe est un arbre maximal ou une arborescence maximale.
Forêt
Lorsque nous avons un graphe composé d'arbres, nous parlons de forêt. Comme un arbre peut généralement être décomposé en sous-arbres, nous avons généralement une forêt dès que nous avons un arbre dans notre graphe.
Exercice
Voici quelques graphes, à vous de déterminer si nous sommes en présence d'un arbre, d'une arborescence, d'une forêt...
| 
| L'orientation de G2 ne nous permet pas de déterminer une racine.
| Par contre nous avons 2 arbres constituées par les sous graphes {1,2,3,4,5} et {6,7}
Par contre nous avons 2 arborescences constituées par les sous graphes {1,2,3,4,5} et {6,7}
| Nous sommes en présence d'un cycle.
Il existe par exemple plusieurs chemins depuis 2 vers 3
| Par contre nous avons 3 arbres constituées par les sous graphes {1,2}, {3,4} et {5,6}
Par contre nous avons 3 arborescences constituées par les sous graphes {1,2}, {3,4} et {5,6}
| L'orientation de G6 ne nous permet pas de déterminer une racine.
Nederlandse vertaling
U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.
Bij voorbaat dank.
Document heeft de 22/11/2009 gemaakt, de laatste keer de 09/03/2020 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-arbres.html
De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.
Referenties
Arbres : lien interne, Les arbres en programmation.
INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri
(September 2008)
Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.
