Graphe de Turán

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 }$.

Définition

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 }$.

Propriétés

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

Cas particuliers et inclusions

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.

Histoire

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.

Notes et références

Voir aussi

Article connexe

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

Lien externe

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

• Portail des mathématiques