Graphes : vocabulaire, représentation, parcours

Un graphe est un ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté). Le degré d'un sommet est le nombre d'arêtes qui y aboutissent. Dans un graphe non orienté, la somme des degrés vaut 2 × (nombre d'arêtes) — c'est le lemme des poignées de main. Un chemin est une suite de sommets consécutivement reliés ; un cycle est un chemin fermé. Un graphe est connexe si, depuis tout sommet, on peut atteindre tout autre sommet par un chemin. Un arbre est un graphe connexe sans cycle ; il a exactement n−1 arêtes pour n sommets. Le parcours en largeur (BFS) explore les sommets couche par couche depuis un sommet source, tandis que le parcours en profondeur (DFS) explore aussi loin que possible avant de revenir. Par exemple, un réseau social est modélisé par un graphe : les personnes sont les sommets, les relations d'amitié sont les arêtes.