Graf Turána

Graf Turána ${\displaystyle T(n,r)}$ – graf powstały przez podział zbioru ${\displaystyle n}$ wierzchołków na ${\displaystyle 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.

Graf Turána ${\displaystyle T(13,4)}$

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

${\displaystyle \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 ${\displaystyle K_{r+1}.}$