ATLAS
Ouvrir dans l'atlas →AnnalesEnseignement
Agrégation interne 2019 — Épreuve 1
Le sujet étudie un graphe fini à travers sa matrice d'adjacence. Il encadre les valeurs propres de matrices symétriques par blocs pour minorer le nombre chromatique par , démontre le théorème des arbres de Kirchhoff (le nombre d'arbres couvrants est un cofacteur de la matrice laplacienne) via la formule de Binet-Cauchy, calcule des groupes d'automorphismes de graphes par une action sur les 3-arcs, et majore le diamètre d'un graphe régulier connexe à l'aide de la deuxième valeur propre.
Le sujet, partie par partie
Notations et Partie I — Spectre d'un graphe et nombre chromatique p. 5–8
Théorie spectrale des graphes · Quotient de Rayleigh et Courant-Fischer · Théorème spectral · Matrices par blocs · Matrices symétriques positives — matrice d'adjacence, graphe biparti complet, quotient de Rayleigh, coloriage d'un graphe, nombre chromatique, graphe de Schläfli
Partie II — Nombre d'arbres couvrant un graphe p. 8–11
Théorie spectrale des graphes · Déterminants · Applications linéaires et rang · Matrices par blocs · Polynômes — théorème des arbres de Kirchhoff, formule de Binet-Cauchy, matrice d'incidence, matrice laplacienne, comatrice, mineurs principaux, composantes connexes
Partie III — Exemples de groupes d'automorphismes p. 12–13
Actions de groupes · Groupe symétrique · Groupes · Graphes · Dénombrement et combinatoire — automorphisme de graphe, orbite, formule orbite-stabilisateur, générateurs d'un groupe, sous-groupe d'indice 2, groupe simple
Partie IV — Une majoration du diamètre d'un graphe p. 13–14
Théorie spectrale des graphes · Matrices positives et stochastiques · Théorème spectral · Inégalité de Cauchy-Schwarz · Dénombrement de configurations — graphe régulier, diamètre d'un graphe, puissances de la matrice d'adjacence, nombre de chemins, deuxième valeur propre, base orthonormée de vecteurs propres