L'essentiel à connaître
La théorie des graphes est une branche fondamentale de l'informatique et des mathématiques discrètes servant à modéliser des réseaux (sociaux, routiers, informatiques). Un graphe G est composé d'un ensemble de sommets et d'un ensemble d'arêtes (ou arcs si le graphe est orienté) reliant ces sommets. Pour manipuler ces structures informatiquement, on utilise souvent une matrice d'adjacence : une matrice carrée où l'élément à la ligne i et colonne j indique la présence d'une liaison entre le sommet i et le sommet j.
L'analyse d'un graphe passe par l'étude de sa connexité. Un graphe est dit connexe si chaque paire de sommets peut être reliée par une chaîne. Dans le cas des graphes orientés, on parle de forte connexité si l'on peut aller de n'importe quel sommet à n'importe quel autre en suivant le sens des arcs. L'exploration de ces structures se fait via des algorithmes de parcours, principalement le parcours en largeur (BFS) et le parcours en profondeur (DFS).
Définition : La matrice d'adjacence d'un graphe non orienté à n sommets est une matrice symétrique de taille n x n où A_ij = 1 si une arête existe, 0 sinon.
À retenir : La puissance k-ième de la matrice d'adjacence donne le nombre de chemins de longueur k entre deux sommets.
Les points clés
Il est crucial de savoir choisir entre une matrice d'adjacence et une liste d'adjacence. La matrice est très efficace pour vérifier rapidement l'existence d'une arête, mais elle consomme beaucoup de mémoire pour les graphes "creux" (peu d'arêtes). À l'inverse, la liste d'adjacence est préférable pour les graphes de grande taille avec peu de connexions.
Les parcours BFS et DFS ont des comportements très différents : le BFS utilise une file (FIFO) et permet de trouver le chemin le plus court dans un graphe non pondéré, tandis que le DFS utilise une pile (LIFO) et est idéal pour détecter des cycles ou tester la connectivité. Attention aux pièges : dans un graphe orienté, la matrice d'adjacence n'est généralement pas symétrique, car l'existence d'un arc de i vers j n'implique pas celle d'un arc de j vers i.
Formule : Degré d'un sommet d(v) = somme des éléments de la ligne correspondante dans la matrice d'adjacence (pour un graphe non orienté).
Piège classique : Ne pas confondre une chaîne (graphe non orienté) et un chemin (graphe orienté), les règles de parcours et de connexité en dépendent.
Quiz : Teste tes connaissances
Question 1 : Dans un graphe non orienté, comment est toujours la matrice d'adjacence ?
Réponse : C. Puisque l'arête (i, j) est identique à (j, i), l'élément A_ij est égal à A_ji. La matrice est donc le miroir d'elle-même par rapport à sa diagonale principale.
Question 2 : Quel algorithme de parcours utilise une file (FIFO) ?
Réponse : B. Le parcours en largeur (Breadth-First Search) explore les voisins niveau par niveau en utilisant une file pour mémoriser les sommets à visiter prochainement.
Question 3 : Que représente l'élément (i, j) de la matrice A² (A au carré) ?
Réponse : D. C'est une propriété majeure des matrices d'adjacence. La puissance k de la matrice donne le nombre de chemins de longueur exactement k entre les sommets.
Question 4 : Un graphe sans cycle est appelé :
Réponse : A. Un arbre est un graphe connexe et acyclique. S'il n'est pas connexe mais toujours acyclique, on l'appelle une forêt.
Question 5 : Quel est le nombre maximum d'arêtes dans un graphe simple non orienté à n sommets ?
Réponse : B. Dans un graphe complet K_n, chaque sommet est relié à tous les autres. Le calcul est la combinaison de 2 parmi n, soit n(n-1)/2.
Question 6 : Dans une matrice d'adjacence, que signifie une valeur sur la diagonale principale ?
Réponse : C. Un élément A_ii non nul signifie qu'il existe une arête (ou un arc) partant du sommet i et revenant sur lui-même. C'est ce qu'on appelle une boucle.
Question 7 : La forte connexité concerne :
Réponse : D. Un graphe orienté est fortement connexe si pour tout couple de sommets (u, v), il existe un chemin de u vers v ET un chemin de v vers u.
Question 8 : Quel parcours est le plus adapté pour trouver le plus court chemin (en nombre d'arêtes) ?
Réponse : A. Le BFS explore par cercles concentriques. Le premier chemin trouvé vers une destination est donc forcément celui qui comporte le moins d'étapes (arêtes).
Question 9 : Si un graphe a n sommets et n-1 arêtes et qu'il est connexe, c'est :
Réponse : B. C'est l'une des définitions équivalentes d'un arbre. Le nombre minimal d'arêtes pour lier n sommets est n-1, et rajouter une arête créerait forcément un cycle.
Question 10 : Quel est l'inconvénient majeur de la matrice d'adjacence ?
Réponse : C. Même si le graphe n'a que deux arêtes, une matrice n x n occupera n² cases. Pour un million de sommets, c'est impossible à stocker en mémoire vive standard.
Question 11 : Comment appelle-t-on un sommet qui n'est relié à aucun autre ?
Réponse : B. Un sommet isolé a un degré de 0. Dans la matrice d'adjacence, sa ligne et sa colonne ne contiennent que des zéros.
Question 12 : Dans un graphe complet à 4 sommets, quel est le degré de chaque sommet ?
Réponse : A. Dans un graphe complet K_n, chaque sommet est relié à tous les autres sauf lui-même. Son degré est donc n - 1, ici 4 - 1 = 3.
Question 13 : Quel est l'ordre de complexité en temps d'un parcours BFS sur un graphe (V, E) avec listes d'adjacence ?
Réponse : D. On visite chaque sommet une fois et on examine chaque arête une fois. C'est une complexité linéaire par rapport à la taille de la structure.
Question 14 : Un graphe biparti est un graphe où :
Réponse : C. Dans un graphe biparti, on peut colorer les sommets en deux couleurs telles que deux sommets de même couleur ne soient jamais reliés.
Question 15 : Quel concept permet de modéliser les relations asymétriques (ex: A suit B sur Twitter) ?
Réponse : B. Le graphe orienté utilise des arcs (flèches) pour indiquer un sens unique de relation, ce qui est parfait pour les réseaux sociaux ou les liens hypertextes.
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 !