Twierdzenie Turána

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

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]

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]