Twierdzenie Turána

Z Wikipedii

Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki K_{r + 1}.

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.

[edytuj] Sformułowanie

Spośród wszystkich grafów n-wierzchołkowych, które nie zawierają kliki (r + 1)-wierzchołkowej, najwięcej krawędzi posiada graf Turána T(n,r).

Stąd wynika, że w dowolnym grafie G takim, że G ma co najwyżej n wierzchołków oraz nie zawiera (r + 1)-wierzchołkowej kliki, jest co najwyżej

krawędzi.

Szczególnym przypadkiem (dla r = 2) 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 .

[edytuj] Dowód

Niech G = (V,E) będzie n-wierzchołkowym grafem niezawierającym kliki K_{r + 1} takim, że G ma maksymalną możliwą liczbę krawędzi.

Teza 1: W G nie istnieją wierzchołki takie, że , ale .

Załóżmy, że teza jest fałszywa - wtedy uda się skonstruować graf G' = (V',E') zawierający tyle samo wierzchołków co G i niezawierający kliki K_{r + 1}, ale mający więcej niż G krawędzi.

Przypadek 1: deg(w) < deg(u) lub deg(w) < deg(v).

Bez zmniejszenia ogólności, niech deg(w) < deg(u). Tworzymy graf G' usuwając wierzchołek w i tworząc kopię wierzchołka u z takim samym jak u zbiorem sąsiadów (nazwijmy ją u'). Ponieważ nie ma krawędzi między u i u', to żadna klika w G' nie zawiera obu wierzchołków. Stąd jeżeli G nie zawierał kliki K_{r + 1}, to również G' jej nie zawiera. Jednocześnie G' zawiera więcej krawędzi:

| E' | = | E | − deg(w) + deg(u) > | E |

Przypadek 2: oraz .

W tym przypadku tworząc G' usuwamy wierzchołki u oraz v i tworzymy dwie kopie wierzchołka w: w' i w''. Ponownie, ponieważ nie ma krawędzi pomiędzy w, w' i w'', to w G' nie stworzymy kliki większej niż taka, która istniałaby już w G. Zauważmy jednak, że i w tym przypadku G' 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 G nie ma krawędzi między u i w oraz między w i v, to nie może być też krawędzi między u i v. Stąd wynika, że G jest, dla pewnego k 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 G zawierałby jako podgraf klikę K_{r + 1}, oraz że w pełnym grafie k-dzielnym liczba krawędzi rośnie wraz z k. Stąd i z założenia, że G ma maksymalną liczbę krawędzi, wynika ostatecznie, że k = r i G jest pełnym grafem r-dzielnym.

Teza 2: Liczba krawędzi w pełnym grafie k-dzielnym jest maksymalna, kiedy wielkości części podziału zbioru wierzchołków różnią się co najwyżej o 1.

Niech G = (V,E) będzie pełnym grafem k-dzielnym, w którym istnieją części podziału A i B takie, że | A | > | B | + 1. Możemy zwiększyć liczbę krawędzi w G, przenosząc wierzchołek ze zbioru A do zbioru B. Wskutek przeniesienia usuniemy z grafu | B | krawędzi, jednocześnie dodając | A | − 1 krawędzi. W ostatecznym rozrachunku dodajemy krawędzi, co dowodzi tezy 2.

Z powyższego dowodu wynika, że spośród grafów n-wierzchołkowych niezawierających kliki K_{r + 1}, najwięcej krawędzi ma graf Turána T(n,r).

[edytuj] Zobacz też

• Graf Turána

To jest tylko zalążek artykułu związanego z matematyką. Jeśli potrafisz, rozbuduj go.