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.