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 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. Pięć dowodów tego twierdzenia znajduje się w Dowodach z Księgi.

Sformułowanie[edytuj | edytuj kod]

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

\frac{r-1}{r}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{r} \right) \cdot\frac{n^2}{2}.

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 \lfloor n^2/4\rfloor.

Dowód[edytuj | edytuj kod]

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 u,\,v,\,w takie, że (u, v)\in E, ale  (u, w)\notin E \land (v, w)\notin E.

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: deg(w) \geqslant deg(u) oraz deg(w) \geqslant deg(v).
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:
 \begin{align}
|E'| & = |E| - (deg(u)+deg(v)-1) + 2deg(w) \\
     & = |E| + \underbrace{deg(w)-deg(u)}_{\geqslant 0} + \underbrace{deg(w)-deg(v)}_{\geqslant 0} + 1 \geqslant |E| + 1
\end{align}
Teza 1 jest więc prawdziwa.

Zdefiniujmy relację u\sim v \iff (u, v)\notin E. 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 \sim.

Zauważmy, że musi być k \leqslant r, 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 |A|-1-|B| \geqslant 1 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).

Zobacz też[edytuj | edytuj kod]