Les graphes
Cours · NSI (terminale), chapitre 4 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
Les graphes constituent l'une des structures de données les plus puissantes et les plus universelles de l'informatique. Ils permettent de modéliser un grand nombre de situations du monde réel dès lors que l'on s'intéresse à des objets reliés entre eux par des relations : un réseau social où des personnes sont amies, une carte routière où des villes sont reliées par des routes, un réseau informatique où des machines sont connectées, ou encore les pages du web reliées par des liens hypertextes.
Dans ce chapitre, nous étudierons d'abord le vocabulaire mathématique des graphes (sommets, arêtes, degré, chemin, cycle), puis les deux grandes manières de représenter un graphe en mémoire (matrice d'adjacence et listes d'adjacence). Nous présenterons ensuite les deux algorithmes fondamentaux de parcours, le parcours en largeur (BFS) et le parcours en profondeur (DFS), avant d'aborder la détection de cycle. Le chapitre se termine par des exercices et des problèmes résolus inspirés d'applications concrètes comme les réseaux sociaux et le routage de l'information.
4.1 Définitions et vocabulaire
4.1.1 Notion de graphe
Un graphe est un couple où :
- est un ensemble fini d'éléments appelés sommets (en anglais vertices ou nodes) ;
- est un ensemble de liens reliant des paires de sommets.
On note souvent le nombre de sommets et le nombre de liens.
Dans un graphe non orienté, les liens sont appelés arêtes (en anglais edges). Une arête entre les sommets et est notée : elle ne possède pas de sens, on peut la parcourir de vers comme de vers .
Considérons quatre personnes : Alice, Bob, Chloé et David. Alice est amie avec Bob et Chloé ; Bob est ami avec Chloé ; Chloé est amie avec David. On modélise cette situation par un graphe non orienté à 4 sommets et 4 arêtes : \{Alice, Bob\}, \{Alice, Chloé\}, \{Bob, Chloé\} et \{Chloé, David\}. La relation « être ami avec » est symétrique, ce qui justifie l'emploi d'un graphe non orienté.
Dans un graphe orienté (en anglais directed graph ou digraph), les liens sont appelés arcs. Un arc du sommet vers le sommet est noté : il possède un sens. L'arc ne permet d'aller que de vers , et n'implique pas l'existence de l'arc .
Les pages d'un site web forment un graphe orienté : chaque page est un sommet, et un lien hypertexte de la page vers la page est un arc . Le fait que pointe vers n'implique pas que pointe vers : la relation n'est pas symétrique, d'où l'utilisation d'un graphe orienté.
Un graphe pondéré (ou valué) est un graphe dans lequel chaque lien (arête ou arc) est associé à un nombre appelé poids (ou coût). Le poids peut représenter une distance, une durée, un prix, une capacité, etc.
Une carte routière est un graphe pondéré : les villes sont les sommets, les routes sont les arêtes, et le poids d'une arête est la longueur (en kilomètres) de la route correspondante. Calculer le plus court trajet entre deux villes revient à chercher un chemin de poids minimal dans ce graphe.
4.1.2 Degré, chemin et cycle
Deux sommets et sont dits adjacents (ou voisins) s'ils sont reliés par une arête (graphe non orienté) ou par un arc (graphe orienté). L'ensemble des voisins d'un sommet est appelé son voisinage.
Dans un graphe non orienté, le degré d'un sommet , noté , est le nombre d'arêtes incidentes à , c'est-à-dire le nombre de ses voisins.
Dans un graphe orienté, on distingue :
- le degré entrant : nombre d'arcs arrivant en ;
- le degré sortant : nombre d'arcs partant de .
Dans un graphe non orienté à arêtes, la somme des degrés de tous les sommets vaut le double du nombre d'arêtes :
En effet, chaque arête contribue pour au degré de et pour au degré de , donc pour au total. On en déduit que le nombre de sommets de degré impair est toujours pair.