Forum Prepas.org

bonjour quelle différence entre graphe et arbre ?

Un arbre est un graphe non orienté, acyclique et connexe.

Donc un arbre est un cas particulier de graphe.

Avec un schéma en appui de la définition, ce sera encore plus clair :
https://fr.wikipedia.org/wiki/Arbre_enracin%C3%A9

Le caractère connexe dont np* parle, c'est pour le cas de l'utilisation d'une tronçonneuse pour couper une partie des branches de l'arbre ?

abouMPSI a écrit :Avec un schéma en appui de la définition, ce sera encore plus clair :
https://fr.wikipedia.org/wiki/Arbre_enracin%C3%A9

Cette référence considère que les arbres sont orientés (ce que j'ai toujours cru), je ne comprends pas que np* les définis comme non orientés.

https://fr.wikipedia.org/wiki/Arbre_(graphe)

très différent de la notion d'arbre enraciné

Ma définition est juste un peu plus générale :

https://fr.wikipedia.org/wiki/Arbre_(graphe)

Si l'on choisit un somment particulier d'un arbre (on dit que l'arbre est enraciné), alors il vient une orientation naturelle (de la racine vers les feuilles ou l'inverse). L'orientation est souvent implicite d'ailleurs (et on ne la représente pas forcément graphiquement).

Dans la pratique, je pense que 95% des applications utilisent en effet des arbres enracinés (celui que l'on représente avec la racine en haut et les feuilles en bas). Mais en théorie des graphes on utilise également la version non-orienté dans certains cas. Un exemple classique est celui de l'arbre couvrant d'un graphe. Il n'y a pas de raison de préférer un noeud en particulier et on travaille avec l'arbre vu comme sous-graphe (non-orienté) du graphe initial.