Graphes et arbres

Sommaire du document

Arbre

Un arbre est un graphe simplement connexe, non orienté, sans cycles (et donc forcément sans boucles[1]), 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êtes[2].

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...

GraphesArbreArborescenceForêt
graphe1
oui
oui
oui
graphe2
oui
non
L'orientation de G2 ne nous permet pas de déterminer une racine.
oui
graphe3
non
Par contre nous avons 2 arbres constituées par les sous graphes {1,2,3,4,5} et {6,7}
non
Par contre nous avons 2 arborescences constituées par les sous graphes {1,2,3,4,5} et {6,7}
oui
graphe4
non
Nous sommes en présence d'un cycle.
non
Il existe par exemple plusieurs chemins depuis 2 vers 3
non
graphe5
non
Par contre nous avons 3 arbres constituées par les sous graphes {1,2}, {3,4} et {5,6}
non
Par contre nous avons 3 arborescences constituées par les sous graphes {1,2}, {3,4} et {5,6}
oui
graphe6
oui
non
L'orientation de G6 ne nous permet pas de déterminer une racine.
oui

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

23 mots clés dont 20 définis manuellement (plus d'information...).

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Notes

  1.  Cycles et boucles : Une boucle correspond à la description d'un cycle (sauf que dans le cas d'une boucle le circuit ne comporte qu'un seul sommet)

  2.  n : Rappel : n est la cardinalité de l'ensemble des sommets.

 

Références

  1. livre Langue du document: fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)
  2. Consulter le document html Langue du document: fr Arbres : lien interne, Les arbres en programmation.

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-11315
Document créé le 22/11/09 15:00, dernière modification le Vendredi 17 Juin 2011, 12:11
Source du document imprimé : http:///www.gaudry.be/graphes-arbres.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,07 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Les passions sont toutes bonnes de leur nature et nous n'avons rien à éviter que leurs mauvais usages ou leurs excès.

René Descartes [Extrait de Les passions de l’âme]
 
l'infobrol
Nous sommes le Dimanche 28 Mai 2017, 05:17, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)