Graphes et matrice d'adjacence

🟠 Difficile

Les é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
On considère le graphe de sommets A, B et C dont les seules arêtes sont AB et BC. Détermine le nombre de chemins de longueur 2 allant de A à C.
Voir le corrigéoffert
Un chemin de longueur 2 de A vers C doit passer par un sommet intermédiaire relié aux deux.
Seul B convient, et le chemin A puis B puis C existe bien.
Il y a donc exactement 1 chemin de longueur 2 de A à C. On le retrouve en calculant le carré de la matrice d'adjacence, dont le coefficient de la première ligne et de la troisième colonne vaut 1.
2
On reprend le graphe de sommets A, B et C d'arêtes AB et BC. Calcule le carré de sa matrice d'adjacence.
Voir le corrigéoffert
La matrice est $M = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ .
En effectuant le produit de $M$ par elle-même, on trouve $M^{2} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ .
Le coefficient central vaut 2 : depuis B, il y a deux allers-retours de longueur 2, l'un par A et l'autre par C.
3
Explique pourquoi un coefficient de la diagonale du carré de la matrice d'adjacence donne le degré du sommet correspondant, dans un graphe non orienté sans boucle.
🔒 Corrigé réservé aux abonnésS'abonner →
4
Un graphe orienté a pour sommets A, B et C, et pour seuls arcs celui de A vers B, celui de B vers C et celui de C vers A. Écris sa matrice d'adjacence.
🔒 Corrigé réservé aux abonnésS'abonner →
5
Dans le graphe triangle de sommets A, B et C, où chaque sommet est relié aux deux autres, détermine le nombre de chemins de longueur 2 reliant A à B.
🔒 Corrigé réservé aux abonnésS'abonner →
6
Explique comment utiliser les puissances de la matrice d'adjacence pour savoir si deux sommets peuvent être reliés par un chemin.
🔒 Corrigé réservé aux abonnésS'abonner →
7
Détermine la somme de tous les coefficients de la matrice d'adjacence d'un graphe non orienté possédant 7 arêtes et aucune boucle.
🔒 Corrigé réservé aux abonnésS'abonner →
8
Un graphe non orienté a pour matrice d'adjacence $\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ . Dis s'il est connexe, en justifiant.
🔒 Corrigé réservé aux abonnésS'abonner →
9
On considère le graphe triangle de sommets A, B et C. Détermine le nombre de chemins de longueur 3 allant de A à A.
🔒 Corrigé réservé aux abonnésS'abonner →
10
Explique pourquoi une boucle sur un sommet se traduit par un coefficient non nul sur la diagonale de la matrice d'adjacence.
🔒 Corrigé réservé aux abonnésS'abonner →

Comment ça s'est passé ?

Retrouve tout dans Mon suivi.

← Changer de niveau