Graphe de Klein

Graphe de Klein
Graphe de Klein
Nombre de sommets 24
Nombre d'arêtes 84
Distribution des degrés 7-régulier
Rayon 3
Diamètre 3
Maille 3
Automorphismes 336
Nombre chromatique 4
Indice chromatique 7
Propriétés Régulier
Hamiltonien
Graphe de Cayley
Symétrique
modifier Consultez la documentation du modèle

Le graphe de Klein est, en théorie des graphes, un graphe 7-régulier possédant 24 sommets et 84 arêtes.

Sommaire

Propriétés

Propriétés générales

Le diamètre du graphe de Klein, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 7-sommet-connexe et d'un graphe 7-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 7 sommets ou de 7 arêtes.

Coloriage

Le nombre chromatique du graphe de Klein est 4. C'est-à-dire qu'il est possible de le colorer avec 4 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 3-coloration valide du graphe.

L'indice chromatique du graphe de Klein est 7. Il existe donc une 7-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques

Le graphe de Klein est symétrique, c'est-à-dire que son groupe d'automorphisme agit transitivement sur ses arêtes, ses sommets et ses arcs. Son groupe d'automorphisme est d'ordre 336.

Le polynôme caractéristique du graphe de Klein est : (x − 7)(x + 1)7(x2 − 7)8.

Voir aussi

Liens internes

Liens externes

Références



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Klein de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Graphe local — En théorie des graphes, un graphe G est dit être localement X si quel que soit le sommet s de G considéré, le sous graphe induit sur G par les voisins de s est isomorphe à X (si X est un graphe) ou à un graphe appartenant à X (si X est une… …   Wikipédia en Français

  • Graphe diamant — Représentation du graphe diamant. Nombre de sommets 4 Nombre d arêtes 5 Distribution des degrés 2 (2 sommets) 3 (2 sommets) Rayon 1 …   Wikipédia en Français

  • Graphe criquet — Représentation du graphe criquet. Nombre de sommets 5 Nombre d arêtes 5 Distribution des degrés 1 (2 sommets) 2 (2 sommets) 4 (1 sommet) Rayon 1 …   Wikipédia en Français

  • Graphe mite — Représentation du graphe mite. Nombre de sommets 6 Nombre d arêtes 7 Distribution des degrés 1 (2 sommets) 2 (2 sommets) 3 (1 sommet) 5 (1 sommet) Rayon 1 …   Wikipédia en Français

  • Graphe Du Désir — Un graphe du désir est une méthode de représentation de processus insconcients conçue par Lacan et présenté lors de son séminaire de 1957 1958 [1]. Sommaire 1 L’origine du graphe du désir 2 Notes …   Wikipédia en Français

  • Graphe du desir — Graphe du désir Un graphe du désir est une méthode de représentation de processus insconcients conçue par Lacan et présenté lors de son séminaire de 1957 1958 [1]. Sommaire 1 L’origine du graphe du désir 2 Notes …   Wikipédia en Français

  • Graphe de Franklin — Représentation du graphe de Franklin. Nombre de sommets 12 Nombre d arêtes 18 Distribution des degrés 3 régulier Rayon …   Wikipédia en Français

  • Graphe de Harborth — Nombre de sommets 52 Nombre d arêtes 104 Distribution des degrés 4 régulier Rayon 6 Diamètre 9 Maille …   Wikipédia en Français

  • Graphe poisson — Représentation du graphe poisson. Nombre de sommets 6 Nombre d arêtes 7 Distribution des degrés 2 (5 sommets) 4 (1 sommet) Rayon 2 Di …   Wikipédia en Français

  • Graphe domino — Représentation du graphe domino. Nombre de sommets 6 Nombre d arêtes 7 Distribution des degrés 2 (4 sommets) 3 (2 sommets) Rayon 2 …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”