%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] > > | | [[Code et Développement/Programmation/Graphes/02_Représentation en Python\|Représentation en Python →]] | > |:---|---:| %% nav-fin %% # Introduction aux graphes Ce chapitre présente la notion de graphe et le vocabulaire associé. Un graphe est un ensemble de **sommets** et d'**arêtes**. Une arête relie deux sommets. Un graphe représente des relations entre des éléments : des villes reliées par des routes, des personnes reliées sur un réseau social. En Python, les graphes de ce cours sont construits avec le module `networkx`. Le chapitre [[Code et Développement/Programmation/Graphes/02_Représentation en Python|Représentation en Python]] détaille ce module. ## Le graphe de référence Le graphe ci-dessous a 7 sommets, nommés de A à G, et 9 arêtes. Les chapitres suivants reprennent ce graphe, dessiné de la même façon. Sa construction en Python est donnée au chapitre [[Code et Développement/Programmation/Graphes/02_Représentation en Python|Représentation en Python]]. La position des sommets sur le dessin n'a pas d'importance. Deux dessins différents peuvent représenter le même graphe. Seules comptent les relations entre les sommets. **À manipuler :** cliquez sur un sommet pour afficher ses voisins et son degré. ```sq-graphe-dessin titre: Graphe de référence arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D ``` ## Chemin et longueur Un **chemin** est une suite d'arêtes qui relie deux sommets. Plusieurs chemins peuvent relier deux sommets. Dans le graphe de référence, E et F sont reliés par un chemin qui passe par C. Ils sont aussi reliés par un chemin qui passe par D et G. La **longueur** d'un chemin est le nombre d'arêtes parcourues. Le chemin E, C, F a une longueur de 2. Le chemin E, D, G, F a une longueur de 3. ## Graphe connexe Un graphe est **connexe** si deux sommets quelconques sont toujours reliés par un chemin. Le graphe de référence est connexe. Un graphe peut être non connexe. Sans les arêtes C-F et F-G, le graphe de référence se sépare en deux parties. Chaque partie s'appelle une **composante connexe**. **À manipuler :** les arêtes C-F et F-G sont retirées. Cliquez sur une arête en pointillés pour la rétablir, ou sur une autre arête pour la retirer. ```sq-graphe-proprietes arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D désactivées: C-F, F-G ``` Un graphe peut même ne contenir aucune arête. ```sq-graphe-dessin titre: Graphe sans arête sommets: A, B, C, D, E, F, G arêtes: ``` À l'inverse, un graphe est **complet** si chaque sommet est relié à tous les autres. ```sq-graphe-dessin titre: Graphe complet à 4 sommets arêtes: A-B, A-C, A-D, B-C, B-D, C-D ``` ## Voisins et degré Deux sommets sont **voisins** s'ils sont reliés par une arête. Le **degré** d'un sommet est le nombre de ses voisins. On le note deg(x). **À manipuler :** cliquez sur chaque sommet. A a trois voisins, B, C et D : deg(A) = 3. B, C et D ont chacun un seul voisin : deg(B) = deg(C) = deg(D) = 1. ```sq-graphe-dessin titre: Voisins et degré arêtes: A-B, A-C, A-D positions: A:190,120; B:80,50; C:300,60; D:190,215 ``` La somme des degrés d'un graphe est égale à deux fois le nombre d'arêtes. Chaque arête compte en effet une fois pour chacune de ses deux extrémités. Ici, 3 + 1 + 1 + 1 = 6 = 2 × 3. ## Cycle et arbre Un **cycle** est un chemin qui revient à son sommet de départ sans repasser par la même arête. Dans le graphe de référence, A, B, F forment un cycle de longueur 3. F, C, D, G forment un cycle de longueur 4. Un **arbre** est un graphe connexe qui ne contient aucun cycle. Un arbre de n sommets a toujours n − 1 arêtes. ```sq-graphe-proprietes arêtes: A-B, B-C, C-D, C-E, E-F positions: A:50,120; B:130,120; C:215,120; D:300,50; E:300,190; F:360,120 ``` ## Arbre couvrant Un **arbre couvrant** d'un graphe est un arbre qui relie tous les sommets du graphe, en n'utilisant que des arêtes de ce graphe. On l'obtient en retirant des arêtes qui forment des cycles, sans jamais séparer le graphe en deux. Un graphe est connexe si et seulement s'il possède un arbre couvrant. **À manipuler :** retirez les arêtes A-B, D-E et D-G. Le tableau indique alors « Arbre : oui ». D'autres choix d'arêtes donnent d'autres arbres couvrants. ```sq-graphe-proprietes arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D ``` ## Graphe orienté Dans un **graphe orienté**, chaque arête a un sens. Elle va d'un sommet de départ vers un sommet d'arrivée. On la dessine par une flèche. Pour un sommet x d'un graphe orienté : - le **degré entrant** d⁻(x) est le nombre d'arêtes qui arrivent sur x ; - le **degré sortant** d⁺(x) est le nombre d'arêtes qui partent de x ; - le degré de x est la somme des deux : deg(x) = d⁻(x) + d⁺(x). **À manipuler :** cliquez sur D. Deux arêtes arrivent sur D, depuis C et G : d⁻(D) = 2. Une arête part de D, vers E : d⁺(D) = 1. Donc deg(D) = 3. ```sq-graphe-dessin titre: Graphe de référence orienté arêtes: A>B, B>F, C>D, C>E, C>F, D>E, F>G, F>A, G>D ``` Un **circuit** est un chemin orienté qui revient à son sommet de départ en suivant le sens des flèches. ```sq-graphe-dessin titre: Un circuit arêtes: A>B, B>C, C>D, D>A ``` Un graphe orienté sans circuit peut représenter un ordre d'exécution : les étapes d'une recette, d'une notice de montage. Une flèche de X vers Y signifie que X doit être fait avant Y. **À manipuler :** le bouton donne un ordre dans lequel exécuter les étapes. ```sq-graphe-dessin titre: Graphe orienté sans circuit arêtes: A>B, A>C, B>D, C>E, E>D positions: A:50,120; B:190,55; C:150,190; E:270,190; D:330,90 ordre: topologique ``` ## Graphe pondéré Un **graphe pondéré** associe un nombre, le **poids**, à chaque arête. Le poids représente par exemple une distance ou une durée. Un graphe peut être à la fois orienté et pondéré. **À manipuler :** le bouton passe du graphe non orienté au graphe orienté. ```sq-graphe-dessin titre: Graphe de référence pondéré arêtes: A-B:12.3, B-F:6.1, C-D:4.2, C-E:17.0, C-F:9.8, D-E:3.3, F-G:6.2, F-A:14.5, G-D:10.6 bascule: oui ``` ## Pour vérifier ```sq-cartes sommet :: un élément du graphe arête :: un lien entre deux sommets chemin :: une suite d'arêtes qui relie deux sommets graphe connexe :: deux sommets quelconques sont reliés par un chemin degré d'un sommet :: le nombre de ses voisins arbre :: un graphe connexe sans cycle arbre couvrant :: un arbre qui relie tous les sommets du graphe circuit :: un chemin orienté qui revient à son départ ``` %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] > > | | [[Code et Développement/Programmation/Graphes/02_Représentation en Python\|Représentation en Python →]] | > |:---|---:| %% nav-fin %%