Aller au contenu

Définitions (Bac 🎯)⚓︎

Licence Creative Commons
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.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 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é.

alt

Une représentation de graphe non orienté pondéré.

alt

Une représentation de graphe orienté.

alt

Une représentation de graphe orienté pondéré.

alt

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

alt

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

alt

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

alt

💡 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 distinctes
  • 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.

alt

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 : on peut penser à des problèmes d'allocations des processeurs à des processus dans un ordinateur multiprocesseur.

💡 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 les sommets sont les cases vides, 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.

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

alt

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 parlere 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 représenté 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.

alt

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é.

alt

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

alt

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.

alt

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.

alt

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.

alt

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.

alt

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.

alt

Dans le graphe orienté ci-dessous, le degré entrant du sommet 2 est de un et son degré sortant est de deux.

alt

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
  • le nombre de chemins simples entre le sommet C et le sommet G

alt

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
    • F - E - G - F
  • Il existe six 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

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

alt

Crédit : Cédric Gouygou

  • 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 F :
    • 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 sommmets 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).

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

alt

Graphe non orienté connexe avec 4 sommets et un nombre minimal d'arêtes 3.

alt

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.