--- tags: TNSI, 2023-24, graphes --- # Les graphes ## Plusieurs exemples en un seul La figure ci-dessous représente un réseau informatique, où A, B, C, D et E sont des machines reliées par des câbles. On voit que D est reliée directement à A mais pas à B ni à C. ```mermaid graph A --- B A --- C A --- D B --- C B --- E ``` Mais la même figure peut représenter bien d'autres relations : - Un réseau social : des utilisateurs qui peuvent être "amis" (au sens du réseau social). Dans notre exemple, A est ami avec B, C et D. - Un réseau routier, ferroviaire, téléphonique : A, B, C, D et E sont des villes qui peuvent être reliées par une route, une voie ferrée ou un câble de téléphone. La ville A est reliée avec les villes B, C et D. - Une carte administrative ou politique : les lettres représentent des pays, on relie deux pays sur la figure lorsqu'ils sont frontaliers : ici A possède une frontière avec B, avec C et avec D. ## Prenons du recul Le même schéma peut représenter de nombreuses situations concrètes, nous allons donc avoir besoin d'un vocabulaire précis pour généraliser et étudier cette nouvelle structure abstraite. :::info **Définition.** Un **graphe** est constitué de **sommets** qui peuvent être éventuellement reliés par des **arêtes**. Deux sommets directement reliés par une arête sont des **voisins**. On dit qu'ils sont **adjacents**. Le nombre de sommets d'un graphe est appelé **ordre** du graphe. Le nombre de voisins d'un sommet est le **degré** de ce sommet. ::: Dans notre graphe exemple, qui est un graphe d'**ordre** 5, les **sommets** sont nommés A, B, C, D et E. Ce graphe possède 5 **arêtes** : A-B, A-C, A-D, B-C et B-E. Le sommet A possède trois **voisins** : B, C et D, son **degré** est donc 3. L'avantage d'étudier une structure abstraite est que la même figure peut représenter de nombreuses situations différentes. En pratique les graphes seront constitués d'objets ou de personnes (les sommets) qui peuvent être reliés par une relation. Deux sommets en relation seront liés par une arête sur le graphe. ## À quoi ça sert ? - Nous avons déjà vu quelques exemples. - En philosophie, littérature ou art : [cette étude](https://www.researchgate.net/figure/Network-visualization-of-music-genres-and-subgenres-Note-Nodes-represent-subgenres-and_fig2_328370462) montre un graphe des genres et sous-genres musicaux. Dans cette étude, deux genres sont voisins quand des musiciens jouent les deux. - Et bien d'autres situations où on étudie n'importe quel type de données (les "sommets") qui peuvent être en relation. Ainsi, tout ce que nous apprendrons sur les graphes pourra être utilisé dans de nombreuses situations. :::warning **Exercice** Recherchez, dans la vie de tous les jours ou dans une autre discipline du lycée, une situation pouvant être représentée par un graphe. Dessinez-la sur une feuille de papier (vous vous limiterez à 6 sommets si la situation en présente davantage). Vous pouvez vous inspirer des exemples vus plus haut. :::