AccueilđŸ‡«đŸ‡·Chercher

Graphe régulier

En thĂ©orie des graphes, un graphe rĂ©gulier est un graphe oĂč tous les sommets ont le mĂȘme nombre de voisins, c'est-Ă -dire le mĂȘme degrĂ© ou valence. Un graphe rĂ©gulier dont les sommets sont de degrĂ© est appelĂ© un graphe -rĂ©gulier ou graphe rĂ©gulier de degrĂ© .

Exemples

Un graphe 0-rĂ©gulier est un ensemble de sommets dĂ©connectĂ©s; un graphe 1-rĂ©gulier a un nombre pair de sommets et est un ensemble d'arĂȘtes dĂ©connectĂ©es ou couplage; enfin, un graphe 2-rĂ©gulier est un ensemble de cycles dĂ©connectĂ©s. Un graphe 3-rĂ©gulier est aussi appelĂ© graphe cubique.

  • graphe 0-rĂ©gulier
    graphe 0-régulier
  • graphe 1-rĂ©gulier
    graphe 1-régulier
  • graphe 2-rĂ©gulier
    graphe 2-régulier
  • graphe de Petersen (graphe cubique particulier)
    graphe de Petersen (graphe cubique particulier)
  • graphe infini 2-rĂ©gulier
    graphe infini 2-régulier

Graphes fortement réguliers

Un graphe fortement rĂ©gulier est un graphe rĂ©gulier oĂč chaque paire de sommets adjacents a le mĂȘme nombre de voisins en commun et oĂč chaque paire de sommets non-adjacents a le mĂȘme nombre de voisins en commun. Les plus petits graphes qui sont rĂ©guliers sans ĂȘtre fortement rĂ©guliers sont le graphe cycle et le graphe circulant, tous deux Ă  6 sommets. Le graphe complet est fortement rĂ©gulier pour tout

Existence

Une condition nécessaire et suffisante pour l'existence d'un graphe -régulier à sommets est que soit pair et que [1].

Propriétés

Un théorÚme de Crispin Nash-Williams affirme que tout graphe -régulier ayant sommets admet un cycle hamiltonien[2].

Soit la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si est un vecteur propre de . Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe.

Aspects algorithmiques

Optimisation combinatoire

De nombreux problĂšmes de graphes sont difficiles mĂȘme si l'on se restreint Ă  la classe des graphes rĂ©guliers. Plus prĂ©cisĂ©ment, la coloration, le problĂšme du voyageur de commerce et le problĂšme du stable maximum sont NP-difficiles pour les graphes rĂ©guliers et mĂȘme pour les graphes k-rĂ©guliers avec k fixĂ©[3].

Par contre le problĂšme de l'isomorphisme de graphes peut ĂȘtre dĂ©cidĂ© en temps polynomial sur les graphes de degrĂ© bornĂ©, par exemple les graphes rĂ©guliers[4].

Génération

Des graphes rĂ©guliers peuvent ĂȘtre gĂ©nĂ©rĂ©s en utilisant le logiciel GenReg[5].

Références

  1. (en) Ioan Tomescu, Problems in combinatorics and graph theory, New York, Wiley, , 335 p., p. 212-213
  2. Une preuve du thĂ©orĂšme de Nash-Williams et l'article original : Crispin Nash-Williams, « Valency sequences which force graphs to have Hamiltonian circuits », University of Waterloo Research Report, Waterloo, Ontario,‎ .
  3. Pour k bien choisi, typiquement 3, 4 ou plus grand. Voir la page k-regular, fixed k sur Graphclasses.org, pour un résumé et les références.
  4. Voir Luks 1982. Cet article a permis Ă  Eugene Luks (en) de recevoir le prix Fulkerson en 1985. Une description de l'idĂ©e de l'algorithme peut ĂȘtre trouvĂ© dans Fortin 1996, section 2.3.
  5. M. Meringer, J. Graph Theory, 1999, 30, 137.

Voir aussi

Bibliographie

  • Eugene M. Luks, « Isomorphism of graphs of bounded valence can be tested in polynomial time », Journal of Computer and System Sciences, vol. 25,‎ , p. 42-65 (DOI 10.1016/0022-0000(82)90009-5).
  • (en) Scott Fortin, The graph isomorphism problem (Technical Report 96-20), University of Alberta, Edmonton, Alberta, Canada, (lire en ligne)

Articles connexes

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.