Graphe tétraédrique

Graphe tétraédrique
Représentation du graphe tétraédrique.
Nombre de sommets	4
Nombre d'arêtes	6
Distribution des degrés	3-régulier
Rayon	1
Diamètre	1
Maille	3
Automorphismes	24
Nombre chromatique	4
Indice chromatique	3
Propriétés	Arête-transitif Complet Cubique Distance-régulier Fortement régulier Hamiltonien Parfait Planaire Régulier Sommet-transitif Symétrique Intégral
modifier

Le graphe tétraédrique est, en théorie des graphes, un graphe 3-régulier possédant 4 sommets et 6 arêtes. C'est le squelette du tétraèdre régulier, un solide de Platon ayant 4 faces, toutes triangulaires.

Construction

Il existe cinq graphes correspondant aux squelettes des cinq solides de Platon. Le graphe tétraédrique est l'un d'eux. Les quatre autres sont le graphe hexaédrique, le graphe octaédrique, le graphe dodécaédrique et le graphe icosaédrique.

Le graphe tétraédrique est également isomorphe au graphe complet K₄ et au graphe roue W₄.

Propriétés

Propriétés générales

Le diamètre du graphe tétraédrique, l'excentricité maximale de ses sommets, est 1 ainsi que son rayon, l'excentricité minimale de ses sommets. Tous ses sommets appartiennent donc à son centre.

La maille du graphe tétraédrique, la longueur de son plus court cycle, est 3. 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.

Le graphe tétraédrique contient 14 cycles distincts (7 sans tenir compte du sens de parcours). Six d'entre eux sont des cycles hamiltoniens (3 sans tenir compte du sens de parcours). Il contient également 24 chemins hamiltoniens.

Les cycles du graphe tétraédrique.

Coloriage

Le nombre chromatique du graphe tétraédrique 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. Ce nombre est minimal.

L'indice chromatique du graphe tétraédrique 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.

Il est possible de compter les colorations distinctes d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs à 4 et est de degrés 4. Il est égal à : (x − 3)(x − 2)(x − 1)x.

Propriétés algébriques

Le graphe tétraédrique 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 graphee tétraédrique est l'unique graphe cubique symétrique à 4 sommets et sa notation dans le Foster Census, le catalogue classifiant tous les graphes cubiques symétriques, est F4A^[1]. C'est le plus petit graphe cubique symétrique^[2].

Le groupe d'automorphismes du graphe tétraédrique est d'ordre 24.

Le polynôme caractéristique du graphe tétraédrique est : (x − 3)(x + 1)³. Il n'admet que des racines entières. Le graphe tétraédrique est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Voir aussi

Liens internes

• Théorie des graphes

Liens externes

• (en) Eric W. Weisstein, Tetrahedral Graph (MathWorld)

Références

1. ↑ (en) Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002
2. ↑ (en) Royle, G. "Cubic Symmetric Graphs (The Foster Census)."