Graphes et matrice d'adjacence
🔴 ExpertLes énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres suivent l'accès à la famille « Matrices, graphes et chaînes de Markov ».
- 1
Démontre que le coefficient de la ligne et de la colonne du carré de la matrice d'adjacence donne le nombre de chemins de longueur 2 du sommet au sommet .
Voir le corrigéoffert
Par définition du produit, ce coefficient vaut la somme, pour tous les sommets , des produits du coefficient de la ligne et de la colonne par celui de la ligne et de la colonne .
Chacun de ces produits vaut 1 si les deux liaisons existent, et 0 sinon : il vaut donc 1 exactement lorsque le chemin passant par est possible.
La somme compte ainsi le nombre de sommets intermédiaires utilisables, c'est-à-dire le nombre de chemins de longueur 2.
Le même raisonnement, répété de proche en proche, montre que la puissance d'exposant compte les chemins de longueur . - 2
Démontre que la somme des degrés des sommets d'un graphe est toujours un nombre pair.
Voir le corrigéoffert
Chaque arête possède deux extrémités, et elle ajoute 1 au degré de chacune d'elles.
La somme des degrés vaut donc le double du nombre d'arêtes.
Un double étant toujours pair, la somme des degrés est paire.
Ce résultat porte le nom de lemme des poignées de main : dans une assemblée, la somme des nombres de mains serrées par chacun est nécessairement paire, puisque chaque poignée de main est comptée deux fois. - 3
Démontre qu'il n'existe aucun graphe possédant 5 sommets dont tous les degrés valent 3.
🔒 Corrigé réservé aux abonnésS'abonner → - 4
Écris la matrice d'adjacence du graphe complet à 4 sommets, puis calcule son carré et interprète les coefficients obtenus.
🔒 Corrigé réservé aux abonnésS'abonner → - 5
Explique comment la somme de la matrice d'adjacence et de ses premières puissances permet de décider si un graphe est connexe.
🔒 Corrigé réservé aux abonnésS'abonner → - 6
Dans un graphe orienté, explique ce que compte la somme des coefficients de la diagonale du cube de la matrice d'adjacence.
🔒 Corrigé réservé aux abonnésS'abonner → - 7
Un graphe non orienté est connexe et tous ses sommets ont pour degré 2. Démontre qu'il s'agit nécessairement d'un cycle.
🔒 Corrigé réservé aux abonnésS'abonner → - 8
Explique pourquoi deux dessins très différents peuvent représenter le même graphe, et comment la matrice d'adjacence permet de le vérifier.
🔒 Corrigé réservé aux abonnésS'abonner → - 9
Dans un réseau de 4 villes, on souhaite savoir combien de trajets de longueur 2 relient deux villes données. Explique pourquoi un calcul matriciel est préférable à un dénombrement à la main.
🔒 Corrigé réservé aux abonnésS'abonner → - 10
Explique pourquoi le nombre de chemins de longueur entre deux sommets d'un graphe connexe augmente très vite avec .
🔒 Corrigé réservé aux abonnésS'abonner →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.