Aller au contenu
Omnikalc

Calculateur du théorème de Turán

Saisissez le nombre de sommets et la taille de clique à éviter pour obtenir le nombre maximal d’arêtes du graphe de Turán, la taille de ses parties, la densité d’arêtes et le nombre d’arêtes qui force une clique.

Mis à jour le
Vos paramètres

Valeur hors limites

Valeur hors limites

Résultats

Nombre maximal d’arêtes sans la clique

133

Arêtes qui forcent une clique

134

Arêtes du graphe complet
190
Part de toutes les arêtes possibles
70,00 %
Nombre de parties (r)
3
Parties de la plus grande taille
2
Taille des plus petites parties
6

Le calculateur du théorème de Turán donne le nombre maximal d’arêtes qu’un graphe à n sommets peut avoir sans clique d’une taille donnée, la structure du graphe de Turán extrémal, sa densité, et le nombre d’arêtes qui force la clique.

Comment se fait le calcul

  • Saisissez le nombre de sommets n.
  • Saisissez la taille de clique à éviter, r + 1, d’au moins 3.
  • Lisez le nombre maximal d’arêtes, les parties et la densité.

Exemple

Un graphe à 20 sommets sans clique de 4 peut avoir au plus 133 arêtes, soit 70,00 % des 190 arêtes du graphe complet. Le graphe de Turán a 3 parties : 2 d’entre elles ont un sommet de plus que les plus petites de 6. Avec 134 arêtes, une clique est inévitable.

Pourquoi c’est utile

Le calculateur aide les étudiants et enseignants de mathématiques discrètes, informaticiens et analystes de réseaux qui étudient des problèmes extrémaux de graphes, vérifient des exercices sur les théorèmes de Mantel et de Turán, ou estiment la densité d’un réseau avant qu’il doive contenir un groupe soudé.

À savoir

La taille de clique à éviter est r + 1, donc un graphe sans triangle a r = 2 et une valeur de 3 ici. La formule demande des sommets répartis en parties aussi égales que possible. Le maximum n’est atteint que par le graphe de Turán, donc tout autre graphe avec autant d’arêtes et sans clique est impossible. Le résultat est le plus grand nombre d’arêtes et non le nombre typique. Les vrais graphes, même denses, sont en général très en dessous de cette borne. Quand le nombre de sommets n’est pas un multiple de r, les parties diffèrent d’un sommet, et le calculateur traite ce cas avec le reste.

Outils liés

Le calculateur des nombres de Catalan compte d’autres structures combinatoires, celui des combinaisons compte les sous-ensembles, celui du binôme donne les coefficients et celui des nombres polygonaux liste des dénombrements figurés voisins.

Questions fréquentes

Que dit le théorème de Turán ?

Le théorème de Turán donne le nombre maximal d’arêtes d’un graphe à n sommets qui ne contient aucun sous-graphe complet sur r + 1 sommets. Le graphe extrémal est le graphe r-partite complet dont les parties sont aussi égales que possible, appelé graphe de Turán. Pour r = 2, sans triangle, la réponse est le théorème de Mantel : au plus n² / 4 arêtes.

Quelle est la formule ?

Si n = q × r + s avec 0 ≤ s < r, le graphe de Turán a s parties de taille q + 1 et r − s parties de taille q. Son nombre d’arêtes est (1 − 1/r) × n² / 2 − s × (r − s) / (2r). Si r divise n, cela se réduit à (1 − 1/r) × n² / 2.

Que dit-il sur le fait de forcer une clique ?

Tout graphe avec plus d’arêtes que le nombre de Turán doit contenir une clique sur r + 1 sommets. Pour 20 sommets, un graphe de 133 arêtes ou plus doit contenir une clique de 4. C’est le point de départ de la théorie extrémale des graphes, qui demande combien d’arêtes forcent une structure donnée.

Où l’utilise-t-on ?

Il apparaît en combinatoire extrémale, conception de réseaux, théorie des codes et analyse des graphes denses. Un réseau social avec plus de connexions que la borne de Turán doit contenir un groupe d’amis soudés d’une taille donnée, ce qui permet de prouver l’existence de cliques sans les trouver.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.