Graf Turána

Graf Turána $T(13,4)$

Graf Turána $T(n,r)$ – graf powstały przez podział zbioru $n$ wierzchołków na $r$ możliwie równych części i połączenie krawędziami tych wierzchołków, które w wyniku podziału znajdą się w różnych podzbiorach.

W wyniku podziału zbioru wierzchołków powstaje $n{\bmod {r}}$ podzbiorów zawierających $\lceil n/r\rceil$ elementów oraz $r-(n{\bmod {r}})$ podzbiorów $\lfloor n/r\rfloor$-elementowych. Z samej definicji wynika, że $T(n,r)$ jest zupełnym grafem r-dzielnym. Każdy wierzchołek jest stopnia $n-\lfloor n/r\rfloor$ albo $n-\lceil n/r\rceil .$ Liczba krawędzi grafu wynosi w przybliżeniu:

$\left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}.$

Nazwa grafu pochodzi od nazwiska węgierskiego matematyka Pála Turána, który wykorzystywał własności takich grafów w dowodzie twierdzenia Turána dotyczącego oszacowania maksymalnej liczby krawędzi w grafie niezawierającym kliki $K_{r+1}.$