Graf Turána

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Graf Turána

Graf Turána to 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

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