Loading AI tools
élément d'une famille de graphes qui portent le nom de Pál Turán De Wikipédia, l'encyclopédie libre
En théorie des graphes, un graphe de Turán (noté ), aussi appelé maximally saturated graph, est un élément d'une famille de graphes qui portent le nom de Pál Turán.
graphe de Turán | |
Le graphe de Turan (13,4) | |
Notation | |
---|---|
Nombre de sommets | |
Nombre d'arêtes | ~ |
Rayon | |
Diamètre | |
Maille | |
Nombre chromatique | |
modifier |
Le graphe 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 a sous-ensembles de taille , et sous-ensembles de taille .
La graphe the Turán de paramètres n et r, noté 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 .
Le nombre chromatique du graphe 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,
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.