Graf Turána
Wygląd
Graf Turána – graf powstały przez podział zbioru wierzchołków na 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 podzbiorów zawierających elementów oraz podzbiorów -elementowych. Z samej definicji wynika, że jest zupełnym grafem r-dzielnym. Każdy wierzchołek jest stopnia albo Liczba krawędzi grafu wynosi w przybliżeniu:
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