Graf Turána

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.

Graf Turána

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

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