L'essentiel à connaître
Un graphe est un modèle mathématique composé d'un ensemble de points appelés sommets (ou nœuds) et de liens entre ces points appelés arêtes. Si les liens ont un sens (une flèche), on parle d'un graphe orienté et les liens sont alors nommés arcs. Les graphes permettent de représenter des structures variées : un réseau d'amis sur Facebook, les liaisons aériennes entre des villes ou encore l'organisation des pages web liées par des hyperliens.
Pour exploiter un graphe, il faut savoir le parcourir, c'est-à-dire visiter ses sommets de manière systématique. Il existe deux méthodes fondamentales : le parcours en largeur (BFS - Breadth First Search) qui explore étage par étage autour du sommet de départ, et le parcours en profondeur (DFS - Depth First Search) qui s'enfonce le plus loin possible dans une branche avant de revenir en arrière (backtracking). Ces algorithmes sont la base de problèmes plus complexes comme la recherche du plus court chemin.
Définition : Un graphe est dit "connexe" s'il existe toujours une chaîne (un chemin) permettant de relier n'importe quelle paire de sommets du graphe.
À retenir : Le degré d'un sommet correspond au nombre d'arêtes qui lui sont incidentes. Dans un graphe orienté, on distingue le degré entrant et le degré sortant.
Les points clés
L'une des notions cruciales est la représentation informatique du graphe. On utilise principalement la matrice d'adjacence (un tableau à deux dimensions très pratique pour les graphes denses) ou la liste d'adjacence (plus efficace en mémoire pour les graphes creux où peu de sommets sont reliés). Le choix de la structure impacte directement la performance de tes algorithmes de parcours et de recherche.
Les graphes peuvent aussi être "pondérés", ce qui signifie que chaque arête possèd'une valeur (un poids), représentant par exemple une distance, un coût ou un temps de trajet. C'est ici qu'interviennent des algorithmes célèbres comme celui de Dijkstra pour trouver le chemin le moins coûteux entre deux points, une technologie utilisée quotidiennement par tous les systèmes de navigation GPS.
Formule : Dans un graphe non orienté, la somme des degrés de tous les sommets est égale à deux fois le nombre d'arêtes.
Piège classique : Confondre un cycle et une chaîne simple. Un cycle est une chaîne dont les sommets de départ et d'arrivée sont identiques, sans repasser deux fois par la même arête.
Quiz : Teste tes connaissances
Question 1 : Comment appelle-t-on un lien dans un graphe orienté ?
Réponse : C. Dans la terminologie des graphes, on utilise le mot "arête" pour les graphes non orientés (relation symétrique) et "arc" pour les graphes orientés (relation avec un sens, du sommet origine vers le sommet destination).
Question 2 : Quel algorithme utilise une file (FIFO) pour explorer les sommets niveau par niveau ?
Réponse : A. Le BFS (Breadth First Search) explore d'abord tous les voisins directs d'un sommet avant de passer aux voisins des voisins. Pour garantir cet ordre "en couche", on utilise une structure de file (First In, First Out).
Question 3 : Qu'est-ce qu'un graphe "complet" ?
Réponse : B. Dans un graphe complet (noté Kn pour n sommets), il existe une arête entre chaque paire de sommets distincts. C'est le niveau maximal de densité pour un graphe simple.
Question 4 : Quel type de structure est idéal pour représenter un graphe "creux" (très peu d'arêtes par rapport au nombre de sommets) ?
Réponse : D. La liste d'adjacence ne stocke que les liens existants. Pour un graphe creux, elle économise énormément de mémoire par rapport à une matrice qui stockerait une majorité de zéros inutilement.
Question 5 : Comment appelle-t-on un graphe connexe sans cycle ?
Réponse : B. Un arbre est une structure fondamentale en informatique. S'il n'est pas connexe mais reste sans cycle, on l'appelle alors une "forêt". L'arbre possède toujours n-1 arêtes pour n sommets.
Question 6 : Quel parcours est naturellement implémenté via la récursivité ?
Réponse : C. Le DFS (Depth First Search) utilise une structure de pile. La récursivité utilisant la pile d'exécution du système, elle permet d'écrire un DFS de manière très concise et élégante.
Question 7 : Dans un graphe orienté, si un sommet possèd'un degré entrant de 0, on dit que c'est :
Réponse : A. Une source est un sommet dont aucun arc ne provient d'un autre sommet. À l'inverse, un sommet avec un degré sortant de 0 est appelé un "puits".
Question 8 : L'algorithme de Dijkstra sert à trouver :
Réponse : C. Dijkstra est l'algorithme de référence pour le plus court chemin dans un graphe pondéré avec des poids positifs. Il est à la base de la navigation moderne.
Question 9 : Qu'est-ce qu'un graphe biparti ?
Réponse : D. C'est un concept clé pour les problèmes d'appariement (matching), comme affecter des tâches à des travailleurs ou des étudiants à des écoles.
Question 10 : Quelle est la complexité d'un parcours (BFS ou DFS) utilisant une liste d'adjacence pour un graphe G(V, E) ?
Réponse : A. Le parcours visite chaque sommet (|V|) et chaque arête (|E|) exactement une fois. C'est une complexité linéaire par rapport à la taille de la structure, ce qui est très performant.
Question 11 : Un cycle eulérien est un cycle qui passe par :
Réponse : B. Attention au piège ! Le cycle qui passe par chaque sommet est un cycle "Hamiltonien". Le cycle "Eulérien" concerne les arêtes (c'est le fameux problème des ponts de Königsberg résolu par Euler).
Question 12 : Dans quel cas un graphe non orienté admet-il un cycle eulérien ?
Réponse : C. C'est le théorème d'Euler. Si un seul sommet a un degré impair, tu ne peux pas revenir au point de départ en ayant parcouru toutes les arêtes sans en emprunter une deux fois.
Question 13 : Quel problème concret peut être modélisé par un graphe ?
Réponse : D. Les graphes sont universels. Ils servent à l'ordonnancement (graphes de dépendance), à la logistique (plus court chemin) et à l'analyse de réseaux (graphes sociaux).
Question 14 : Que représente la "densité" d'un graphe ?
Réponse : B. Un graphe dense a beaucoup d'arêtes (proche d'un graphe complet), tandis qu'un graphe creux en a peu. Cela oriente le choix des algorithmes et des structures de données.
Question 15 : Lequel de ces graphes est obligatoirement planaire (peut être dessiné sans que les arêtes se croisent) ?
Réponse : A. Un arbre n'a pas de cycles, il peut donc toujours être dessiné sur un plan sans croisement d'arêtes. K5 et K3,3 sont les exemples classiques de graphes non planaires (théorème de Kuratowski).
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
- Générateur de Mind Maps : visualise et organise tes idées avec des cartes mentales générées automatiquement.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !