différence graphe arbre
Re: différence graphe arbre
Un arbre est un graphe non orienté, acyclique et connexe.
Donc un arbre est un cas particulier de graphe.
Donc un arbre est un cas particulier de graphe.
$ $P = N\!P^* ?$ $
Re: différence graphe arbre
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 ?
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 ?
Re: différence graphe arbre
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.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
Re: différence graphe arbre
ENS Lyon
Ingénieur de recherche
Ingénieur de recherche
Re: différence graphe arbre
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.
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.
$ $P = N\!P^* ?$ $