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 $nmodr$ podzbiorów zawierających $\lceil n/r\rceil$ elementów oraz $r-(nmodr)$ 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:

$(1-\frac{1}{r})\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}.$