Structures de données relationnelles

Il s’agit de définir le modèle des graphes, leurs représentations et leurs manipulations. On s’efforce de mettre en avant des applications importantes et si possibles modernes : réseau de transport, graphe du web, réseaux sociaux, bio-informatique. On précise autant que possible la taille typique de tels graphes.

Notions	Commentaires
Graphe orienté, graphe non orienté. Sommet (ou nœud); arc, arête. Boucle. Degré (entrant et sortant). Chemin d’un sommet à un autre. Cycle. Connexité, forte connexité. Graphe orienté acyclique. Arbre en tant que graphe connexe acyclique. Forêt. Graphe biparti.	Notation : graphe 𝐺 = (𝑆,𝐴), degrés 𝑑+(𝑠) et 𝑑−(𝑠) dans le cas orienté. On n’évoque pas les multi-arcs. On représente un graphe orienté par une matrice d’adjacence ou par des listes d’adjacence.
Pondération d’un graphe. Étiquettes des arcs ou des arêtes d’un graphe.	On motive l’ajout d’information à un graphe par des exemples concrets : graphe de distance, automate fini, diagramme de décision binaire.

On présente les manipulations usuelles sur les graphes en C et en OCaml. La présentation en C s’effectue à travers des tableaux statiques. Pour la représentation en liste d’adjacence, on peut considérer un tableau à deux dimensions dont les lignes représentent chaque liste avec une sentinelle ou un indicateur de taille en premier indice.