Quiz HARD — Graphes (20 questions)
Matrices d’adjacence • puissances • chemins • accessibilité • interprétation Bac
Q2. Dans un graphe orienté à 5 sommets, que représente le coefficient \(a_{ij}\) de la matrice d’adjacence ?
Non vérifié
Indice
Ligne = départ, colonne = arrivée.
Correction
Par définition, \(a_{ij}=1\) s’il existe un arc allant du sommet \(i\) vers le sommet \(j\), et 0 sinon.
Q3. Dans un graphe non orienté, la matrice d’adjacence est toujours :
Non vérifié
Indice
Comparer \(a_{ij}\) et \(a_{ji}\).
Correction
Dans un graphe non orienté, \(\{i,j\}=\{j,i\}\), donc \(a_{ij}=a_{ji}\) : la matrice est symétrique.
Q4. Dans un graphe orienté, le degré sortant d’un sommet correspond :
Non vérifié
Indice
Penser aux arcs qui partent du sommet.
Correction
Les arcs sortants partent du sommet : ils apparaissent sur la ligne correspondante de la matrice.
Q5. Dans un graphe non orienté ayant \(m\) arêtes, que vaut la somme des degrés ?
Non vérifié
Indice
Chaque arête touche deux sommets.
Correction
Chaque arête est comptée deux fois dans la somme des degrés, donc \(\sum \deg = 2m\).
Q6. Que représente le coefficient \((A^2)_{ij}\) ?
Non vérifié
Indice
Interprétation fondamentale des puissances.
Correction
Le coefficient \((A^2)_{ij}\) donne exactement le nombre de chemins de longueur 2 allant de \(i\) vers \(j\).
Q7. Si \((A^2)_{3,5}=0\), que peut-on conclure ?
Non vérifié
Indice
Zéro signifie absence totale.
Correction
Un coefficient nul signifie qu’il n’existe aucun chemin de la longueur considérée entre ces deux sommets.
Q8. Dans un graphe à \(n\) sommets, \((A^k)_{ij}\) correspond :
Non vérifié
Indice
Remplacer 2 par k.
Correction
Plus généralement, \((A^k)_{ij}\) compte les chemins de longueur \(k\) de \(i\) vers \(j\).
Q9. Si un sommet possède une boucle \((i\to i)\), alors :
Non vérifié
Indice
Répéter la boucle.
Correction
Une boucle permet de rester sur le sommet, ce qui crée des chemins de toutes longueurs revenant en \(i\).
Q10. Erreur classique : confondre \((A^2)_{ij}\) avec :
Non vérifié
Indice
Chemins ≠ arcs.
Correction
\((A^2)_{ij}\) ne décrit pas un arc direct, mais des chemins de longueur 2.
Q11. Dans un graphe orienté, si \(a_{ij}=1\), peut-on conclure que \(a_{ji}=1\) ?
Non vérifié
Indice
Orientation.
Correction
En orienté, \(i\to j\) n’implique pas \(j\to i\).
Q12. Dire que le sommet \(j\) est accessible depuis \(i\) signifie :
Non vérifié
Indice
Notion de chemin.
Correction
L’accessibilité correspond à l’existence d’au moins un chemin reliant \(i\) à \(j\).
Q13. Un graphe orienté est fortement connexe si :
Non vérifié
Indice
Aller-retour entre tous les sommets.
Correction
Par définition, un graphe orienté est fortement connexe si chaque sommet peut atteindre tous les autres.
Q14. Dans une modélisation par graphe, les sommets représentent le plus souvent :
Non vérifié
Indice
Processus discret.
Correction
Dans les modèles de processus, les sommets correspondent aux états du système.
Q15. Les arcs d’un graphe modélisant un processus représentent :
Non vérifié
Indice
Passage d’un état à un autre.
Correction
Chaque arc indique une transition possible entre deux états.
Q16. Si \((A^3)_{ij}>0\), que peut-on affirmer ?
Non vérifié
Indice
Interprétation directe.
Correction
Un coefficient strictement positif garantit l’existence d’au moins un chemin de longueur 3.
Q17. Dans un graphe non orienté, que vaut \((A^2)_{ii}\) ?
Non vérifié
Indice
Départ = arrivée.
Correction
\((A^2)_{ii}\) compte les chemins de longueur 2 qui partent de \(i\) et reviennent en \(i\).
Q18. Vrai ou faux : si \((A^2)_{ij}=0\), alors il n’existe aucun chemin de \(i\) vers \(j\).
Non vérifié
Indice
Penser aux longueurs > 2.
Correction
Il peut exister un chemin de longueur 3 ou plus.
Q19. Vrai ou faux : la matrice d’adjacence suffit à étudier l’accessibilité dans un graphe.
Non vérifié
Indice
Via les puissances.
Correction
Les puissances successives de la matrice permettent d’étudier l’accessibilité.
Q20. Compléter : « \((A^k)_{ij}\) est égal à … »
Non vérifié
Indice
Phrase clé du chapitre.
Correction
C’est LA phrase à connaître par cœur pour le Bac Maths Expertes.
Q21. Pour résoudre un exercice Bac sur les graphes, la bonne démarche est :
Non vérifié
Indice
Ordre logique.
Correction
On modélise par un graphe, on traduit en matrice, puis on interprète algébriquement.
Clavier