Twierdzenie Turána
![]() | Ten artykuł od 2011-08 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki
Twierdzenie oraz pierwszy opis grafów Turána pochodzi od węgierskiego matematyka Pála Turána i zostało sformułowane w roku 1941. Pięć dowodów tego twierdzenia znajduje się w Dowodach z Księgi.
Sformułowanie
Spośród wszystkich grafów -wierzchołkowych, które nie zawierają kliki -wierzchołkowej, najwięcej krawędzi posiada graf Turána
Stąd wynika, że w dowolnym grafie takim, że ma co najwyżej wierzchołków oraz nie zawiera -wierzchołkowej kliki, jest co najwyżej
krawędzi.
Szczególnym przypadkiem (dla ) twierdzenia Turána jest następujące twierdzenie Mantela: maksymalna liczba krawędzi w grafie bez trójkątów jest równa co najwyżej
Dowód
Niech będzie -wierzchołkowym grafem niezawierającym kliki takim, że ma maksymalną możliwą liczbę krawędzi.
Teza 1: W nie istnieją wierzchołki takie, że ale
- Załóżmy, że teza jest fałszywa – wtedy uda się skonstruować graf zawierający tyle samo wierzchołków co i niezawierający kliki ale mający więcej niż krawędzi.
- Przypadek 1: lub
- Bez zmniejszenia ogólności, niech Tworzymy graf usuwając wierzchołek i tworząc kopię wierzchołka z takim samym jak zbiorem sąsiadów (nazwijmy ją ). Ponieważ nie ma krawędzi między i to żadna klika w nie zawiera obu wierzchołków. Stąd jeżeli nie zawierał kliki to również jej nie zawiera. Jednocześnie zawiera więcej krawędzi:
- Bez zmniejszenia ogólności, niech Tworzymy graf usuwając wierzchołek i tworząc kopię wierzchołka z takim samym jak zbiorem sąsiadów (nazwijmy ją ). Ponieważ nie ma krawędzi między i to żadna klika w nie zawiera obu wierzchołków. Stąd jeżeli nie zawierał kliki to również jej nie zawiera. Jednocześnie zawiera więcej krawędzi:
- Przypadek 2: oraz
- W tym przypadku tworząc usuwamy wierzchołki oraz i tworzymy dwie kopie wierzchołka i Ponownie, ponieważ nie ma krawędzi pomiędzy i to w nie stworzymy kliki większej niż taka, która istniałaby już w Zauważmy jednak, że i w tym przypadku ma więcej krawędzi:
- Teza 1 jest więc prawdziwa.
- W tym przypadku tworząc usuwamy wierzchołki oraz i tworzymy dwie kopie wierzchołka i Ponownie, ponieważ nie ma krawędzi pomiędzy i to w nie stworzymy kliki większej niż taka, która istniałaby już w Zauważmy jednak, że i w tym przypadku ma więcej krawędzi:
Zdefiniujmy relację Jest to relacja równoważności – jest w oczywisty sposób zwrotna i symetryczna, natomiast przechodniość wynika z udowodnionej właśnie tezy 1, ponieważ jeżeli w nie ma krawędzi między i oraz między i to nie może być też krawędzi między i Stąd wynika, że jest, dla pewnego pełnym grafem k-dzielnym, w którym podział wierzchołków odpowiada podziałowi na klasy abstrakcji relacji
Zauważmy, że musi być ponieważ w przeciwnym wypadku zawierałby jako podgraf klikę oraz że w pełnym grafie -dzielnym liczba krawędzi rośnie wraz z Stąd i z założenia, że ma maksymalną liczbę krawędzi, wynika ostatecznie, że i jest pełnym grafem -dzielnym.
Teza 2: Liczba krawędzi w pełnym grafie -dzielnym jest maksymalna, kiedy wielkości części podziału zbioru wierzchołków różnią się co najwyżej o 1.
- Niech będzie pełnym grafem -dzielnym, w którym istnieją części podziału i takie, że Możemy zwiększyć liczbę krawędzi w przenosząc wierzchołek ze zbioru do zbioru Wskutek przeniesienia usuniemy z grafu krawędzi, jednocześnie dodając krawędzi. W ostatecznym rozrachunku dodajemy krawędzi, co dowodzi tezy 2.
Z powyższego dowodu wynika, że spośród grafów -wierzchołkowych niezawierających kliki najwięcej krawędzi ma graf Turána