Définitions (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le cours de Gilles Lassus
- le cours de Cédric Gouygou
🔖 Synthèse de ce qu'il faut retenir pour le bac
Notion de graphe⚓︎
Point de cours 1 : définition d'un graphe
Un graphe est un ensemble d'objets appelés sommets dont certains reliés deux à deux par des liaisons appelées arcs.
En général on associe une étiquette ou nom à chaque sommet.
Il existe deux grandes familles de graphes :
- si les arcs peuvent être orientés on parle de graphe orienté
- sinon de graphe non orienté.
On peut aussi associer une étiquette, en général une valeur numérique appelée poids, à chaque arc : dans ce cas on parle de graphe pondéré (qui peut être orienté ou non).
Conventions de représentation graphique :
| Type de graphe | Sommet | Arc |
|---|---|---|
| Non orienté | Disque avec étiquette | i - jreprésenté par un segment |
| Orienté | Disque avec étiquette | i -> jreprésenté par une flèche orientée |
Une représentation de graphe non orienté.
Une représentation de graphe non orienté pondéré.
Une représentation de graphe orienté.
Une représentation de graphe orienté pondéré.
Modélisation par un graphe
💡 Les graphes étant des objets mathématiques abstraits, on a pu développer de nombreux algorithmes sur les graphes. En modélisant une situation par un graphe, on peut traduire un problème concret comme un problème sur un graphe, qu'on résout avec un algorithme de graphe.
Routage dans un réseau informatique et plus court chemin dans un graphe
Le réseau informatique ci-dessus peut être modélisé par un graphe non orienté dont les sommets sont les routeurs, switchs ou ordinateurs, et les arcs sont les liaisons.
| Problème dans la situation modélisée | Problème sur le graphe | Algorithme de graphe |
|---|---|---|
| Rechercher la route la plus courte pour acheminer un paquet de Alice vers Bob (protocole de routage RIP) | Recherche de plus court chemin en nombre d'arcs du sommet "Alice" vers le sommet "Bob" | Algorithme de parcours en largeur |
Si on tient compte de la bande passante de chaque liaison on peut modéliser le réseau par un graphe non orienté pondéré dont les sommets sont les routeurs, switchs ou ordinateurs, et les arcs sont les liaisons, étiquetés par un poids inversement proportionnel à la bande passante.
| Problème dans la situation modélisée | Problème sur le graphe | Algorithme de graphe |
|---|---|---|
| Rechercher la route la moins coûteuse pour acheminer un paquet de Alice vers Bob (protocole de routage OSPF) | Recherche de plus court chemin en coût total du chemin du sommet "Alice" vers le sommet "Bob" | Algorithme de Dijkstra |
💡 On retrouve le problème de recherche de plus court chemin dans un graphe dans d'autres domaines : réseau routier, d'électricité etc ...
Allocation de ressources et coloration de graphe
Chaque élève de terminale suit deux spécialités parmi huit : ["PHYSIQUE-CHIMIE", "MATHEMATIQUES", "SCIENCES VIE & TERRE", "SC. ECONO.&SOCIALES", "NUMERIQUE SC.INFORM.", "HIST.GEO.GEOPOL.S.P.", "HUMAN.LITTER.PHILO.", "LLC ANGL.MOND.CONT."].
On veut déterminer le nombre minimal de demi-journées nécessaires pour organiser un bac blanc avec un seul sujet par spécialité. Pour celà on modélise les spacialités choisies par les élèves par un graphe de contraintes :
- chaque spécialité est l'étiquette d'un sommet
- on relie deux spécialités par un arc si au moins un élève suit ces deux spécialités
Le problème posé peut alors se traduire en un problème de coloration de graphe :
- chaque demi-journée est une couleur distincte
- on recherche le nombre minimum de couleurs pour colorier tous les sommets du graphe en respectant la contrainte que deux sommets reliés par un arc ne soient pas coloriés avec la même couleur.
| Problème dans la situation modélisée | Problème sur le graphe | Algorithme de graphe |
|---|---|---|
| Nombre minimum de demi-journées pour organiser le bac blanc | Nombre minimal de couleurs pour colorier les sommets du graphes. | Algorithme glouton de coloration de graphe |
Les problèmes d'allocation de ressources peuvent être ainsi modélisés par des problèmes de coloration de graphe. L'article de Wikipedia sur la coloration de graphe cite le problème d'allocation de fréquences dans certains réseaux de télécommunication composés d'émetteurs émettant chacun sur une fréquence particulière. Lorsque deux émetteurs sont trop proches on ne peut leur allouer la même fréquence à cause des interférences.
💡 De nombreux autres problèmes peuvent être modélisés par un problème de coloration de graphe comme par exemple la résolution d'une grille incomplète de Sudoku. Dans ce cas les sommets sont les cases, les arcs de contraintes relient les cases d'une même ligne, même colonne ou d'un même bloc et cette fois on recherche une coloration avec exactement 9 couleurs codant les chiffres de 1 à 9 (une grille incomplète étant un graphe étant partiellement coloré)
Réseau social et existence de chemin dans un graphe
Un réseau social peut être modélisé par un graphe dont les sommets sont les individus et les arcs les relations de "suivi" :
- Le graphe peut être non orienté comme pour Facebook : une personne que je suis me suit forcément
- Le graphe peut être orienté comme pour Twitter : une personne que je suis ne me suit pas forcément
Dans un réseau social, on peut se demander s'il existe une séquence de relations permettant de relier un individu A à un individu B. Dans le graphe, on parlera de l'existence d'un chemin reliant le sommet étiqueté "Individu A" au sommet étiqueté "Individu B". Par ailleurs un ensemble de sommets qui sont tous reliés deux à deux par au moins un chemin, constitue une composante connexe du graphe, qui peut représenter une communauté ou bulle algorithmique dans un réseau social.
| Problème dans la situation modélisée | Problème sur le graphe | Algorithme de graphe |
|---|---|---|
| Existence d'un chemin dans le réseau social entre deux individus | Recherche d'un chemin entre deux sommets | Parcours en profondeur DFS, ou parcours en largeur BFS |
💡 Le problème de l'existence d'un chemin dans un graphe se retrouve dans de nombreux autres domaines : raccordement d'un terminal à un réseau informatique, d'électricité, de transports etc ...
Dépendances dans un projet informatique et détection de cycles dans un graphe
Un projet informatique en Python peut être constitué de multiples modules dont certains dépendent d'autres modules. On peut modéliser cette situation par un graphe orienté où un sommet est un module et un arc relie le sommet étiqueté "module A" au sommet étiqueté "module B" si le module B dépend du module A. On peut avoir un problème en cas de dépendances circulaires, ce qui se traduit par l'existence d'un cycle dans le graphe. On peut alors appliquer un algorithme de détection de cycles.
| Problème dans la situation modélisée | Problème sur le graphe | Algorithme de graphe |
|---|---|---|
| Recherche de dépendances cycliques | Recherche de cycle dans un graphe orienté | Détection de cycles |
Le graphe orienté ci-dessous présente un cycle.
Planification de tâches et ordre topologique des sommets d'un graphe
Un professeur d'informatique doit construire une progression à partir de modules d'enseignement dont un graphe orienté de précédence est donné ci-dessous.
Chaque sommet est un module d'enseignement et un arc relie le sommet étiqueté "module A" au sommet étiqueté "module B" si le module A doit être traité avant le module B.
Le problème qui se pose au professeur est donc un problème d'ordonnancement / tri : dans quel ordre peut-il traiter les modules pour respecter les contraintes ? Un ordonnancement des étiquettes de sommets respectant les contraintes de précédence est un ordre topologique du graphe orienté.
Une solution existe si le graphe est sans cycle et elle est donnée par un parcours en profondeur du graphe (DFS) permettant d'énumérer les sommets dans un ordre topologique : chaque sommet est nommé avant tous les sommets atteignables depuis lui.
| Problème dans la situation modélisée | Problème sur le graphe | Algorithme de graphe |
|---|---|---|
| Ordonner des modules d'enseignement | Recherche d'un ordre tolpologique sur les étiquettes de sommets | Parcours en profondeur DFS |
Sur le graphe précédent une solution possible est donnée ci-dessous en plaçant les sommets dans l'ordre topolgique de gauche à droite.
analyse -> algèbre linéaire -> informatique commune -> programmation avancée -> informatique théorique -> bases de données -> calcul scientifique -> bioinformatique -> intelligence artificielle -> apprentissage machine -> robotique -> réseaux de neurones
Vocabulaire des graphes⚓︎
Point de cours 2 : vocabulaire des graphes
Sauf mention explicite, les définitions suivantes sont valables pour les graphes orientés ou non orientés. Dans les exemples, pour simplifier on assimile un sommet à son étiquette (qui ici est un entier).
Un graphe est un ensemble de sommets et d'arcs⚓︎
Un graphe est défini par un ensemble V de sommets (vertices en anglais) et un ensemble E d'arcs (edges en anglais) qui sont des couples de sommets.
Les arcs peuvent être orientés ou non orientés.
Un arc est une relation d'adjacence entre deux sommets⚓︎
Si un arc a pour origine le sommet \(x\) et pour extrémité le sommet \(y\), on dit que :
- \(y\) est adjacent à \(x\) ou que \(y\) est un voisin de \(x\).
- \(y\) est un successeur de \(x\) et que \(x\) est un prédécesseur de \(y\)
Pour un arc non orienté, on ne distingue pas prédécesseur et successeur et la relation d'adjacence est symétrique : si \(y\) est voisin de \(x\) alors \(x\) est voisin de \(y\).
On note \(x\) -> \(y\) un arc orienté et \(x - y\) un arc non orienté. Pour un arc orienté, on distingue l'arc \(x\) -> \(y\) de l'arc \(y\) -> \(x\).
Exemples
Le sommet 2 est adjacent aux sommets 1, 3 et 4 : il a trois voisins.
Le sommet 2 a deux voisins 3 et 4.
Le sommet 2 est un voisin du sommet 1 mais la réciproque est fausse : l'arc orienté 1 -> 2 définit 1 comme prédécesseur de 2 et 2 comme successeur de 1.
Un chemin est une séquence d'arcs consécutifs⚓︎
Un chemin est une séquence d'arcs consécutifs :
Ainsi le chemin \(x_{0}\) -> \(x_{1}\) -> \(x_{2}\) ... -> \(x_{n}\) part de l'origine \(x_{0}\) puis par le sommet \(x_{1}\), puis le sommet \(x_{2}\) et conduit jusqu'à l'extrémité \(x_{n}\) en suivant des arcs consécutifs.
La longueur d'un chemin est le nombre d'arcs qui le constitue.
Un chemin simple est un chemin sans répétition d'arcs.
Un cycle est un chemin dont l'extrémité coincide avec l'origine.
Exemples
0 - 4 - 3 - 2 - 1 est un chemin de longueur 4 dans le graphe non orienté ci-dessous.
4 - 3 - 2 - 4 est un cycle de longueur 3 dans ce même graphe.
1 -> 2 -> 3 -> 4 - > 0 est un chemin de longueur 4 dans le graphe orienté ci-dessous.
Ce graphe orienté ne contient pas de cycles.
Degré d'un arc⚓︎
Dans un graphe orienté :
- le degré sortant d'un sommet est le nombre d'arcs dont ce sommet est l'origine : c'est le nombre de successeurs de ce sommet
- le degré entrant d'un sommet est le nombre d'arcs dont ce sommet est l'extrémité : c'est le nombre de prédécesseurs de ce sommet
Dans un graphe non orienté, on ne distingue pas degré sortant et degré entrant : le degré d'un sommet est le nombre d'arcs dont il est une extrémité, c'est le nombre de voisins du sommet.
Exemples
Dans le graphe non orienté ci-dessous le degré du sommet 2 est de trois.
Dans le graphe orienté ci-dessous, le degré entrant du sommet 2 est de un et son degré sortant est de deux.
Exercice 1
Question 1
Le World Wide Web peut être modélisé par un graphe :
- Quels objets du Web seront les sommets ? et les arcs ?
- S'agira-t-il d'un graphe orienté ou non orienté ?
Le Web peut être modélisé par un graphe orienté dont les sommets sont les pages Web et les arcs les liens hypertextes pointant d'une page vers une autre (mais il n'existe pas forcément de lien dans l'autre sens c'est pourquoi le graphe est orienté).
Question 2
Dans le graphe non orienté ci-dessous, déterminez :
- le sommet de degré maximal
- le nombre de cycles (minimaux au sens où ils ne contiennent pas un autre cycle)
- le nombre de chemins simples entre le sommet C et le sommet G
Crédit : Cédric Gouygou
- Le sommet de degré maximal est E de degré 4.
- Ce graphe contient trois cycles :
- C - D - B - C
- B - D - E - A - B
- C - B - A - E - D - C
- F - E - G - F
- Il existe huit chemins simples entre le sommet C et le sommet G :
- C - B - A - E - F - G
- C - B - A - E - G
- C - B - D - E - F - G
- C - B - D - E - G
- C - D - E - F - G
- C - D - E - G
- C - D - B - A - E - G
- C - D - B - A - E - F - G
Question 3
Dans le graphe orienté ci-dessous, déterminez :
- le degré entrant du sommet B et le degré sortant du sommet F
- le nombre de cycles
- le nombre de chemins simples d'origine le sommet F et d'extrémité le sommet E
Crédit : Cédric Gouygou
- Le sommet B a pour degré entrant 1 et pour degré sortant 2
- Le sommet F a pour degré sortant 2 et pour degré entrant 1
- Ce graphe orienté contient un seul cycle F -> G -> F.
- Trois chemins simples partent de F et se terminent en E :
- F -> E de longueur 1
- F -> G -> E de longueur 2
- F -> G -> F -> E de longueur 3, notez que les arcs F -> G et G -> F sont bien distincts car le graphe est orienté.
Exercice 2
Nous aurons besoin d'exprimer la performance de nos algorithmes sur les graphes en fonction de paramètres de taille du graphe.
Soit un graphe constitué d'un ensemble V de sommets et E d'arcs, deux paramètres de taille sont importants :
- le nombre de sommets noté |V|
- le nombre d'arcs noté |E|
On considère dans cet exercice un graphe non orienté, dont tous les sommets peuvent être reliés deux à deux par un chemin. Un tel graphe est dit connexe. De plus on fixe comme contrainte qu'un seul arc peut relier deux sommets fixés (pas d'arcs parallèles), on parle alors de gaphe simple.
Question 1
Dessinez un graphe non orienté connexe avec quatre sommets :
- qui comporte un nombre minimal d'arcs
- qui comporte un nombre maximal d'arcs
Graphe non orienté connexe avec 4 sommets et un nombre maximal d'arêtes 3.
Graphe non orienté connexe avec 4 sommets et un nombre minimal d'arêtes 6.
Question 2
Si on note \(n\) = |V| le nombre de sommets et \(m\) = |E| le nombre d'arcs, quelle inégalité est vérifiée par \(m\) ?
- \(n-1 \leqslant m \leqslant n^{2}\)
- \(n-1 \leqslant m \leqslant \frac{n(n-1)}{2}\)
- \(n \leqslant m \leqslant 2^{n}\)
- \(n \leqslant m \leqslant n^{n}\)
Pour un graphe non orienté connexe, avec \(n\) sommets :
- le nombre minimal d'arcs est \(n-1\). Dans ce cas tous les sommets du graphe sont sur un chemin simple non cyclique. Plus précisément un graphe connexe sans cycle, est nécessairement de cette forme, on dit que c'est un arbre.
- le nombre maximal d'arcs est \(\frac{n(n-1)}{2}\), c'est le cas d'un graphe dont tous les sommets sont reliés à tous les autres, un tel graphe est dit complet. Pour un graphe orienté, si on exclut les boucles (arc d'un sommet vers lui-même), ce maximum est \(n(n-1)\).
Un graphe dont le nombre d'arcs est proche du minimum \(n-1\), c'est-à-dire que \(m=O(n)\) est de complexité linéaire par rapport au nombre de sommets, est dit creux (sparse en anglais).
Un graphe dont le nombre d'arcs est proche du maximum \(\frac{n(n-1)}{2}\), c'est-à-dire que \(m=O(n^{2})\) est de complexité quadratique par rapport au nombre de sommets, est dit dense.