Quiz HARD — Graphes (20 questions)
Matrices d’adjacence • puissances • chemins • accessibilité • interprétation Bac
Exercice 1. 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.
Exercice 2. Dans un graphe non orienté, la matrice d’adjacence est toujours :
Non vérifié
Indice
Comparer \(a_{ij}\) et \(a_{ji}\).
Exercice 3. Dans un graphe orienté, le degré sortant d’un sommet correspond :
Non vérifié
Indice
Penser aux arcs qui partent du sommet.
Exercice 4. 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.
Exercice 5. Que représente le coefficient \((A^2)_{ij}\) ?
Non vérifié
Indice
Interprétation fondamentale des puissances.
Exercice 6. Si \((A^2)_{3,5}=0\), que peut-on conclure ?
Non vérifié
Indice
Zéro signifie absence totale.
Exercice 7. Dans un graphe à \(n\) sommets, \((A^k)_{ij}\) correspond :
Non vérifié
Indice
Remplacer 2 par k.
Exercice 8. Si un sommet possède une boucle \((i\to i)\), alors :
Non vérifié
Indice
Répéter la boucle.
Exercice 9. Erreur classique : confondre \((A^2)_{ij}\) avec :
Non vérifié
Indice
Chemins ≠ arcs.
Exercice 10. Dans un graphe orienté, si \(a_{ij}=1\), peut-on conclure que \(a_{ji}=1\) ?
Non vérifié
Indice
Orientation.
Exercice 11. Dire que le sommet \(j\) est accessible depuis \(i\) signifie :
Non vérifié
Indice
Notion de chemin.
Exercice 12. Un graphe orienté est fortement connexe si :
Non vérifié
Indice
Aller-retour entre tous les sommets.
Exercice 13. Dans une modélisation par graphe, les sommets représentent le plus souvent :
Non vérifié
Indice
Processus discret.
Exercice 14. Les arcs d’un graphe modélisant un processus représentent :
Non vérifié
Indice
Passage d’un état à un autre.
Exercice 15. Si \((A^3)_{ij}>0\), que peut-on affirmer ?
Non vérifié
Indice
Interprétation directe.
Exercice 16. Dans un graphe non orienté, que vaut \((A^2)_{ii}\) ?
Non vérifié
Indice
Départ = arrivée.
Exercice 17. 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.
Exercice 18. Vrai ou faux : la matrice d’adjacence suffit à étudier l’accessibilité dans un graphe.
Non vérifié
Indice
Via les puissances.
Exercice 19. Compléter : « \((A^k)_{ij}\) est égal à … »
Non vérifié
Indice
Phrase clé du chapitre.
Exercice 20. Pour résoudre un exercice Bac sur les graphes, la bonne démarche est :
Non vérifié
Indice
Ordre logique.