Przejdź do zawartości

Twierdzenie Turána

Z Wikipedii, wolnej encyklopedii

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

[edytuj | edytuj kod]

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

[edytuj | edytuj kod]

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

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

Zobacz też

[edytuj | edytuj kod]