![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/langpl-640px-Turan_13-4.svg.png&w=640&q=50)
Graf Turána
Z Wikipedii, wolnej encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/320px-Turan_13-4.svg.png)
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