Graphe de Nauru - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Graphe de Nauru
Représentation du graphe de Nauru.

Notation F24A
Nombre de sommets 24
Nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) d'arêtes 36
Distribution des degrés 3-régulier
Rayon 4
Diamètre (Dans un cercle ou une sphère, le diamètre est un segment de droite passant par le centre...) 4
Maille 6
Automorphismes 144
Nombre chromatique 2
Indice chromatique 3
Propriétés Régulier
Biparti
Cubique
Intégral
Hamiltonien
Cayley

En mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide...), et plus précisément en théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux...), le graphe de Nauru est un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) 3-régulier possédant 24 sommets et 36 arêtes. Il a été nommé ainsi par David Eppstein d'après l'étoile (Une étoile est un objet céleste émettant de la lumière de façon autonome, semblable à une...) à 12 branches ornant le drapeau de Nauru (Nauru (prononcer [nauru]), en nauruan Naoero, en forme longue République de Nauru, est un...)..

Propriétés

Propriétés générales

Le diamètre du graphe de Nauru, l'excentricité (Cet article décrit l'excentricité en mathématiques et en psychologie.) maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus...) de son plus court cycle, est 6. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Coloriage

Le nombre chromatique du graphe de Nauru est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du graphe de Nauru est 3. Il existe donc une 3-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 Nauru est symétrique, c'est-à-dire que son groupe d'automorphismes agit transitivement sur ses arêtes, ses sommets et ses arcs. Il est donc également arête-transitif et sommet-transitif. Le graphe de Nauru est l'unique graphe cubique symétrique à 24 sommets et sa notation dans le Foster Census, le catalogue classifiant tous les graphes cubiques symétriques, est F24A.

Le groupe d'automorphismes du graphe de Nauru est d'ordre 144. Sa structure exacte est connue : il est isomorphe au produit direct des groupes symétriques S4 et S3.

Le graphe de Petersen (Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant 10...) généralisé G(n,k) est sommet-transitif si et seulement si n = 10 et k =2 ou si k2 ≡ ±1 (mod n). Il est arête-transitif seulement dans les sept cas qui suivent : (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). Donc le graphe de Nauru est un des sept graphes de Petersen généralisés symétriques. Les six autres sont le graphe hexaédrique G(4,1), le graphe de Petersen G(5,2), le graphe de Möbius-Kantor G(8,3), le graphe dodécaédrique G(10,2) et le graphe de Desargues G(10,3).

Le polynôme caractéristique (En algèbre linéaire, à toute matrice carrée ou à tout endomorphisme d'un...) du graphe de Nauru est : (x − 3)(x − 2)6(x − 1)3x4(x + 1)3(x + 2)6(x + 3). Il n'admet que des racines entières. Le graphe de Nauru est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Propriétés topologiques

Le plongement symétrique du graphe de Nauru dans un tore (Un tore est un solide géométrique représentant un tube courbé refermé sur...), formé en collant ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) les arêtes opposées de l' hexagone (Un hexagone (du grec hexi = six et gonia = angle) est un polygone à six sommets et six...) régulier externe
Un plongement symétrique du graphe de Nauru sur une surface (Une surface désigne généralement la couche superficielle d'un objet. Le terme a...) de genre 4, ayant six faces dodécagonales.

Le graphe de Nauru possède deux plongements distincts qu'on peut considérer comme des polyèdres réguliers généralisés : des surfaces (ou plus précisément des variétés de dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une...) 2) décomposées en sommets, arêtes et faces de telle sorte qu'il y ait une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y...) (respectant les relations d'incidence) de la surface envoyant n'importe quel drapeau (un triplet formé d'un sommet, d'une arête et d'une face incidents) vers n'importe quel autre drapeau.

Un de ces deux plongements forme un tore et le graphe de Nauru est donc un graphe torique : il est formé de 12 faces hexagonales, et des 24 sommets et 36 arêtes du graphe de Nauru. Le graphe dual de ce plongement est un graphe symétrique 6-régulier à 12 sommets et 36 arêtes.

L'autre plongement symétrique du graphe de Nauru a six faces dodécagonales, et forme une surface de genre 4. Son dual n'est pas un graphe simple, mais un multigraphe, puisque chaque face a trois côtés communs avec quatre autres faces. Ce graphe dual peut être construit à partir d'un octaèdre (Un octaèdre (du grec oktô, huit et hedra, face) est un polyèdre à huit faces....) régulier en en remplaçant chaque arête par un faisceau de trois arêtes "parallèles".

L'ensemble des faces de chacun de ces deux plongements est l'ensemble des polygones de Pétrie de l'autre plongement.

Page générée en 0.051 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique