Utilisateur:Wattcle/Brouillon

Une page de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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, sur la théorie des groupes et sur l'étude des invariants de graphe.

Branches de la théorie algébrique des graphes[modifier | modifier le code]

Algèbre linéaire[modifier | modifier le code]

Article détaillé : Théorie spectrale des graphes.

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.

Théorie des groupes[modifier | modifier le code]

Une seconde approche est fondée sur la théorie des groupes, le lien étant fait avec 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.

Invariants de graphes[modifier | modifier le code]

Une troisième approche étudie les invariants de graphes comme le polynôme chromatique et le polynôme de Tutte.

Notes et références[modifier | modifier le code]

_______________________________________________________________________________________________________________________________________________________________ _______________________________________________________________________________________________________________________________________________________________

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

En théorie des graphes, un graphe non-orienté est arête-transitif si pour tout couple d'arêtes, il existe un automorphisme de graphe envoyant la première arête sur la seconde[1].

Définitions[modifier | modifier le code]

Un graphe non-orienté est arête-transitif si pour tout couple d'arêtes, il existe un automorphisme de graphe envoyant la première arête sur la seconde. En d'autres termes, un graphe est arête-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arêtes.

De manière informelle, cette propriété signifie que toutes les arêtes jouent le même rôle dans le graphe.

Propriétés[modifier | modifier le code]

Tout graphe biparti complet et tout graphe symétrique est arête-transitif.

Exemples[modifier | modifier le code]

Le graphe de Gray est arête-transitif et régulier, mais pas sommet-transitif.

Notes et références[modifier | modifier le code]

  1. (en) Eric W. Weisstein, « Edge-Transitive Graph », sur mathworld.wolfram.com (consulté le 9 mars 2019)

_______________________________________________________________________________________________________________________________________________________________ _______________________________________________________________________________________________________________________________________________________________

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

En théorie des graphes, un graphe non-orienté est demi-transitif s'il est arête-transitif et sommet-transitif, mais pas symétrique. Autrement dit, un graphe est demi-transitif si son groupe d'automorphismes agit transitivement sur ses arêtes et ses sommets, mais pas sur les paires de sommets adjacents.

Le graphe de Doyle est le plus petit graphe demi-transitif.

Le plus petit graphe demi-transitif est le graphe de Doyle, un graphe 4-régulier de 27 sommets et 54 arêtes.

Notes et références[modifier | modifier le code]

_______________________________________________________________________________________________________________________________________________________________ _______________________________________________________________________________________________________________________________________________________________

s1 à s2
l = 0
p1 à p6
l = 1
d1 à d10
l = 2
f1 à f14
l = 3
m=0 m=-1 m=0 m=1 m=-2 m=-1 m=0 m=1 m=2 m=-3 m=-2 m=-1 m=0 m=1 m=2 m=3
n=1 Orbitales 1s^1 à 1s^2
1 ≤ N ≤ 2
n=2 Orbitales 2s^1 à 2s^2 Orbitales 2p^1 à 2p^6 Orbitales 2p^1 à 2p^6 Orbitales 2p^1 à 2p^6
3 ≤ N ≤ 4 5 ≤ N ≤ 10
n=3 Orbitales 3s^1 à 3s^2 Orbitales 3p^1 à 3p^6 Orbitales 3p^1 à 3p^6 Orbitales 3^1 à 3p^6 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10
11 ≤ N ≤ 12 13 ≤ N ≤ 18 21 ≤ N ≤ 30
n=4 Orbitales 4s^1 à 4s^2 Orbitales 4p^1 à 4p^6 Orbitales 4p^1 à 4p^6 Orbitales 4p^1 à 4p^6 Orbitales 4d^1 à 4d^10 Orbitales 4d^1 à 4d^10 Orbitales 4d^1 à 4d^10 Orbitales 4d^1 à 4d^10 Orbitales 4d^1 à 4d^10 Orbitales 4f^1 à 4f^14 Orbitales 4f^1 à 4f^14 Orbitales 4f^1 à 4f^14 Orbitales 4f^1 à 4f^14 Orbitales 4f^1 à 4f^14 Orbitales 4f^1 à 4f^14 Orbitales 4f^1 à 4f^14
19 ≤ N ≤ 20 31 ≤ N ≤ 36 39 ≤ N ≤ 48 57 ≤ N ≤ 70
n=5 Orbitales 5s^1 à 5s^2 Orbitales 5p^1 à 5p^6 Orbitales 5p^1 à 5p^6 Orbitales 5p^1 à 5p^6 Orbitales 5d^1 à 5d^10 Orbitales 5d^1 à 5d^10 Orbitales 5d^1 à 5d^10 Orbitales 5d^1 à 5d^10 Orbitales 5d^1 à 5d^10
37 ≤ N ≤ 38 49 ≤ N ≤ 54 71 ≤ N ≤ 80 89 ≤ N ≤ 102
n=6 Orbitales 6s^1 à 6s^2 Orbitales 2p^1 à 2p^6 Orbitales 2p^1 à 2p^6 Orbitales 2p^1 à 2p^6 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10 Orbitales 3d^1 à 3d^10
55 ≤ N ≤ 56 81 ≤ N ≤ 86 103 ≤ N ≤ 112 pas d'élément connu
n=7 Orbitales 7s^1 à 7s^2
87 ≤ N ≤ 88 113 ≤ N ≤ 118 pas d'élément connu pas d'élément connu