Théorie des graphes extrémaux

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété P est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété P. L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits.

L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes.

Définition rigoureuse[modifier | modifier le code]

Soit P une propriété sur les graphes qui se conserve par ajout d'arêtes et G=(V,E) un graphe quelconque. G est dit extrémal par rapport à la propriété P si :

  • G ne vérifie pas P ;
  • \forall (x,y) non adjacents dans G, le graphe G'=(V,E\cup (x,y)) vérifie P.

D'autre part, une fonction f est une borne inférieure par rapport à la propriété P si \forall G=(V,E), |E| > f(|V|) permet d'assurer que G vérifie P.

À noter que les graphes extrémaux ne vérifient pas nécessairement la meilleure borne inférieure.

Exemples[modifier | modifier le code]

Pour la propriété P = "ne pas admettre de triangles comme sous-graphe", une borne inférieure est  |E| = \frac{|V|^2}{4}. Les graphes extrémaux sont exactement les graphes bipartis K_{k,k} et K_{k,k+1}.

Plus généralement, pour P_l = "ne pas admettre de clique de taille l comme sous-graphe", les graphes extrémaux sont les graphes complets (l-1)-partis K_{k,..,k,k+1,..,k+1}. Ce résultat est une conséquence du théorème de Turán, qui fournit également une borne inférieure (trop longue pour être incluse ici).

Références[modifier | modifier le code]