Graphe de Turán

graphe de Turán
Le graphe de Turan (13,4)
Notation	${\displaystyle T(n,r)}$
Nombre de sommets	${\displaystyle n}$
Nombre d'arêtes	~${\displaystyle {\frac {(r-1)n^{2}}{2r}}}$
Rayon	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{sinon}}\end{array}}\right.}$
Diamètre	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{sinon}}\end{array}}\right.}$
Maille	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{sinon}}\end{array}}\right.}$
Nombre chromatique	${\displaystyle r}$
modifier

En théorie des graphes, un graphe de Turán (noté ${\displaystyle T(n,r)}$), aussi appelé maximally saturated graph, est un élément d'une famille de graphes qui portent le nom de Pál Turán.

Le graphe ${\displaystyle T(n,r)}$ possède ${\displaystyle n}$ sommets, partitionnés en ${\displaystyle r}$ sous-ensembles les plus équilibrés possibles, et chaque sommet est relié à tous les sommets qui ne sont pas dans son sous-ensemble. Par équilibré, on entend que le graphe a ${\displaystyle (n{\text{ mod }}r)}$ sous-ensembles de taille ${\displaystyle \lceil n/r\rceil }$, et ${\displaystyle r-(n{\text{ mod }}r)}$ sous-ensembles de taille ${\displaystyle \lfloor n/r\rfloor }$.

La graphe the Turán de paramètres n et r, noté ${\displaystyle T(n,r)}$ possède ${\displaystyle n}$ sommets, partitionnés en ${\displaystyle r}$ sous-ensembles les plus équilibrés possibles, et chaque sommet est relié à tous les sommets qui ne sont pas dans son sous-ensemble. Par équilibré, on entend que le graphe aura ${\displaystyle (n{\text{ mod }}r)}$ sous-ensembles de taille ${\displaystyle \lceil n/r\rceil }$, et ${\displaystyle r-(n{\text{ mod }}r)}$ sous-ensembles de taille ${\displaystyle \lfloor n/r\rfloor }$.

Le nombre chromatique du graphe ${\displaystyle T(n,r)}$ est r^[1].

Les graphes bipartis complets sont des graphes de Turán.

Ce sont des cographes, c'est-à-dire qu'ils peuvent être formés par des unions disjointes et des passages au graphe complémentaire. On peut le réaliser de la manière suivante :

pour chaque stable du graphe final,

• faire d'abord une union de tous les sommets,
• passer au complémentaire (dans chaque ensemble) pour avoir des cliques,
• puis faire l'union de toutes les cliques,
• passer encore au complémentaire.

Les graphes de Turán portent le nom de Pál Turán, qui les a définis et utilisés pour la démonstration du théorème de Turán^[2].

• Théorème d'Erdős-Stone

• (en) Eric W. Weisstein, « Turán Graph », sur MathWorld

• Portail des mathématiques