Graphe de Turán

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique théorique image illustrant les mathématiques
Cet article est une ébauche concernant l’informatique théorique et les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le graphe de Turan (13,4)

Un graphe de Turán (noté ), aussi appelé maximally saturated graph, est un objet de la théorie des graphes.

possède sommets, partitionnés en 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 sous-ensembles de taille , et sous-ensembles de taille .

Ils 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[1].

Propriétés[modifier | modifier le code]

Le nombre chromatique du graphe est r[2]

Notes et références[modifier | modifier le code]

  1. Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48,‎ , p. 436–452
  2. Chong-Yun Chao et George A Novacky Jr, « On maximally saturated graphs », Discrete Mathematics, Elsevier, vol. 41, no 2,‎ , p. 139-143

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Théorème d'Erdős-Stone (en)

Lien externe[modifier | modifier le code]

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