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 $n$ tel qu'une représentation classique du graphe dans l'espace affine euclidien $E^{n}$ de dimension $n$ ne comporte que des segments de longueur 1.

La dimension du graphe de Petersen est 2.

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 $G$ ainsi : $dim\,G$.

Par exemple, le graphe de Petersen peut être tracé avec des segments de longueur 1 sur le plan euclidien $E^{2}$, mais pas sur la droite $E^{1}$ : 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 $E^{2}$.

Exemples

Avec 4 sommets régulièrement espacés, on a besoin de 3 dimensions.

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 $n-1$ pour y plonger le graphe complet $K_{n}$ à $n$ 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.

$dim\,K_{n}=n-1$

Dit autrement, la dimension du graphe complet coïncide avec la dimension du simplexe associé.

Tracé d'un graphe biparti complet $K_{4,2}$ en 3 dimensions.

Graphes bipartis complets

Un graphe en étoile tracé dans le plan avec des arêtes de longueur 1.

Tous les graphes étoile $K_{m,1}$, pour $m\geq 3$ 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 $K_{m,2}$, pour $m\geq 3$, vaut 3 : sur la figure, on voit comment placer $m$ sommets sur un même cercle et les 2 sommets restants sur l'axe de ce cercle. $K_{2,2}$ peut quant à lui se tracer avec un losange dans un plan.

La dimension d'un graphe biparti complet général $K_{m,n}$, pour $m\geq 3$ et $n\geq 3$, vaut 4.

Démonstration

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 $m$ points ont pour coordonnées :

$\left({\frac {1}{\sqrt {2}}}\cos \alpha _{i},{\frac {1}{\sqrt {2}}}\sin \alpha _{i},0,0\right)$

où les $\alpha _{i}$ sont des mesures d'angles distinctes. On peut par exemple prendre :

$\alpha _{i}=i\cdot {\frac {2\pi }{m}}$

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 $n$ points ont pour coordonnées :

$\left(0,0,{\frac {1}{\sqrt {2}}}\cos \beta _{j},{\frac {1}{\sqrt {2}}}\sin \beta _{j}\right)$

où les $\beta _{j}$ sont aussi des mesures d'angles distinctes.

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

$d^{2}={\frac {1}{2}}(\cos ^{2}\alpha _{i}+\sin ^{2}\alpha _{i})+{\frac {1}{2}}(\cos ^{2}\beta _{j}+\sin ^{2}\beta _{j})={\frac {1}{2}}+{\frac {1}{2}}=1$

On a exhibé une représentation dans l'espace à 4 dimensions du graphe biparti $K_{m,n}$ 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 $K_{3,3}$ n'admet pas de telle représentation en dimension 3.

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

La dimension de $K_{m,n}$ est supérieure ou égale à celle de $K_{3,3}$ et il n'existe pas de plongement de $K_{3,3}$ dans $E^{3}$ avec des arêtes de longueur 1 : la dimension de $K_{m,n}$ est donc au minimum 4.

La dimension de $K_{m,n}$, pour $m\geq 3$ et $n\geq 3$, est à la fois supérieure ou égale à 4 et inférieure ou égale à 4 : elle est donc exactement 4.

En résumé :

$dim\,K_{m,n}=1,2,3{\text{ ou }}4$, selon les valeurs de $m$ et de $n$

Dimension et nombre chromatique

Théorème — La dimension de n'importe quel graphe $G$ est toujours inférieure ou égale au double de son nombre chromatique :

$dim\,G\leq 2\,\chi (G)$

Démonstration

La démonstration reprend encore une fois le principe des cercles d'intersection vide deux à deux.

Notons $n$ le nombre chromatique de $G$ et considérons un repère orthonormal $(O,{\vec {u}}_{1},{\vec {u}}_{2},{\vec {u}}_{3},{\vec {u}}_{4},\ldots ,{\vec {u}}_{2n-1},{\vec {u}}_{2n})$ de l'espace affine euclidien $E^{2n}$ de dimension $2n$. Considérons ensuite les $n$ cercles des plans $(O,{\vec {u}}_{1},{\vec {u}}_{2})$, $(O,{\vec {u}}_{3},{\vec {u}}_{4}),\ldots ,(O,{\vec {u}}_{2n-1},{\vec {u}}_{2n})$, de centre $O$ et de rayon ${\frac {1}{\sqrt {2}}}$. On représente les sommets de $G$ de même couleur par des points différents sur un même cercle.

Toutes les arêtes de $G$ relient des sommets de couleurs différentes, c'est le principe même de la coloration d'un graphe. Les arêtes de $G$ sont donc toutes représentées par des segments reliant des points de cercles différents. De plus, ces segments sont tous, comme dans la démonstration précédente, de longueur 1.

On a donc bien construit un plongement de $G$ dans un espace affine euclidien de dimension $2n$ tel que toutes les arêtes soient de longueur 1. Rien ne garantit que ce soit la plus petite dimension possible, donc on sait seulement que $dim\,G\leq 2\,n$.

Dimension euclidienne

La roue à laquelle on a enlevé un rayon est de dimension 2.

La même roue est de dimension euclidienne 3.

La notion de dimension d'un graphe $G$ présentée plus haut ne satisfait pas complètement certains auteurs. En effet :

• si deux sommets de $G$ 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 $G$ est le nombre $n$ entier tel que dans une représentation classique de $G$ dans l'espace à $n$ dimensions $E^{n}$, deux sommets du graphe sont reliés si et seulement si leurs représentations sont à une distance de 1.

On note cette dimension $Edim\,G$. Elle est toujours plus élevée que la dimension définie plus haut :

$dim\,G\leq Edim\,G$

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 :

Théorème — La dimension euclidienne de n'importe quel graphe $G$ est inférieure ou égale au double de son degré maximal plus un :

$Edim\,G\leq 2\,\Delta (G)+1$