Théorie algébrique des graphes

Le graphe de Petersen, qui possède 10 sommets et 15 arêtes. Hautement symétrique, il est en particulier distance-transitif. Son groupe d'automorphisme a 120 éléments et est en fait le groupe symétrique S₅. De diamètre 2, il possède 3 valeurs propres.

En mathématiques, la théorie algébrique des graphes utilise des méthodes algébriques pour résoudre des problèmes liés aux graphes, par opposition à des approches géométriques, combinatoires ou algorithmiques. On distingue trois branches principales au sein de la théorie algébriques des graphes, fondées respectivement sur l'algèbre linéaire, la théorie des groupes et l'étude des invariants de graphe.

Branches de la théorie algébrique des graphes

Algèbre linéaire

Une première approche possible, dite théorie spectrale des graphes, consiste en l'étude des graphes dans le cadre de l'algèbre linéaire. Elle s'intéresse en particulier au spectre des matrices que l'on peut associer à un graphe, comme la matrice d'adjacence ou la matrice laplacienne normalisée. Des relations entre le spectre du graphe et ses propriétés sont établies. Par exemple, un graphe connexe de diamètre D aura au moins D+1 valeurs propres distinctes^[1]. Cette approche est notamment utilisée dans l'étude de la synchronisabilité des réseaux^[2].

Théorie des groupes

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, (t ≥ 2)		symétrique gauche (en)
↓
(si connexe) sommet-transitif et arête-transitif	→	régulier et arête-transitif	→	arête-transitif
↓		↓		↓
sommet-transitif	→	régulier	→	(si biparti) birégulier
↑
graphe de Cayley	←	zéro-symétrique		asymétrique

Une seconde approche est fondée sur la théorie des groupes et étudie les automorphismes de graphe. Cette branche s'intéresse à des ensembles de graphes définis à partir de propriétés de symétrie, tels que les graphes symétriques, les graphes sommet-transitifs, les graphes arête-transitifs, les graphes distance-transitifs, les graphes distance-réguliers ou les graphes fortement réguliers, et aux relations d'inclusion entre ces ensembles.

Le théorème de Frucht affirme par ailleurs que tout groupe peut être vu comme le groupe des automorphismes d'un graphe non orienté connexe^[3], et même d'un graphe cubique^[4]. Un autre lien avec la théorie des groupes sont les graphes de Cayley qui encodent la structure d'un groupe.

Les propriétés de symétrie d'un graphe ont des répercussions sur son spectre. Informellement, un graphe hautement symétrique a peu de valeurs propres distinctes^[5], à l'instar du graphe de Petersen qui en possède 3, ce qui est le minimum pour un graphe de diamètre 2. Le spectre d'un graphe de Cayley peut quant à lui être relié à la structure du groupe et en particulier à ses caractères irréductibles^[6].

Invariants de graphes

Une troisième approche étudie les invariants de graphes comme le polynôme chromatique, qui compte les colorations distinctes d'un graphe, ou le polynôme de Tutte.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Algebraic graph theory » (voir la liste des auteurs).

Références

1. Algebraic Graph Theory, 2^d Edition, p. 10
2. (en) Mauricio Barahona et Louis M. Pecora, « Synchronization in Small-World Systems », Physical Review Letters, vol. 89, n^o 5,‎ 16 juillet 2002 (DOI 10.1103/PhysRevLett.89.054101, arXiv nlin/0112023, lire en ligne, consulté le 2 juillet 2019)
3. (de) Robert Frucht, « Herstellung von Graphen mit vorgegebener abstrakter Gruppe. », Compositio Mathematica, vol. 6,‎ 1939, p. 239–250 (ISSN 0010-437X, zbMATH 0020.07804, lire en ligne).
4. (en) Robert Frucht, « Graphs of degree three with a given abstract group », Canadian Journal of Mathematics, vol. 1,‎ 1949, p. 365–378 (ISSN 0008-414X, DOI 10.4153/CJM-1949-033-6, MR 0032987, lire en ligne).
5. (en) Paul Terwilliger, « Eigenvalue multiplicities of highly symmetric graphs », Discrete Mathematics, vol. 41, n^o 3,‎ 1^er janvier 1982, p. 295–302 (ISSN 0012-365X, DOI 10.1016/0012-365X(82)90025-5, lire en ligne, consulté le 4 juillet 2019)
6. Algebraic Graph Theory, 2^d Edition, p. 128

• Alain Bretto, Alain Faisant et François Hennecart, Elements of Graph Theory: From Basic Concepts to Modern Developments, European Mathematical Society Press, 2022 (ISBN 978-3-98547-017-4, lire en ligne)

Bibliographie

• (en) Norman Biggs, Algebraic Graph Theory, 2^d Edition, Cambridge University Press, 1993, 214 p. (ISBN 978-0-521-45897-9, lire en ligne)