Graphes connexes non isomorphes et k-réguliers - Collège Georges Pompidou (Cajarc) Lycée Raymond Savignac (Villefranche de Rouergue), Lycée Louis Massignon (Casablanca)

Titre du sujet
Graphes connexes non isomorphes et k-réguliers
Établissement
Collège Georges Pompidou (Cajarc)
Année
2021-2022
Etablissement(s) jumelé(s)
Lycée Raymond Savignac (Villefranche de Rouergue)
Lycée Louis Massignon (Casablanca)
Résumé
Après avoir introduit la notion de graphe connexe, on définit celle d’isomorphisme et de k-régulier. Deux graphes sont isomorphes si on peut passer de l’un à l’autre en renumérotant les sommets. Un graphe est k-régulier si tous ses sommets sont de degré k. Rappelons que le degré d’un sommet est le nombre d’arêtes adjacentes à ce sommet. Il n’existe pas de formule générale qui donne le nombre de graphes connexes non isomorphes et k-régulier mais on peut résoudre le problème pour des petites valeurs de k ou des petites valeurs de n. C’est l’objet de cette recherche.
Mots clés