Dimension (théorie des graphes)

En mathématiques, et plus particulièrement dans la théorie des graphes, la dimension d'un graphe est le plus petit nombre entier  tel qu'une représentation classique du graphe dans l'espace affine euclidien  de dimension  ne comporte que des segments de longueur 1.

Dans cette définition, les sommets doivent être distincts, mais il n'y a pas de contraintes sur le croisement des arêtes. On note la dimension d'un graphe  ainsi : .

Par exemple, le graphe de Petersen peut être tracé avec des segments de longueur 1 sur le plan euclidien , mais pas sur la droite  : sa dimension est 2 (figure).

Cette notion a été introduite en 1965 par Paul Erdős, Frank Harary et William Tutte. Elle généralise à une dimension quelconque la notion de graphe distance-unité du plan .

Exemples

Graphe complet 
Dans le pire des cas pour un graphe, tous les sommets sont reliés, c'est le graphe complet.

Il faut un espace euclidien de dimension  pour y plonger le graphe complet  à  sommets pour que toutes les arêtes soient de longueur 1. Par exemple, il faut 2 dimensions pour le graphe complet à 3 sommets représenté par un triangle équilatéral, 3 dimensions pour le graphe complet à 4 sommets représenté par un quadrilatère régulier (figure), etc.
 
Dit autrement, la dimension du graphe complet coïncide avec la dimension du simplexe associé.

Graphes bipartis complets 

Tous les graphes étoile , pour  sommets périphériques, sont de dimension 2 (figure) : ils ont besoin d'un plan pour être tracés avec des arêtes de longueur 1. Les graphes étoile à 1 et 2 sommets périphériques n'ont besoin que d'une droite (dimension 1).

La dimension d'un graphe biparti complet , pour , vaut 3 : sur la figure, on voit comment placer  sommets sur un même cercle et les 2 sommets restants sur l'axe de ce cercle.  peut quant à lui se tracer avec un losange dans un plan.

La dimension d'un graphe biparti complet général , pour  et , vaut 4.

Pour démontrer qu'un espace à 4 dimensions suffit, comme dans le cas précédent, on utilise des cercles.

Le premier cercle est dans le plan X,Y. Ses  points ont pour coordonnées :
 
où les  sont des mesures d'angles distinctes. On peut par exemple prendre :
 
encore que rien n'oblige à les répartir aussi régulièrement sur le cercle.

Le second cercle est dans le plan Z,T. Ses  points ont pour coordonnées :
 
où les  sont aussi des mesures d'angles distinctes.

La distance  entre n'importe quel point du premier cercle et n'importe quel point du second cercle vérifie :
 

On a exhibé une représentation dans l'espace à 4 dimensions du graphe biparti  avec des arêtes de longueur 1. La dimension de ce graphe est donc au maximum 4.

Démontrons par ailleurs que le sous-graphe  n'admet pas de telle représentation en dimension 3.

Si une telle représentation existait, on y verrait trois points ,  et  reliés par des arêtes de longueur 1 à trois points ,  et . Si ,  et  ne sont pas alignés, ils définissent un plan .  étant équidistant de  et de , il est sur le plan médiateur du segment . Il est aussi sur les deux autres plans médiateurs du triangle . L'intersection de ces trois plans est la droite  passant par le centre du cercle circonscrit à  et perpendiculaire à . Il en va de même pour  et . Or, on ne peut pas avoir trois points distincts à même distance de  et de  sur une même droite . On a donc une absurdité dans ce cas. D'autre part, si ,  et  sont alignés, ils sont à même distance de , ce qui est tout aussi absurde puisqu'ils sont distincts.

La dimension de  est supérieure ou égale à celle de  et il n'existe pas de plongement de  dans  avec des arêtes de longueur 1 : la dimension de  est donc au minimum 4.

La dimension de , pour  et , est à la fois supérieure ou égale à 4 et inférieure ou égale à 4 : elle est donc exactement 4.

En résumé :
 , selon les valeurs de  et de

Dimension et nombre chromatique

Dimension euclidienne 

La notion de dimension d'un graphe  présentée plus haut ne satisfait pas complètement certains auteurs. En effet :
 si deux sommets de  sont reliés par une arête, alors leur représentation les place à 1 unité de distance ;
 en revanche, si dans la représentation, deux sommets sont à une unité de distance, ils ne sont pas forcément reliés dans le graphe.

La figure ci-contre montre le problème dans le cas d'un graphe roue à un sommet central et 6 sommets périphériques auquel on a retiré un des rayons. Sa représentation dans le plan admet deux sommets à distance 1, mais qui ne sont pas reliés.

Alexander Soifer définit en 1991 la dimension euclidienne d'un graphe. Avant lui, en 1980, Paul Erdős et Miklós Simonovits l'avaient déjà définie sous le nom de dimension fidèle (faithful dimension). La dimension euclidienne d'un graphe  est le nombre  entier tel que dans une représentation classique de  dans l'espace à  dimensions , deux sommets du graphe sont reliés si et seulement si leurs représentations sont à une distance de 1.

On note cette dimension . Elle est toujours plus élevée que la dimension définie plus haut :
 

Ainsi, dans l'exemple du graphe roue auquel on a enlevé une arête radiale, si l'on exclut que des sommets non reliés puissent être à une distance de 1, il faut sortir un sommet du plan (illustration).

Dimension euclidienne et degré maximal 
Paul Erdős et Miklós Simonovits ont démontré en 1980 le résultat suivant :

Notes et références 

Concept en théorie des graphes
Graphe
Invariant de graphe