Les graphes : modèle et représentations
Cours · informatique (tronc commun des prépas scientifiques), chapitre 12 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
12.1 Introduction et motivation
Un plan de métro, une carte d'amitiés, le réseau des pages web, les interactions entre protéines d'une cellule : derrière ces objets sans rapport apparent vit une même structure mathématique — des points reliés par des liens. Cette structure s'appelle un graphe, et c'est l'objet conceptuel le plus polyvalent de l'informatique : dès qu'un problème parle de relations, de réseaux, de dépendances ou de déplacements, le réflexe professionnel est de le modéliser par un graphe — première compétence du programme — puis d'appliquer l'arsenal d'algorithmes des deux chapitres à venir.
Les tailles en jeu donnent la mesure de l'enjeu : le graphe du web compte de l'ordre de pages et bien davantage de liens ; un réseau social, comptes et relations ; le réseau routier européen, carrefours ; un réseau d'interactions protéiques, nœuds. À ces échelles, le choix de la représentation en mémoire — listes d'adjacence ou matrice d'adjacence, les deux héros de ce chapitre — n'est pas un détail d'implémentation : c'est lui qui décide si le graphe tient en mémoire, et à quel coût on peut l'interroger.
12.2 Le vocabulaire des graphes
12.2.1 Graphes non orientés, graphes orientés
Un graphe non orienté est la donnée d'un ensemble fini de sommets (on dit aussi nœuds) et d'un ensemble d'arêtes, chaque arête reliant une paire de sommets . L'arête est un lien symétrique : si est relié à , alors est relié à — le modèle des amitiés, des routes à double sens, des liaisons chimiques.
Un graphe orienté a des arcs : des couples ordonnés , représentés par des flèches de vers . Le lien n'implique pas — le modèle des liens hypertextes (la page pointe vers ), des abonnements, des rues à sens unique, des dépendances entre tâches. Une boucle est un arc d'un sommet vers lui-même. (Conformément au programme, on exclut les multi-arcs et multi-arêtes : entre deux sommets, au plus un lien dans chaque sens.)
À gauche, le sommet est isolé : aucun lien ne l'atteint — un graphe n'est pas forcément d'un seul tenant. À droite, le triangle se parcourt dans un seul sens.
12.2.2 Degrés, chemins, cycles, connexité
Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes qui le touchent. Dans un graphe orienté, on distingue le degré sortant (nombre d'arcs partant de ) et le degré entrant (nombre d'arcs arrivant en ). Sur les exemples ci-dessus : , ; , . (Une boucle compte dans chacun des deux degrés orientés.)