Graphe de Turán

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le graphe de Turan (13,4)

Un graphe de Turán (noté T(n,r)) est un objet de la théorie des graphes.

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.

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 (Turán 1941).

Bibliographie[modifier | modifier le code]

  • Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48,‎ 1941, p. 436–452

Article connexe[modifier | modifier le code]

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

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « TuranGraph », MathWorld