INFORMATIQUE > STRUCTURES DE DONNÉES
N. m. Graphe non orienté connexe et acyclique. (définition appartenant à la théorie mathématique des graphes)
Un graphe est défini par un ensemble fini G dont les éléments sont appelés sommets et par un ensemble de couples non ordonnés d'éléments de G appelés arêtes.
Les graphes se représentent facilement par un dessin. A chaque sommet on fait correspondre un point du plan et on relie par des traits les points correspondants aux extrémités d'une arête.
La définition précise que le graphe doit être connexe, ce qui signifie qu'il est possible, à partir de n'importe quel sommet, de rejoindre tous les autres en suivant les arêtes.
Elle précise enfin que le graphe doit être acyclique, ce qui signifie qu'il ne doit pas comporter de cycle (pas de chemin admettant le même sommet comme sommet de départ et sommet d'arrivée).
En informatique, un arbre est une structure de données qui représente ce graphe. Elle est composée d'un ensemble de noeuds qui ont chacun au plus un seul ancêtre chacun et un nombre quelconque de descendants. On peut classer les arbres en fonction de leur arité. L'informatique fait un grand usage des arbres binaires.