title: Graphe de Turán
text: # Graphe de Turán
  
  En théorie des graphes, un graphe de Turán (noté $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 $T(n,r)$ possède $n$ sommets, partitionnés en $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 $(n{\text{ mod }}r)$ sous-ensembles de taille $\lceil n/r\rceil$, et $r-(n{\text{ mod }}r)$ sous-ensembles de taille $\lfloor n/r\rfloor$.
  
  ## Définition
  
  La graphe the Turán de paramètres n et r, noté $T(n,r)$ possède $n$ sommets, partitionnés en $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 $(n{\text{ mod }}r)$ sous-ensembles de taille $\lceil n/r\rceil$, et $r-(n{\text{ mod }}r)$ sous-ensembles de taille $\lfloor n/r\rfloor$.
  
  ## Propriétés
  
  Le nombre chromatique du graphe $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.
  
  