Graf Turána

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Graf Turána T(13, 4)

Graf Turána T(n, r) to 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 n\bmod r podzbiorów zawierających \lceil n/r\rceil elementów oraz r - (n\bmod r) 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

\left\lfloor\left(1-\frac1r\right)\frac{n^2}{2}\right\rfloor.

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}.