Les structures de données

Qu'est ce qu'est un graphe ?

L'objet "graphe"

Le graphe est une structure mathématique, qu'il est possible d'implémenter en structure de données informatique. Mathématiquement, un graphe représente un couple entre un ensemble d'éléments, et un ensemble dans lequel des relations entre éléments sont spécifiées. Dans un arbre, chaque élément est nommé un noeud, et les relations sont nommés des liens. Selon la façon dont sont représentés les liens, l'arbre peut avoir plusieurs charactéristiques différentes. Si deux éléments sont liés dans un seul sens possible, alors le graphe est dit orienté, sinon il est non-orienté. Si les liens contiennent aussi une valeur, le graphe est dit pondéré. Dans le cas d'une représentation d'un réseau sous forme de graphe, chaque valeurs des liens peut représenter la bande passante du réseau. C'est la même chose pour les noeuds : si les noeuds contiennent une valeur, le graphe est dit étiqueté. Topologiquement, l'étude des combinaisons des liens des graphes permettent d'avoir plus de données sur ce graphe. Par exemple, si il existe un chemin dans le graphe permettant d'aller d'un noeud à... lui même en passant par d'autres noeuds, le graphe est dit cyclique (sinon, il est acyclique). De plus, un graphe où il est possible d'aller vers tous les éléments (quelque soit l'élément de départ) est dit connexe. Des graphes peuvent interdire l'accès de certains noeuds par d'autres : ils sont dit non connexes. De plus, nous pouvons représenter les liens d'un graphe de pleins de manières possibles, comme avec une matrice (dite adjacente).

En informatique, ces liens représentent des moyens d'accés aux données liées.

L'objet "arbre"

Dans un arbre binaire, le plus grand nombre de noeud est log2(n+1). La complexité est donc logarithmique.