01ZTGA:Kapitola2 3: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Založena nová stránka: %\wikiskriptum{01ZTGA}) |
|||
| Řádka 1: | Řádka 1: | ||
%\wikiskriptum{01ZTGA} | %\wikiskriptum{01ZTGA} | ||
| + | |||
| + | \section{Extremální teorie grafů} | ||
| + | |||
| + | Věty z extremální teorie grafů vyjadřují vztahy typu | ||
| + | |||
| + | \begin{itemize} | ||
| + | \item ,,jistý počet něčeho už vynucuje něco{}`` nebo | ||
| + | \item ,,kolik něčeho může být, aby platilo něco{}`` | ||
| + | \end{itemize} | ||
| + | |||
| + | \subsection{Turánova věta} | ||
| + | |||
| + | \begin{thm} | ||
| + | \textbf{\emph{\label{thm:turan}(Turán, 1943)}} | ||
| + | |||
| + | Nechť $G=(V,E)$ je graf, který neobsahuje kliku velikosti $p$ (viz. | ||
| + | definice \ref{def:klika-nez-mnozina}) , tj. $K_{p}$ není podgrafem | ||
| + | $G$. Potom\begin{equation} | ||
| + | \# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right).\label{eq:turan}\end{equation} | ||
| + | |||
| + | \end{thm} | ||
| + | Důkazů Turánovy věty existuje řada, my postupně provedeme důkaz založený | ||
| + | na následujícím lemmatu: | ||
| + | |||
| + | \begin{lem} | ||
| + | Nechť $G$ je graf (na pevném počtu vrcholů) neobsahující $K_{p}$ | ||
| + | s maximálním počtem hran. Potom v $G$ neexistuje trojice vrcholů | ||
| + | $u,v,w$ takových, že $\{ v,w\}\in E$ a přitom $\{ u,v\}\notin E,\{ u,w\}\notin E$. | ||
| + | |||
| + | \hfill{} | ||
| + | \begin{center} | ||
| + | %Title: turan_lemma.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 18:00:48 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.003 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 20.003 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 8.096 20.003 to 10.478 20.003 | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}w}% | ||
| + | } [lB] at 10.835 19.884 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}v}% | ||
| + | } [lB] at 7.499 19.884 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}% | ||
| + | } [lB] at 9.167 20.360 | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.286 20.955 | ||
| + | }% | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 7.468 21.088 and 10.867 19.852 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | \hfill{}~ | ||
| + | \end{lem} | ||
| + | \begin{proof} | ||
| + | Nejprve proveďme pomocnou úvahu: Buď $G=(V,E)$ bez $K_{p}$, nechť | ||
| + | $x\in V$. Sestrojme graf \[ | ||
| + | G'=\left(V\cup\{ x'\},E\cup\left\{ \left.\{ v,x'\}\right|v\in V\wedge\{ v,x\}\in E\right\} \right),\] | ||
| + | pro nějž $\forall v\in V$ platí $\{ x,v\}\in E(G')\Leftrightarrow\{ x',v\}\in E(G')$. | ||
| + | Vrcholy $x$ a $x'$ jsou tedy v $G'$ zcela rovnocenné. Protože $\{ x,x'\}\notin E(G')$, | ||
| + | tak $G'$ \underbar{nemůže obsahovat} $K_{p}$. V $K_{p}$ by totiž | ||
| + | musel být buď jen vrchol $x$, nebo jen vrchol $x'$, což je spor, | ||
| + | protože v tom případě by musela klika $K_{p}$ existovat už v $G$. | ||
| + | |||
| + | Nyní postupujme sporem. Nechť v $G$ existuje trojice vrcholů $u,v,w$ | ||
| + | daných vlastností. Potom mohou nastat dvě možnosti: | ||
| + | \begin{enumerate} | ||
| + | \item $d_{G}(u)<d_{G}(v)$ nebo $d_{G}(u)<d_{G}(w)$ (nechť BÚNO $d_{G}(u)<d_{G}(v)$). | ||
| + | V tomto případě ke grafu $G$ přidáme právě popsaným způsobem vrchol | ||
| + | $v'$ a ubereme vrchol $u$ (i se všemi hranami, které do něj vedly). | ||
| + | Nově vytvořený graf neobsahuje $K_{p}$, ale přitom má o\[ | ||
| + | d_{G}(v')-d_{G}(u)=d_{G}(v)-d_{G}(u)>0\] | ||
| + | hran více než $G$, což je spor s maximálním počtem hran grafu $G$. | ||
| + | \item $d_{G}(u)\geq d_{G}(v)$ a $d_{G}(u)\geq d_{G}(w)$. V tomto případě | ||
| + | ke $G$ přidáme kopie $u',u''$ a ubereme vrcholy $v,w$. Nový graf | ||
| + | opět neobsahuje $K_{p}$ a má o\[ | ||
| + | 2d_{G}(u)-d_{G}(v)-d_{G}(w)+1>0\] | ||
| + | hran více než $G$, což je spor. Jedničku přičítáme proto, že $\{ v,w\}\in E$, | ||
| + | a odečtením stupňů vrcholů $v,w$ jsme tuto hranu odečetli od celkového | ||
| + | počtu hran dvakrát. | ||
| + | \end{enumerate} | ||
| + | \end{proof} | ||
| + | \begin{cor*} | ||
| + | Relace $\oslash$ na množině vrcholů $V$ grafu $G$ s vlastnostmi | ||
| + | z minulého lemmatu definovaná jako\[ | ||
| + | \left(u\oslash v\right)\Leftrightarrow\{ u,v\}\notin E\] | ||
| + | je ekvivalence na $V$. | ||
| + | \end{cor*} | ||
| + | \begin{proof} | ||
| + | Symetrie a reflexivita relace $\oslash$ jsou zřejmé. Tranzitivitu | ||
| + | pak vyjadřuje předchozí lemma:\[ | ||
| + | \{ v,u\}\notin E\wedge\{ u,w\}\notin E\Rightarrow\{ v,w\}\notin E.\] | ||
| + | |||
| + | \end{proof} | ||
| + | Nyní přikročíme přímo k důkazu tvrzení Turánovy věty. | ||
| + | |||
| + | \begin{proof} | ||
| + | Mějme tedy $G=(V,E)$ bez $K_{p}$, s maximálním počtem hran. Bude-li | ||
| + | platit (\ref{eq:turan}) pro tento $G$, bude platit i pro libovolný | ||
| + | jiný graf bez $K_{p}$ (s nejvýše stejným počtem hran). $V$ je rozdělena | ||
| + | na třídy ekvivalence podle relace $\oslash$\[ | ||
| + | V=V_{1}\cup V_{2}\cup...\cup V_{s},\] | ||
| + | přičemž z definice $\oslash$ platí: | ||
| + | \begin{itemize} | ||
| + | \item \begin{equation} | ||
| + | \left(\forall i\in\hat{s}\right)\left(\forall u,v\in V_{i}\right)\left(\{ u,v\}\notin E\right),\label{eq:turan-podm1}\end{equation} | ||
| + | |||
| + | \item \begin{equation} | ||
| + | \left(\forall i,j\in\hat{s},i\neq j\right)\left(\forall u\in V_{i}\right)\left(\forall v\in V_{j}\right)\left(\{ u,v\}\in E\right).\label{eq:turan-podm2}\end{equation} | ||
| + | |||
| + | \end{itemize} | ||
| + | Mezi každými dvěma vrcholy z různých tříd tedy vedou hrany, ale v | ||
| + | jedné třídě není hrana mezi žádnými dvěma vrcholy. | ||
| + | |||
| + | Počet tříd je $s=p-1$. Kdyby jich totiž bylo alespoň $p$, bylo by | ||
| + | možné vybrat z každé z nich jeden vrchol, a vybraná podmnožina $V$ | ||
| + | by tvořila kliku velikosti $s\geq p$, takže by v $G$ existovala | ||
| + | i $K_{p}\subset K_{s}\subset G$. Kdyby jich naopak bylo méně než | ||
| + | $p-1$, potom bychom mohli jednu třídu ekvivalence rozbít na dvě (přidat | ||
| + | hrany mezi odpovídajícími množinami vrcholů), a stále by graf neobsahoval | ||
| + | $K_{p}$ (je jasné, že různé vrcholy z $K_{p}$ musí ležet v různých | ||
| + | třídách $V_{i}$). To by ale byl spor s maximalitou počtu hran v $G$. | ||
| + | |||
| + | $V$ se tedy skládá z $p-1$ podmnožin $V_{1},...,V_{p-1}$ s vlastnostmi | ||
| + | (\ref{eq:turan-podm1}) a (\ref{eq:turan-podm2}). Označme si $k_{i}=\# V_{i}$ | ||
| + | pro každé $i\in\widehat{p-1}$. Potom\[ | ||
| + | n=\sum_{i=1}^{p-1}k_{i}.\] | ||
| + | Počet hran mezi $V_{i}$ a $V_{j}$ pro $i\neq j$ je zřejmě $k_{i}k_{j}$, | ||
| + | takže počet hran v celém grafu je\begin{equation} | ||
| + | \sum_{1\leq i<j\leq p-1}k_{i}k_{j}\label{eq:turan-pocet-hran}\end{equation} | ||
| + | a přitom v $G$ je počet hran maximální mezi všemi grafy na $n=\# V$ | ||
| + | vrcholech, které neobsahují $K_{p}$. Je tedy maximální i mezi takovými | ||
| + | z nich, které mají stejný ,,tvar{}`` jako $G$: jejich množina vrcholů | ||
| + | je nějak rozdělena na $p-1$ neprázdných disjunktních podmnožin, které | ||
| + | splňují (\ref{eq:turan-podm1}) a (\ref{eq:turan-podm2}). Přitom | ||
| + | každý graf, který splňuje tyto podmínky, neobsahuje $K_{p}$. Každý | ||
| + | z těchto grafů je navíc jednoznačně (až na izomorfismus) určen $(p-1)$-ticí | ||
| + | $(k_{1},...,k_{p-1})$. Počet hran v $G$ je potom možno vyjádřit | ||
| + | jako\[ | ||
| + | \max\left(\sum_{1\leq i<j\leq p-1}k_{i}k_{j}\right)\] | ||
| + | za podmínky\[ | ||
| + | n=\sum_{i=1}^{p-1}k_{i}\,,\; k_{i}\in\N_{0}.\] | ||
| + | Maxima počtu hran se však nabyde právě tehdy, když počet ,,nehran{}`` | ||
| + | (dvojic vrcholů, mezi nimiž nevede hrana) bude minimální. Ekvivalentně | ||
| + | tak lze hledat\[ | ||
| + | \min\left(\sum_{i=1}^{p-1}\binom{k_{i}}{2}\right)\] | ||
| + | za stejných podmínek, což bude jednodušší. Protože chceme pouze shora | ||
| + | odhadnout skutečný počet hran v $G$, vyřešíme úlohu minima bez podmínky | ||
| + | na celočíselnost proměnných $k_{i}$. Hledáme tedy vázaný extrém funkce\[ | ||
| + | f(x_{1},...,x_{p-1})=\sum_{i=1}^{p-1}\binom{x_{i}}{2}=\sum_{i=1}^{p-1}\frac{1}{2}x_{i}(x_{i}-1)\] | ||
| + | za podmínky\[ | ||
| + | \sum_{i=1}^{p-1}x_{i}=n.\] | ||
| + | Sestavíme Lagrangeovu funkci\[ | ||
| + | \Lambda(x_{1},...,x_{p-1})=f(x_{1},...,x_{p-1})-\lambda\left(\sum_{i=1}^{p-1}x_{i}-n\right)\] | ||
| + | a po zderivování a položení $\left(\forall i\in\widehat{p-1}\right)\left(\partial_{i}\Lambda=0\right)$ | ||
| + | dostaneme\[ | ||
| + | 0=\frac{\partial\Lambda}{\partial x_{i}}=x_{i}-\frac{1}{2}-\lambda\;\Rightarrow x_{i}=\lambda+\frac{1}{2}.\] | ||
| + | Pokud dosadíme do podmínky vazby, vyjde $\lambda=\frac{n}{p-1}-\frac{1}{2}$, | ||
| + | takže pro všechna $x_{i}$ platí \[ | ||
| + | x_{i}=\frac{n}{p-1}.\] | ||
| + | Lze snadno ověřit, že se skutečně jedná o minimum, výpočtem (tzv. | ||
| + | Hessovy) matice $\vec{H}=\left(\frac{\partial^{2}\Lambda}{\partial x_{i}\partial x_{j}}\right)$. | ||
| + | Platí $\vec{H}=\vec{I}$, což je zřejmě pozitivně definitní matice. | ||
| + | |||
| + | Dosadíme-li nyní za $x_{i}$ do $\sum_{1\leq i<j\leq p-1}x_{i}x_{j}$, | ||
| + | získáme horní odhad skutečného počtu hran (\ref{eq:turan-pocet-hran}). | ||
| + | Všechny sčítance v sumě jsou stejné a jejich počet je $\binom{p-1}{2}$, | ||
| + | takže horní odhad počtu hran vychází jako\[ | ||
| + | \left(\frac{n}{p-1}\right)^{2}\binom{p-1}{2}=\frac{n^{2}}{(p-1)^{2}}\frac{(p-1)(p-2)}{2}=\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right),\] | ||
| + | což je přesně (\ref{eq:turan}). | ||
| + | \end{proof} | ||
| + | \begin{rem*} | ||
| + | Důkaz Turánovy věty také ukazuje, jak graf s co největším počtem hran, | ||
| + | a přitom bez $K_{p}$, zkonstruovat. Například graf neobsahující $K_{3}$ | ||
| + | s maximálním počtem hran bude úplný bipartitní s množinou vrcholů | ||
| + | $V$ rozdělenou na podmnožiny s počty vrcholů $\left[\frac{n+1}{2}\right]$ | ||
| + | a $\left[\frac{n}{2}\right]$. | ||
| + | \end{rem*} | ||
| + | V následujícím ukážeme jednu z aplikací Turánovy věty. | ||
| + | |||
| + | \begin{defn*} | ||
| + | Nechť $S=\{ x_{1},...,x_{n}\}\subset\R^{2}$ je množina bodů v rovině. | ||
| + | \textbf{Průměrem} (diametrem) množiny $S$ rozumíme číslo\[ | ||
| + | \mathrm{diam}\, S=\max_{i,j\in\hat{n}}\left\Vert x_{i}-x_{j}\right\Vert .\] | ||
| + | |||
| + | \end{defn*} | ||
| + | \begin{rem*} | ||
| + | Nechť $S=\{ x_{1},...,x_{n}\}\subset\R^{2}$, $\mathrm{diam}\, S\leq1$, | ||
| + | $d\in(0,1)$. Otázkou je, kolik párů bodů $x_{i},x_{j}$ má vzdálenost | ||
| + | $\geq d$, a jestli tento počet lze jiným uspořádáním bodů $x_{1},...,x_{n}$ | ||
| + | zvýšit. Jako příklad si vezměme $n=6,d=\frac{\sqrt{3}}{2}-\varepsilon$, | ||
| + | $\varepsilon>0$. Potom existuje $\binom{6}{2}=15$ různých párů. | ||
| + | Na obrázku \ref{cap:vzdalene-pary} jsou páry od sebe vzdálených bodů | ||
| + | spojeny čarami. Vlevo má $9$ párů vzdálenost $\geq d$ a $6$ párů | ||
| + | vzdálenost $<d$, vpravo má $12$ párů vzdálenost $\geq d$ a jen | ||
| + | $3$ páry vzdálenost $<d$. Obecně omezuje počet vzdálených párů následující | ||
| + | věta. % | ||
| + | \begin{figure} | ||
| + | \begin{center} | ||
| + | %Title: diameter1.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:47:04 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 15.001 20.479 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 16.311 17.264 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 16.669 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 14.525 20.479 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 13.216 17.264 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.857 19.526 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.857 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.191 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.191 19.526 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 16.669 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.905:1.905 360 degrees | ||
| + | from 11.430 18.574 center at 9.525 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 20.479 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{1,0,0}\putrule from 13.214 17.266 to 16.311 17.266 | ||
| + | \plot 16.311 17.266 15.001 20.479 / | ||
| + | \plot 15.001 20.479 12.859 17.621 / | ||
| + | \putrule from 12.859 17.621 to 16.669 17.621 | ||
| + | \plot 16.669 17.621 14.525 20.479 / | ||
| + | \plot 14.525 20.479 13.214 17.266 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{1,0,0}\plot 14.525 20.479 12.859 17.621 / | ||
| + | \plot 12.859 17.621 16.311 17.266 / | ||
| + | \plot 16.311 17.266 14.525 20.479 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{1,0,0}\plot 15.001 20.479 13.214 17.266 / | ||
| + | \plot 13.214 17.266 16.669 17.621 / | ||
| + | \plot 16.669 17.621 15.001 20.479 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{1,0,0}\putrule from 9.525 20.479 to 9.525 16.669 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{1,0,0}\plot 7.857 17.621 11.191 19.526 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{1,0,0}\putrule from 7.857 19.526 to 11.191 19.526 | ||
| + | \plot 11.191 19.526 9.525 16.669 / | ||
| + | \plot 9.525 16.669 7.857 19.526 / | ||
| + | \plot 7.857 19.526 11.191 17.621 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{1,0,0}\putrule from 7.857 17.621 to 11.191 17.621 | ||
| + | \plot 11.191 17.621 9.525 20.479 / | ||
| + | \plot 9.525 20.479 7.857 17.621 / | ||
| + | }% | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 7.603 20.612 and 16.804 16.535 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | |||
| + | |||
| + | \caption{\label{cap:vzdalene-pary}Páry vzdálených bodů v rovině} | ||
| + | \end{figure} | ||
| + | |||
| + | \end{rem*} | ||
| + | \begin{thm} | ||
| + | \label{thm:vzdalene-pary}Nechť $d\in\left(\frac{1}{\sqrt{2}},1\right)$. | ||
| + | Potom počet párů z $n$-prvkové množiny $S\subset\R^{2}$ s průměrem | ||
| + | $\mathrm{diam}\, S\leq1$, které mají vzdálenost alespoň $d$, je | ||
| + | nejvýše $\left[\frac{n^{2}}{3}\right]$. Přitom tohoto počtu lze vhodným | ||
| + | uspořádáním bodů vždy dosáhnout. | ||
| + | \end{thm} | ||
| + | Než dokážeme tuto větu, která je snadným důsledkem Turánovy věty, | ||
| + | připravíme si ješte malé lemma. | ||
| + | |||
| + | \begin{lem} | ||
| + | Z libovolných čtyř bodů v rovině lze vybrat tři tak, že tvoří pravoúhlý | ||
| + | nebo tupoúhlý trojúhelník (přitom přímku považujeme za tupoúhlý trojúhelník | ||
| + | s úhlem $180^{\circ}$). | ||
| + | \end{lem} | ||
| + | \begin{proof} | ||
| + | Mohou nastat dva případy: | ||
| + | \begin{enumerate} | ||
| + | \item Jeden bod $x$ leží v konvexním obalu zbylých tří bodů $y_{1},y_{2},y_{3}$. | ||
| + | Potom součet vrcholových úhlů $\measuredangle y_{1}xy_{2}$,$\measuredangle y_{2}xy_{3}$,$\measuredangle y_{3}xy_{1}$ | ||
| + | je $360^{\circ}$, takže jeden z nich musí být dokonce $\geq120^{\circ}$. | ||
| + | \item Všechny čtyři body tvoří konvexní čtyřúhelník. Protože v něm je součet | ||
| + | úhlů $360^{\circ}$, musí tam existovat jeden $\geq90^{\circ}$. | ||
| + | \end{enumerate} | ||
| + | \end{proof} | ||
| + | |||
| + | |||
| + | \begin{proof} | ||
| + | (věty \ref{thm:vzdalene-pary}) | ||
| + | |||
| + | Definujme graf $G=(S,E)$, kde $\{ x_{i},x_{j}\}\in E\Leftrightarrow\left\Vert x_{i}-x_{j}\right\Vert \geq d$. | ||
| + | Potom $G$ neobsahuje kliku $K_{4}$. Jestliže totiž čtyři body (vrcholy | ||
| + | $G$) tvoří $K_{4}$, tak jsou každé dva z nich od sebe dál než $d$. | ||
| + | Podle předchozího lemmatu lze vybrat tři, které tvoří tupoúhlý trojúhelník. | ||
| + | Obě ,,odvěsny{}`` tohoto trojúhelníka jsou delší než $d\geq\frac{1}{\sqrt{2}}$, | ||
| + | a tak je ,,přepona{}`` delší než $1$, což je spor. | ||
| + | |||
| + | Podle Turánovy věty pro $p=4$ potom platí\[ | ||
| + | \# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right)=\frac{n^{2}}{3}.\] | ||
| + | Nyní zbývá dokázat, že této mezi se lze přiblížit. Za tím účelem se | ||
| + | podívejme na důkaz Turánovy věty. Počtu hran $\frac{n^{2}}{3}$ se | ||
| + | dosahuje, jestliže graf $G$ je rozdělen do $p-1=3$ ,,knedlíků{}``, | ||
| + | v nichž nevedou hrany (body z jednoho ,,knedlíku{}`` jsou v rovině | ||
| + | blízko sebe) a mezi nimiž naopak vedou všechny hrany (celé ,,knedlíky{}`` | ||
| + | jsou v rovině daleko od sebe), a jestliže počet vrcholů v každém ,,knedlíku{}`` | ||
| + | je $\frac{n}{p-1}=\frac{n}{3}$. Protože to však nemusí být celé číslo, | ||
| + | lze ve skutečnosti dosáhnout počtu hran jen $\left[\frac{n^{2}}{3}\right]$. | ||
| + | Dodejme, že popsané uspořádání přesně odpovídá pravé části obrázku | ||
| + | \ref{cap:vzdalene-pary}. | ||
| + | \end{proof} | ||
| + | |||
| + | \subsection{Erdösova věta} | ||
| + | |||
| + | \begin{lem*} | ||
| + | \textbf{\emph{\label{lem:jensenova-nerovnost}(Jensenova nerovnost)}} | ||
| + | |||
| + | Nechť $f:[a,b]\mapsto\R$ je konvexní funkce, tj.\[ | ||
| + | \left(\forall x_{1},x_{2}\in[a,b]\right)\left(\forall\lambda\in[0,1]\right)\left(\lambda f(x_{1})+(1-\lambda)f(x_{2})\geq f(\lambda x_{1}+(1-\lambda)x_{2}\right).\] | ||
| + | Nechť $\alpha_{i}\in\R_{0}^{+}$ pro každé $i\in\hat{n}$, $\sum_{i=1}^{n}\alpha_{i}=1$ | ||
| + | a nechť $x_{i}\in[a,b]$ pro každé $i\in\hat{n}$. Potom\[ | ||
| + | \sum_{i=1}^{n}\alpha_{i}f(x_{i})\geq f\left(\sum_{i=1}^{n}\alpha_{i}x_{i}\right).\] | ||
| + | |||
| + | \end{lem*} | ||
| + | \begin{proof} | ||
| + | Snadno se ukáže indukcí podle $n$, byl proveden například v \cite{TIN}. | ||
| + | \end{proof} | ||
| + | \begin{cor*} | ||
| + | Za stejných předpokladů platí i\begin{equation} | ||
| + | \frac{1}{n}\sum_{i=1}^{n}f(x_{i})\geq f\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}\right).\label{eq:konvexni-fce}\end{equation} | ||
| + | |||
| + | \end{cor*} | ||
| + | \begin{proof} | ||
| + | Položíme $\alpha_{i}=\frac{1}{n}$ pro každé $i\in\hat{n}$. | ||
| + | \end{proof} | ||
| + | \begin{thm} | ||
| + | \textbf{\emph{(Erdös)}} | ||
| + | |||
| + | Nechť $G=(V,E)$ je graf, který neobsahuje jako svůj podgraf $K_{r,r}$ | ||
| + | (úplný bipartitní graf na $r+r$ vrcholech). Potom\[ | ||
| + | \# E\leq C_{r}\cdot n^{2-\frac{1}{r}},\] | ||
| + | kde $C_{r}$ je konstanta nezávislá na $n=\# V$. | ||
| + | \end{thm} | ||
| + | \begin{rem*} | ||
| + | Vždy platí $\# E\leq\binom{n}{2}\leq\frac{n^{2}}{2}$. Turánova věta | ||
| + | omezuje počet hran grafu bez $K_{p}$ podle vztahu (\ref{eq:turan}), | ||
| + | tj. řádově stejně. Erdösova věta však udává řádově \emph{menší} omezení. | ||
| + | \end{rem*} | ||
| + | \begin{proof} | ||
| + | Nechť $G=(V,E)$, kde BÚNO $V=\hat{n}$, je graf bez $K_{r,r}$. Vytvoříme | ||
| + | nový bipartitní graf $G'$, který bude definován na základě grafu | ||
| + | $G$ jako $G'=(V_{1}\cup V_{2},E')$, kde $V_{1}=V$ a $V_{2}=\binom{V}{r}$ | ||
| + | je množina všech $r$-prvkových podmnožin $V$. Přitom \[ | ||
| + | \{\underbrace{i}_{\in V_{1}},\underbrace{\{ k_{1},...,k_{r}\}}_{\in V_{2}}\}\in E',\] | ||
| + | právě když $\{ k_{1},...,k_{r}\}\subset N(i)$ v grafu $G$, tj, | ||
| + | právě když $\left(\forall j\in\hat{r}\right)\left(\{ i,k_{j}\}\in E\right)$. | ||
| + | |||
| + | Základem odvození požadované nerovnosti bude vyjádření počtu hran | ||
| + | v grafu $G'$ dvěma různými způsoby, a to jednak jako počet hran vycházejících | ||
| + | z $V_{1}$, a jednak jako \emph{odhad} počtu hran vycházejících z | ||
| + | $V_{2}$: | ||
| + | \begin{enumerate} | ||
| + | \item Z definice $E'$ plyne, že z $i\in V_{1}$ vede v $G'$ tolik hran, | ||
| + | kolik je $r$-prvkových podmnožin množiny sousedů vrcholu $i$:\[ | ||
| + | d_{G'}(i)=\binom{d_{G}(i)}{r}.\] | ||
| + | Přitom pokud $d_{G}(i)=\# N_{G}(i)<r$, pak $d_{G'}(i)=0$, což je | ||
| + | v souladu s definicí kombinačního čísla. Počet všech hran v $G'$ | ||
| + | je tedy\[ | ||
| + | \sum_{i=1}^{n}\binom{d_{G}(i)}{r}.\] | ||
| + | |||
| + | \item Platí $d_{G'}(\{ k_{1},...,k_{r}\})\leq r-1$. V opačném případě by | ||
| + | totiž z definice $E'$ existovalo (alespoň) $r$ vrcholů $l_{1},...,l_{r}$ | ||
| + | v grafu $G$ různých od $k_{1},...,k_{r}$, které by byly napojeny | ||
| + | na všechny vrcholy $k_{1},...,k_{r}$. To by ale znamenalo, že $G$ | ||
| + | obsahuje $K_{r,r}$. Různost vrcholů, tj. skutečnost, že\[ | ||
| + | \left(\forall j\in\hat{r}\right)\left(l_{j}\notin\{ k_{1},...,k_{r}\}\right)\] | ||
| + | plyne z toho, že žádný vrchol v $G$ není v hraně sám se sebou. Proto | ||
| + | žádný $k_{j}\in V_{1}$ nemůže být v grafu $G'$ spojen hranou s vrcholem | ||
| + | $\{ k_{1},...,k_{r}\}\in V_{2}$. Z uvedené úvahy plyne, že počet | ||
| + | hran v $G'$ musí být menší nebo roven než\[ | ||
| + | (r-1)\underbrace{\binom{n}{r}}_{\# V_{2}}.\] | ||
| + | |||
| + | \end{enumerate} | ||
| + | Srovnáním obou vyjádření dostáváme nerovnost\begin{equation} | ||
| + | \sum_{i=1}^{n}\binom{d_{G}(i)}{r}\leq(r-1)\binom{n}{r},\label{eq:erdos-nerovnost1}\end{equation} | ||
| + | kterou již budeme jen dále odhadovat a upravovat do požadovaného tvaru. | ||
| + | Pokud \[ | ||
| + | \frac{1}{n}\underbrace{\sum_{i=1}^{n}d_{G}(i)}_{2\# E}\leq r-1,\] | ||
| + | tak potom \[ | ||
| + | \# E\leq\frac{1}{2}(r-1)n\leq\underbrace{(r-1)}_{C_{r}}n^{2-\frac{1}{r}}\] | ||
| + | a není co dokazovat. Předpokládejme proto \begin{equation} | ||
| + | \frac{1}{n}\sum_{i=1}^{n}d_{G}(i)\geq r.\label{eq:erdos-predp}\end{equation} | ||
| + | Definujme konvexní funkci\[ | ||
| + | f(x)=\begin{cases} | ||
| + | \binom{x}{r} & x\geq r\\ | ||
| + | 0 & x<r\end{cases},\] | ||
| + | kde dodefinování nulou je potřebné jen pro $x$ neceločíselné. Potom | ||
| + | $f\left(d_{G}(i)\right)=\binom{d_{G}(i)}{r}$ a podle (\ref{eq:konvexni-fce}) | ||
| + | platí\[ | ||
| + | n\cdot\binom{\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)}{r}=n\cdot f\left(\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)\right)\leq\sum_{i=1}^{n}f(d_{G}(i))=\sum_{i=1}^{n}\binom{d_{G}(i)}{r},\] | ||
| + | přičemž levá strana je nenulová, takže ji lze použít k dalším odhadům | ||
| + | (proto je důležitý předpoklad \ref{eq:erdos-predp}). Použijeme-li | ||
| + | tento odhad v (\ref{eq:erdos-nerovnost1}), dostaneme\[ | ||
| + | n\cdot\binom{\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)}{r}\leq(r-1)\binom{n}{r},\] | ||
| + | neboli při označení $m=\# E$\begin{equation} | ||
| + | n\cdot\binom{2m/n}{r}\leq(r-1)\binom{n}{r}.\label{eq:erdos-nerovnost2}\end{equation} | ||
| + | Kombinační číslo $\binom{n}{k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$ | ||
| + | lze odhadnout zdola a shora\[ | ||
| + | \frac{(n-k+1)^{k}}{k!}\leq\binom{n}{k}\leq\frac{n^{k}}{k!},\] | ||
| + | což pro náš případ znamená\[ | ||
| + | n\frac{\left(\frac{2m}{n}-r+1\right)^{r}}{r!}\leq n\binom{2m/n}{r}\leq(r-1)\binom{n}{r}\leq(r-1)\frac{n^{r}}{r!}.\] | ||
| + | Vynásobíme $\frac{r!}{n}$ a odmocníme $\sqrt[r]{...}$, takže dostaneme\[ | ||
| + | \frac{2m}{n}-r+1\leq\sqrt[r]{r-1}n^{1-\frac{1}{r}}\] | ||
| + | a už jen upravujeme:\[ | ||
| + | m\leq\frac{n}{2}\left(\sqrt[r]{r-1}n^{1-\frac{1}{r}}+r-1\right)=\frac{1}{2}\sqrt[r]{r-1}n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n\leq\frac{1}{2}\sqrt[r]{r-1}n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n^{2-\frac{1}{r}}\leq\] | ||
| + | \[ | ||
| + | \leq\frac{1}{2}(r-1)n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n^{2-\frac{1}{r}}\leq\underbrace{(r-1)}_{C_{r}}n^{2-\frac{1}{r}}\] | ||
| + | |||
| + | \end{proof} | ||
| + | \begin{rem*} | ||
| + | Pro $r=2$, tj. pro graf bez $K_{2,2}=C_{4}$ máme odhad\[ | ||
| + | \# E\leq C_{r}\cdot n^{3/2}.\] | ||
| + | Nerovnost (\ref{eq:erdos-nerovnost2}) lze však v tomto případě upravovat | ||
| + | šikovněji, a tak získat (trochu) přísnější odhad:\begin{eqnarray*} | ||
| + | n\frac{\frac{1}{n}2m\left(\frac{1}{n}2m-1\right)}{2} & \leq & \frac{n(n-1)}{2}\\ | ||
| + | 2m(2m-n) & \leq & n^{3}-n^{2}\\ | ||
| + | 4m^{2}-2nm-n^{3}+n^{2} & \leq & 0\end{eqnarray*} | ||
| + | Kvadratickou rovnici pro počet hran $m$ vyřešíme:\[ | ||
| + | m_{1,2}=\frac{2n\pm\sqrt{4n^{2}-16(-n^{3}+n^{2})}}{8}=\frac{n\pm n\sqrt{4n-3}}{4}.\] | ||
| + | Jeden kořen je záporný, takže nehraje roli. Dostáváme tedy odhad\begin{equation} | ||
| + | \# E\leq\frac{n+n\sqrt{4n-3}}{4}=\frac{1}{4}n\left(1+\sqrt{4n-3}\right).\label{eq:odhad-E-bez-K22}\end{equation} | ||
| + | V následujícím ukážeme, jak se mu lze vhodnou konstrukcí grafu přiblížit. | ||
| + | \end{rem*} | ||
| + | |||
| + | \subsection{Graf s $\# E$ blízkým Erdösovu odhadu} | ||
| + | |||
| + | Zkonstruujeme graf $G=(V,E)$ neobsahující $K_{2,2}=C_{4}$ s počtem | ||
| + | hran blížícím se odhadu (\ref{eq:odhad-E-bez-K22}). V následujícím | ||
| + | velmi pěkném postupu se využije mnoho znalostí z různých partií matematiky. | ||
| + | |||
| + | Nechť $p$ je prvočíslo. Uvažujme těleso zbytkových tříd $\Z_{p}=\{0,1,2,...,p-1\}$ | ||
| + | a vektorový prostor $\Z_{p}^{3}$ nad tělesem $\Z_{p}$. Vrcholy grafu | ||
| + | $G$ budou představovat přímky v $\Z_{p}^{3}$ procházející počátkem. | ||
| + | V tomto prostoru má každá taková přímka právě $p$ bodů, protože ji | ||
| + | lze vyjádřit jako lineární obal jejího směrového vektoru, který je | ||
| + | z definice roven\[ | ||
| + | [\underbrace{(x_{1},x_{2},x_{3})}_{\vec{x}}]_{\lambda}=\left\{ \left.(kx_{1},kx_{2},kx_{3})\right|k\in\Z_{p}\right\} .\] | ||
| + | Různých nenulových vektorů v $\Z_{p}^{3}$ je zřejmě $p^{3}-1$. Protože | ||
| + | každá přímka má $p$ bodů, z nichž $p-1$ jsou nenulové vektory, je | ||
| + | možné ji reprezentovat libovolným z $p-1$ směrových vektorů. Proto | ||
| + | počet všech přímek procházejících počátkem je roven\[ | ||
| + | \# V=\frac{p^{3}-1}{p-1}=p^{2}+p+1.\] | ||
| + | |||
| + | |||
| + | Označme si (vybrané) směrové vektory přímek ( = vrcholů grafu $G$) | ||
| + | $v_{1},v_{2},...,v_{p^{2}+p+1}$ po řadě jako $\vec{x}_{1},...,\vec{x}_{p^{2}+p+1}$, | ||
| + | tj. nechť platí\[ | ||
| + | \left(\forall i\in\{1,...,p^{2}+p+1\}\right)\left(v_{i}=[\vec{x}_{i}]_{\lambda}\right).\] | ||
| + | Dále definujme ,,pseudoskalární{}`` součin vektorů $\vec{x}=(x_{1},x_{2},x_{3})$ | ||
| + | a $\vec{y}=(y_{1},y_{2},y_{3})$ z prostoru $\Z_{p}^{3}$ jako\[ | ||
| + | \left\langle \vec{x},\vec{y}\right\rangle =x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}.\] | ||
| + | Řekneme, že vektor $\vec{x}$ je kolmý na vektor $\vec{y}$, jestliže | ||
| + | $\left\langle \vec{x},\vec{y}\right\rangle =0$. Protože existují | ||
| + | vektory, které jsou kolmé samy na sebe, nejedná se o pravý skalární | ||
| + | součin. Nyní množinu hran $E$ definujeme jako\[ | ||
| + | E=\left\{ \left.\{ v_{i},v_{j}\}\right|i\neq j\wedge\left\langle \vec{x}_{i},\vec{x}_{j}\right\rangle =0\right\} .\] | ||
| + | |||
| + | |||
| + | \begin{example*} | ||
| + | Abychom si dobře uvědomili, jak je graf $G$ definován, ukážeme si | ||
| + | jej pro $p=2$. Na obrázku \ref{cap:konstrukce-Z2} jsou jednotlivé | ||
| + | vrcholy grafu označeny svými směrovými vektory. Je vidět, že například | ||
| + | vektor $(1,1,0)$ je kolmý sám na sebe.% | ||
| + | \begin{figure} | ||
| + | \begin{center} | ||
| + | %Title: konstrukce_Z2.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:35:44 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 20.955 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.715 20.003 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.715 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 20.955 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 19.526 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 8.572 19.526 to 8.572 20.973 | ||
| + | \putrule from 8.572 20.955 to 12.876 20.955 | ||
| + | \putrule from 12.859 20.955 to 12.859 17.621 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\plot 8.572 20.955 10.715 20.003 / | ||
| + | \putrule from 10.715 20.003 to 10.715 18.574 | ||
| + | \plot 10.715 18.574 12.859 17.621 / | ||
| + | \putrule from 12.859 17.621 to 8.555 17.621 | ||
| + | \putrule from 8.572 17.621 to 8.572 19.526 | ||
| + | \plot 8.572 19.526 10.715 20.003 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,1,1)$}% | ||
| + | } [lB] at 13.214 17.503 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,0,1)$}% | ||
| + | } [lB] at 9.167 18.455 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,0,1)$}% | ||
| + | } [lB] at 7.023 19.408 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,1,0)$}% | ||
| + | } [lB] at 11.070 19.884 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,1,1)$}% | ||
| + | } [lB] at 13.214 20.836 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,0,0)$}% | ||
| + | } [lB] at 7.023 20.836 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,1,0)$}% | ||
| + | } [lB] at 7.023 17.503 | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 6.991 21.207 and 13.246 17.344 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | |||
| + | |||
| + | \caption{\label{cap:konstrukce-Z2}Konstrukce $G$ pro $p=2$} | ||
| + | \end{figure} | ||
| + | |||
| + | \end{example*} | ||
| + | Ukážeme, že pro libovolné prvočíslo $p$ takto definovaný graf $G$ | ||
| + | neobsahuje $K_{2,2}=C_{4}$. Kdyby $G$ obsahoval $C_{4}$, existovaly | ||
| + | by v něm vrcholy $v_{i},v_{j}$ spojené hranami s dalšími dvěma vrcholy | ||
| + | takto: | ||
| + | |||
| + | \hfill{} | ||
| + | \begin{center} | ||
| + | %Title: konstrukce_kolmost.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:16:56 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.479 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.479 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.955 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\plot 9.049 20.955 7.620 20.479 / | ||
| + | \plot 7.620 20.479 9.049 20.003 / | ||
| + | \plot 9.049 20.003 10.478 20.479 / | ||
| + | \plot 10.478 20.479 9.049 20.955 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}% | ||
| + | } [lB] at 10.952 20.360 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}% | ||
| + | } [lB] at 6.905 20.360 | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.003 | ||
| + | }% | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 6.873 21.088 and 10.983 19.869 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | \hfill{}~ | ||
| + | |||
| + | \noindent Podívejme se však, kolik vrcholů může být hranami napojeno | ||
| + | na $v_{i}$ i na $v_{j}$. Označme $\vec{x}_{i}=(\alpha_{1},\alpha_{2},\alpha_{3})$, | ||
| + | $\vec{x}_{j}=(\beta_{1},\beta_{2},\beta_{3})$ a hledejme $\vec{y}=(\gamma_{1},\gamma_{2},\gamma_{3})$ | ||
| + | kolmý na $\vec{x}_{i}$ i na $\vec{x}_{j}$. Pro $\vec{y}$ musí platit\begin{eqnarray*} | ||
| + | 0=\left\langle \vec{x}_{i},\vec{y}\right\rangle & = & \alpha_{1}\gamma_{1}+\alpha_{2}\gamma_{2}+\alpha_{3}\gamma_{3}\\ | ||
| + | 0=\left\langle \vec{x}_{j},\vec{y}\right\rangle & = & \beta_{1}\gamma_{1}+\beta_{2}\gamma_{2}+\beta_{3}\gamma_{3},\end{eqnarray*} | ||
| + | což znamená, že $\gamma_{1},\gamma_{2},\gamma_{3}$ jsou řešením homogenní | ||
| + | soustavy lineárních rovnic s maticí\[ | ||
| + | \left(\begin{array}{ccc} | ||
| + | \alpha_{1} & \alpha_{2} & \alpha_{3}\\ | ||
| + | \beta_{1} & \beta_{2} & \beta_{3}\end{array}\right).\] | ||
| + | Protože $\vec{x}_{i},\vec{x}_{j}$ jsou směrové vektory různých přímek, | ||
| + | jsou lineárně nezávislé, a tato matice má tedy hodnost $2$. Podle | ||
| + | Frobeniovy věty o řešení soustav lineárních rovnic pak existuje jediné | ||
| + | lineárně nezávislé řešení $\vec{y}$ této soustavy. Existuje tedy | ||
| + | jediná přímka se směrovým vektorem $\vec{y}$, která je kolmá na obě | ||
| + | přímky $v_{i},v_{j}$, neboli tato přímka jako vrchol grafu $G$ je | ||
| + | jediná, která je hranami spojena s $v_{i}$ i s $v_{j}$. Proto $G$ | ||
| + | neobsahuje $C_{4}$. | ||
| + | |||
| + | Nyní postupně vyčíslíme počet hran v grafu $G$. Hledejme stupeň $d_{G}(v_{i})$ | ||
| + | nějakého pevného vrcholu $v_{i}\in V$, neboli počet různých přímek, | ||
| + | které jsou kolmé na $v_{i}$. Ten je roven počtu \emph{různých} vektorů | ||
| + | $\vec{y}$ kolmých na $\vec{x}_{i}$, přičemž dva takové vektory jsou | ||
| + | \emph{různé}, když jsou lineárně nezávislé (to ovšem neznamená, že | ||
| + | všechny tyto vektory mají tvořit LN soubor). Použijeme-li již zavedené | ||
| + | značení pro $\vec{x}_{i}$ a $\vec{y}$, musí $\vec{y}$ splňovat | ||
| + | rovnici\[ | ||
| + | 0=\left\langle \vec{x}_{i},\vec{y}\right\rangle =\alpha_{1}\gamma_{1}+\alpha_{2}\gamma_{2}+\alpha_{3}\gamma_{3},\] | ||
| + | která má $2$ LN řešení $\vec{y}_{1},\vec{y}_{2}$. Počet všech řešení | ||
| + | této soustavy je $p^{2}$, protože jsou to právě vektory\[ | ||
| + | \vec{y}=k_{1}\vec{y}_{1}+k_{2}\vec{y}_{2}\ ,\; k_{1},k_{2}\in\Z_{p}.\] | ||
| + | Máme tedy $p^{2}-1$ nenulových řešení, ale vždy $p-1$ z nich je | ||
| + | kolineárních, tj. jedná se o směrové vektory téže přímky. \underbar{Počet | ||
| + | různých přímek kolmých na $v_{i}$}, tj. počet \emph{různých} vektorů | ||
| + | $\vec{y}$ kolmých na $\vec{x}_{i}$, je tedy\[ | ||
| + | \frac{p^{2}-1}{p-1}=p+1.\] | ||
| + | Tento výsledek si pro pozdější použití dobře zapamatujme. Nejedná | ||
| + | se totiž ještě o $d_{G}(v_{i})$, protože záleží na tom, zda $\vec{x}_{i}$ | ||
| + | je kolmý sám na sebe. Zatím tedy můžeme shrnout:\[ | ||
| + | \left(\forall i\in\{1,...,p^{2}+p+1\}\right)\left(d_{G}(v_{i})=\begin{cases} | ||
| + | p+1 & \left\langle \vec{x}_{i},\vec{x}_{i}\right\rangle \neq0\\ | ||
| + | p & \left\langle \vec{x}_{i},\vec{x}_{i}\right\rangle =0\end{cases}\right).\] | ||
| + | Dalším naším úkolem je zjistit, v kolika případech je $\vec{x}_{i}$ | ||
| + | kolmý sám na sebe. Jestliže to dokážeme, bude už snadné vyjádřit celkový | ||
| + | počet hran grafu $G$. Definujme čtvercovou matici $\vec{A}$ řádu | ||
| + | $p^{2}+p+1$, jejíž prvky mají hodnotu\[ | ||
| + | \vec{A}_{ij}=\begin{cases} | ||
| + | 1 & \left\langle \vec{x}_{i},\vec{x}_{j}\right\rangle =0\\ | ||
| + | 0 & \textrm{jinak}.\end{cases}\] | ||
| + | Potom $\vec{A}_{ii}=1$, právě když $\vec{x}_{i}$ je kolmý sám na | ||
| + | sebe. Hledaný počet přímek kolmých na sebe sama je tedy roven počtu | ||
| + | nenulových prvků na diagonále matice $\vec{A}$, neboli její stopě | ||
| + | $\Tr\vec{A}$. Protože náš pseudoskalární součin je symetrický, je | ||
| + | i matice $\vec{A}$ symetrická, a tedy diagonalizovatelná. Podobnostní | ||
| + | transformace zachovává stopu, a proto $\Tr\vec{A}$ je rovna součtu | ||
| + | vlastních čísel $\vec{A}$. | ||
| + | |||
| + | $\vec{A}$ nemá zrovna jednoduchý tvar. Pro určení vlastních čísel | ||
| + | proto sestavíme $\vec{A}^{2}$, která vypadá mnohem lépe. Z definice | ||
| + | maticového násobení máme\[ | ||
| + | \vec{A}_{ij}^{2}=\sum_{k=1}^{p^{2}+p+1}\vec{A}_{ik}\vec{A}_{kj},\] | ||
| + | což znamená, že\[ | ||
| + | \vec{A}_{ij}^{2}=\#\left\{ \left.k\right|\left\langle \vec{x}_{k},\vec{x}_{i}\right\rangle =0\wedge\left\langle \vec{x}_{k},\vec{x}_{j}\right\rangle =0\right\} ,\] | ||
| + | tj. $\vec{A}_{ij}^{2}$ je počet přímek kolmých na $v_{i}$ i $v_{j}$. | ||
| + | My už ale víme, že pro $i\neq j$ je taková přímka právě jedna a pro | ||
| + | $i=j$ je těchto přímek $p+1$. Proto\[ | ||
| + | \vec{A}^{2}=\left(\begin{array}{cccc} | ||
| + | p+1 & 1 & \cdots & 1\\ | ||
| + | 1 & p+1 & \cdots & 1\\ | ||
| + | \vdots & \vdots & \ddots & \vdots\\ | ||
| + | 1 & 1 & \cdots & p+1\end{array}\right)=p\vec{I}+\vec{J},\] | ||
| + | kde $\vec{J}_{ij}=1$ pro každé $i,j$. Vlastní čísla matice $\vec{A}$ | ||
| + | jsou posunuta o $p$ vzhledem k vlastním číslům matice $\vec{J}$:\[ | ||
| + | \left(\vec{J}\vec{x}=\lambda\vec{x}\right)\Leftrightarrow\left(\vec{A}^{2}\vec{x}=(p\vec{I}+\vec{J})\vec{x}=(p+\lambda)\vec{x}\right)\] | ||
| + | Protože $\vec{J}$ má zřejmě hodnost $1$, má $\vec{J}$ jediné nenulové | ||
| + | vlastní číslo $\lambda$ a pak vlastní číslo $0$ s násobností (řád | ||
| + | matice$-1$), tj. $p^{2}+p$. Nenulové vlastní číslo $\vec{J}$ je | ||
| + | rovno řádu matice, tj. $\lambda=p^{2}+p+1$, protože\[ | ||
| + | \vec{J}\left(\begin{array}{c} | ||
| + | 1\\ | ||
| + | 1\\ | ||
| + | \vdots\\ | ||
| + | 1\end{array}\right)=\left(\begin{array}{c} | ||
| + | p^{2}+p+1\\ | ||
| + | p^{2}+p+1\\ | ||
| + | \vdots\\ | ||
| + | p^{2}+p+1\end{array}\right)=(p^{2}+p+1)\left(\begin{array}{c} | ||
| + | 1\\ | ||
| + | 1\\ | ||
| + | \vdots\\ | ||
| + | 1\end{array}\right).\] | ||
| + | Matice $\vec{A}^{2}$ má tedy vlastní číslo $(p^{2}+p+1)+p=(p+1)^{2}$ | ||
| + | s násobností $1$ a vlastní číslo $0+p=p$ s násobností $p^{2}+p$. | ||
| + | Matice $\vec{A}$ má vlastní čísla rovná odmocninám z vlastních čísel | ||
| + | $\vec{A}^{2}$, tj. | ||
| + | |||
| + | \begin{itemize} | ||
| + | \item $p+1$ s násobností $1$ | ||
| + | \item $\sqrt{p}$ s násobností $r$ | ||
| + | \item $-\sqrt{p}$ s násobností $s$ | ||
| + | \end{itemize} | ||
| + | \begin{rem*} | ||
| + | Vlastní číslo $p+1$ jsme mohli u matice zjistit rovnou podle\[ | ||
| + | \vec{A}\left(\begin{array}{c} | ||
| + | 1\\ | ||
| + | 1\\ | ||
| + | \vdots\\ | ||
| + | 1\end{array}\right)=\left(\begin{array}{c} | ||
| + | p+1\\ | ||
| + | p+1\\ | ||
| + | \vdots\\ | ||
| + | p+1\end{array}\right)=(p+1)\left(\begin{array}{c} | ||
| + | 1\\ | ||
| + | 1\\ | ||
| + | \vdots\\ | ||
| + | 1\end{array}\right),\] | ||
| + | protože počet jedniček v každém ($i$-tém) řádku $\vec{A}$, což je | ||
| + | počet přímek kolmých na $v_{i}$, je roven $p+1$. | ||
| + | \end{rem*} | ||
| + | Když nyní známe vlastní čísla $\vec{A}$, můžeme konečne vyjádřit\[ | ||
| + | \Tr\vec{A}=(p+1)+(r-s)\sqrt{p},\] | ||
| + | a protože stopa celočíselné matice nemůže být neceločíselná (přitom | ||
| + | $p$ je prvočíslo, takže $\sqrt{p}\notin\N)$, musí nutně $r=s$ a | ||
| + | tedy\[ | ||
| + | \Tr\vec{A}=p+1.\] | ||
| + | |||
| + | |||
| + | Nyní tedy víme, že počet vrcholů $G$ se stupněm $p$ je $p+1$. Ostatních | ||
| + | $p^{2}$ vrcholů má stupeň $p+1$. Proto již lze určit počet hran | ||
| + | v grafu $G$:\[ | ||
| + | 2\# E=\sum_{v\in V}d_{G}(v)=(p+1)p+p^{2}(p+1)=p(p+1)^{2},\] | ||
| + | \[ | ||
| + | \# E=\frac{p(p+1)^{2}}{2}.\] | ||
| + | Abychom mohli $\# E$ srovnat s (\ref{eq:odhad-E-bez-K22}), musíme | ||
| + | jej vyjádřit pomocí $n=\# V$. Z rovnosti \begin{equation} | ||
| + | n=p^{2}+p+1\label{eq:konstrukce-pocet-vrcholu}\end{equation} | ||
| + | tedy získáme\[ | ||
| + | p=\frac{-1+\sqrt{4n-3}}{2}\] | ||
| + | a po vhodné úpravě, která umožní dosadit za $p^{2}+p$ z (\ref{eq:konstrukce-pocet-vrcholu}), | ||
| + | dostaneme\[ | ||
| + | \# E=\frac{p(p+1)^{2}}{2}=\frac{p+1}{2}(p^{2}+p)=\frac{1+\sqrt{4n-3}}{4}(n-1)=\frac{1}{4}(n-1)\left(1+\sqrt{4n-3}\right).\] | ||
| + | Přitom z Erdösovy věty máme odhad\[ | ||
| + | \# E\leq\frac{1}{4}n\left(1+\sqrt{4n-3}\right).\] | ||
| + | Je tedy vidět, že pro $n=p^{2}+p+1$, kde $p$ je prvočíslo, je tento | ||
| + | odhad docela těsný. | ||
| + | |||
| + | |||
| + | \subsection{Počet $K_{3}$ a $\bar{K}_{3}$ v grafu} | ||
| + | |||
| + | \begin{thm} | ||
| + | Nechť $G=(V,E)$ je graf na $n$ vrcholech. Potom počet klik $K_{3}$ | ||
| + | a podgrafů $\bar{K}_{3}$ v grafu $G$ je alespoň \[ | ||
| + | \frac{n(n-1)(n-5)}{24}.\] | ||
| + | |||
| + | \end{thm} | ||
| + | \begin{proof} | ||
| + | Tři vrcholy z $n$ vrcholů lze vybrat $\binom{n}{3}$ způsoby. Až | ||
| + | na izomorfismus existují pouze $4$ podgrafy (tj. $4$ \emph{typy} | ||
| + | podgrafů), které mohou být indukované těmito třemi vrcholy. Jestliže | ||
| + | obrázkem podgrafu umístěným do kroužku rozumíme počet podgrafů tohoto | ||
| + | typu v grafu $G$, můžeme zapsat následující rovnici: | ||
| + | |||
| + | \hfill{} | ||
| + | \begin{center} | ||
| + | %Title: K3_rovnice1.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:48:56 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 15.953 18.754 center at 15.418 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.716 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.121 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.420 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 13.811 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 13.513 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 14.110 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 14.347 18.754 center at 13.811 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 12.738 18.754 center at 12.203 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.501 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 11.906 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.205 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.596 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.298 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.894 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 11.132 18.754 center at 10.596 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 15.716 18.574 to 15.119 18.574 | ||
| + | \plot 15.119 18.574 15.418 19.111 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 13.513 18.574 to 14.108 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\plot 10.298 18.574 10.596 19.111 / | ||
| + | \plot 10.596 19.111 10.892 18.574 / | ||
| + | \putrule from 10.892 18.574 to 10.298 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\binom{n}{3}}$}% | ||
| + | } [lB] at 16.133 18.633 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% | ||
| + | } [lB] at 14.465 18.633 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% | ||
| + | } [lB] at 11.250 18.633 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% | ||
| + | } [lB] at 12.859 18.633 | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 10.029 19.321 and 16.165 18.186 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | \hfill{}~ | ||
| + | |||
| + | \noindent Vezměme nyní vrchol $v\in V$. Z něj vede hrana do $d_{G}(v)$ | ||
| + | vrcholů a do dalších $n-1-d_{G}(v)$ z něj hrana nevede. Počet \emph{uspořádaných} | ||
| + | trojic $(v,u,w)$ takových, že $\{ v,u\}\in E$ a zároveň $\{ v,w\}\notin E$, | ||
| + | je tedy\[ | ||
| + | \sum_{v\in V}d_{G}(v)\left(n-1-d_{G}(v)\right).\] | ||
| + | Každé trojici vrcholů z $V$, která v grafu $G$ indukuje podgrafy | ||
| + | \begin{center} | ||
| + | %Title: K3_podgraf3.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:10:40 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.298 26.312 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.597 26.848 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 0.296 26.312 to 0.893 26.312 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.893 26.312 | ||
| + | }% | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 0.222 26.922 and 0.969 26.238 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | nebo | ||
| + | \begin{center} | ||
| + | %Title: K3_podgraf4.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:10:56 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.298 26.312 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.597 26.848 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 0.891 26.314 to 0.296 26.314 | ||
| + | \plot 0.296 26.314 0.595 26.848 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.893 26.312 | ||
| + | }% | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 0.222 26.922 and 0.969 26.238 | ||
| + | \endpicture}, | ||
| + | \end{center} | ||
| + | však přísluší právě dva různé výběry vrcholu $v$, tj. právě dvě \emph{uspořádané} | ||
| + | trojice $(v,u,w)$ daných vlastností. Proto | ||
| + | |||
| + | \noindent \hfill{} | ||
| + | \begin{center} | ||
| + | %Title: K3_rovnice2.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:29:20 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.561 26.253 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.263 25.718 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.857 25.718 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 3.095 25.897 center at 2.559 25.897 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 1.488 25.897 center at 0.953 25.897 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 1.251 25.718 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.654 25.718 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.953 26.253 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 2.857 25.718 to 2.261 25.718 | ||
| + | \plot 2.261 25.718 2.559 26.255 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 0.654 25.718 to 1.249 25.718 | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% | ||
| + | } [lB] at 1.607 25.777 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\frac{1}{2}\sum_{v \in V}d_{G}(v)\left(n-1-d_{G}(v)\right).}$}% | ||
| + | } [lB] at 3.274 25.777 | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 0.385 26.513 and 3.306 25.330 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | \hfill{}~ | ||
| + | |||
| + | Toto číslo nyní odhadneme shora. Všechny členy sumy, které jsou tvaru | ||
| + | $x(n-1-x)$, jsou $\leq\left(\frac{n-1}{2}\right)^{2}$, protože graf | ||
| + | funkce $x(n-1-x)=-\left(x-\frac{n-1}{2}\right)^{2}+\left(\frac{n-1}{2}\right)^{2}$ | ||
| + | je parabola s maximem $\left(\frac{n-1}{2}\right)^{2}$ v bodě $x=\frac{n-1}{2}$. | ||
| + | Tím současně odhadneme zdola počet $K_{3}$ a $\bar{K}_{3}$ v grafu | ||
| + | $G$: | ||
| + | |||
| + | \hfill{} | ||
| + | \begin{center} | ||
| + | %Title: K3_rovnice3.fig | ||
| + | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
| + | %%CreationDate: Thu Feb 12 19:50:40 1970 | ||
| + | %%User: Pavel Strachota@DIGITHELL (DIGITHELL) | ||
| + | \font\thinlinefont=cmr5 | ||
| + | % | ||
| + | \begingroup\makeatletter\ifx\SetFigFont\undefined% | ||
| + | \gdef\SetFigFont#1#2#3#4#5{% | ||
| + | \reset@font\fontsize{#1}{#2pt}% | ||
| + | \fontfamily{#3}\fontseries{#4}\fontshape{#5}% | ||
| + | \selectfont}% | ||
| + | \fi\endgroup% | ||
| + | \mbox{\beginpicture | ||
| + | \setcoordinatesystem units <1.00000cm,1.00000cm> | ||
| + | \unitlength=1.00000cm | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | \setshadesymbol ({\thinlinefont .}) | ||
| + | \setlinear | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 16.908 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 16.609 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 17.204 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 17.441 18.754 center at 16.906 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 15.835 18.754 center at 15.299 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.598 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.001 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.299 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 17.204 18.574 to 16.607 18.574 | ||
| + | \plot 16.607 18.574 16.906 19.111 / | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\putrule from 15.001 18.574 to 15.596 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% | ||
| + | } [lB] at 15.953 18.633 | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 11.132 18.754 center at 10.596 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.894 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.298 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.596 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.205 19.109 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 11.906 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness= 0.500pt | ||
| + | \setplotsymbol ({\thinlinefont .}) | ||
| + | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.501 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig ELLIPSE | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees | ||
| + | from 12.738 18.754 center at 12.203 18.754 | ||
| + | }% | ||
| + | % | ||
| + | % Fig POLYLINE object | ||
| + | % | ||
| + | \linethickness=1pt | ||
| + | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
| + | {\color[rgb]{0,0,0}\plot 10.298 18.574 10.596 19.111 / | ||
| + | \plot 10.596 19.111 10.892 18.574 / | ||
| + | \putrule from 10.892 18.574 to 10.298 18.574 | ||
| + | }% | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\Bigg)\geq$}% | ||
| + | } [lB] at 17.560 18.633 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\binom{n}{3}}-\Bigg($}% | ||
| + | } [lB] at 12.918 18.633 | ||
| + | % | ||
| + | % Fig TEXT object | ||
| + | % | ||
| + | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% | ||
| + | } [lB] at 11.250 18.633 | ||
| + | \linethickness=0pt | ||
| + | \putrectangle corners at 10.029 19.321 and 17.592 18.186 | ||
| + | \endpicture} | ||
| + | \end{center} | ||
| + | \hfill{}~ | ||
| + | |||
| + | \noindent \[ | ||
| + | \geq\frac{n(n-1)(n-2)}{6}-n\cdot\frac{1}{2}\left(\frac{n-1}{2}\right)^{2}=\frac{n(n-1)\left(4(n-2)-3(n-1)\right)}{24}=\frac{n(n-1)(n-5)}{24}\] | ||
| + | |||
| + | \end{proof} | ||
| + | |||
| + | \subsection{Odhady $\alpha(G)$ a $\omega(G)$} | ||
| + | |||
| + | V této části přednášky se budeme zabývat odhady maximální velikosti | ||
| + | kliky a nezávislé množiny v grafu. Zopakujte si proto definici \ref{def:klika-nez-mnozina} | ||
| + | z první kapitoly. | ||
| + | |||
| + | \begin{obs} | ||
| + | Pro libovolný graf $G=(V,E)$, $n=\# V$, platí\[ | ||
| + | \alpha(G)\geq\frac{n}{\Delta(G)+1}.\] | ||
| + | |||
| + | \end{obs} | ||
| + | \begin{proof} | ||
| + | Ukážeme konstrukci nezávislé množiny o velikosti alespoň $\frac{n}{\Delta(G)+1}$. | ||
| + | \begin{enumerate} | ||
| + | \item $S:=\emptyset$, $W:=V$. | ||
| + | \item Vezmeme libovolný vrchol $v\in W$ a přesuneme jej z množiny $W$ | ||
| + | do množiny $S$. Všechny sousedy $v$ v grafu $G$ odstraníme z $W$. | ||
| + | Celkem tedy z $W$ odstraníme nejvýše $\Delta(G)+1$ vrcholů. | ||
| + | \item Krok 2 opakujeme, dokud $W\neq\emptyset$. | ||
| + | \end{enumerate} | ||
| + | Je zřejmé, že po provedení popsaného postupu bude $S$ nezávislá množina, | ||
| + | přičemž \[ | ||
| + | \# S\geq\frac{n}{\Delta(G)+1}.\] | ||
| + | |||
| + | \end{proof} | ||
| + | \begin{thm} | ||
| + | \label{thm:odhad-alfa-G-pomoci-ro-G}Pro libovolný graf $G=(V,E)$ | ||
| + | platí\[ | ||
| + | \alpha(G)\geq\frac{n}{\rho(G)+1},\] | ||
| + | kde $\rho(G)$ je průměrný stupeň grafu $G$ (viz. definice \ref{def:stupen-vrcholu}). | ||
| + | \end{thm} | ||
| + | Tuto větu dokážeme za chvíli, neboť snadno vyplyne z věty \ref{thm:odhad-omega-G}. | ||
| + | Nejprve ukážeme slabší odhad $\alpha(G)$: | ||
| + | |||
| + | \begin{thm} | ||
| + | Nechť $G=(V,E)$ s průměrným stupněm $\rho(G)\geq1$. Potom\[ | ||
| + | \alpha(G)\geq\frac{n}{2\Delta(G)}.\] | ||
| + | |||
| + | \end{thm} | ||
| + | \begin{proof} | ||
| + | Provedeme pravděpodobnostní důkaz tohoto tvrzení. Nechť $G$ je pevně | ||
| + | daný graf a označme jako vždy $n=\# V,m=\# E$. Sestrojme \underbar{indukovaný} | ||
| + | podgraf $H\subset G$ tak, že každý $v\in V$ zařadíme do $V(H)$ | ||
| + | nezávisle s pravděpodobností $p\in[0,1]$, kde $p$ zatím nespecifikujeme. | ||
| + | Označme si náhodné veličiny | ||
| + | \begin{lyxlist}{00.00.0000} | ||
| + | \item [$X=\# V(H)$,]což je počet vrcholů grafu $H$, a | ||
| + | \item [$Y=\# E(H)$,]což je počet hran v grafu $H$. | ||
| + | \end{lyxlist} | ||
| + | Vypočítáme střední hodnoty těchto veličin obvyklým způsobem. Pro každý | ||
| + | $v\in V$ zavedeme elementární náhodnou veličinu\[ | ||
| + | X_{v}=\begin{cases} | ||
| + | 1 & v\in V(H)\\ | ||
| + | 0 & v\notin V(H)\end{cases}.\] | ||
| + | Potom\[ | ||
| + | X=\sum_{v\in V}X_{v},\] | ||
| + | \[ | ||
| + | \E X_{v}=1\cdot\Pr(X_{v}=1)+0\cdot\Pr(X_{v}=0)=1\cdot p+0\cdot p=p\] | ||
| + | a\[ | ||
| + | \E X=\sum_{v\in V}\E X_{v}=np.\] | ||
| + | Obdobně vypočítáme střední hodnotu počtu hran. Pro každou hranu $e\in E$, | ||
| + | $e=\{ u,v\}$ zavedeme\[ | ||
| + | Y_{e}=\begin{cases} | ||
| + | 1 & e\in E(H)\\ | ||
| + | 0 & e\notin E(H)\end{cases}.\] | ||
| + | Potom\[ | ||
| + | Y=\sum_{v\in V}Y_{e},\] | ||
| + | \[ | ||
| + | \E Y_{e}=\Pr(Y_{e}=1)=\Pr(u\in V(H)\wedge v\in V(H))=p^{2}\] | ||
| + | a\[ | ||
| + | \E Y=\sum_{e\in E}\E Y_{v}=mp^{2}.\] | ||
| + | |||
| + | |||
| + | Platí ale \[ | ||
| + | \rho(G)=\frac{1}{n}\sum_{v\in V}d_{G}(V)=\frac{2m}{n}\quad\Rightarrow\quad\E Y=p^{2}\frac{\rho(G)\cdot n}{2}.\] | ||
| + | Zvolme nyní $p=\frac{1}{\rho(G)}$. Potom\[ | ||
| + | \E(X-Y)=np-\frac{\rho(G)np^{2}}{2}=\frac{n}{\rho(G)}-\frac{n}{2\rho(G)}=\frac{n}{2\rho(G)}.\] | ||
| + | To znamená, že existuje taková konkrétní realizace indukovaného podgrafu | ||
| + | $H$, že\begin{equation} | ||
| + | X-Y\geq\frac{n}{2\rho(G)}.\label{eq:rozdil-hran-vrch}\end{equation} | ||
| + | Nyní odebereme všechny hrany z tohoto $H$ vždy společně s jedním | ||
| + | jejich koncem. Z původní množiny vrcholů $V(H)$ tak vznikne množina | ||
| + | vrcholů $S$, která je nezávislou množinou v grafu $G$. $H$ je totiž | ||
| + | indukovaný podgraf, takže mezi vrcholy z $S$ již nevedou žádné hrany | ||
| + | ani v grafu $G$. Po ubrání $Y$ hran spolu s $Y$ vrcholy zůstane | ||
| + | v $S$ podle vztahu (\ref{eq:rozdil-hran-vrch}) alespoň $\frac{n}{2\rho(G)}$ | ||
| + | vrcholů, čímž je věta dokázána. | ||
| + | \end{proof} | ||
| + | \begin{thm} | ||
| + | \label{thm:odhad-omega-G}Pro libovolný graf $G=(V,E)$ platí\[ | ||
| + | \omega(G)\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)}.\] | ||
| + | |||
| + | \end{thm} | ||
| + | \begin{proof} | ||
| + | bude opět pravděpodobnostní. BÚNO předpokládejme $V=\hat{n}$. Náhodně | ||
| + | vybereme permutaci $\pi\in S_{n}$, které přiřadíme množninu $C_{\pi}\subset V$ | ||
| + | takto: | ||
| + | \begin{itemize} | ||
| + | \item $\pi(1)\in C_{\pi}$ | ||
| + | \item pro $i>1$ dáme vrchol $\pi(i)$ do $C_{\pi}$, pokud $\left(\forall j<i\right)\left(\{\pi(i),\pi(j)\}\in E\right)$, | ||
| + | tj. vrchol se dostane do $C_{\pi}$, jestliže je v hraně se všemi | ||
| + | předchozími vrcholy při jejich uspořádání podle permutace $\pi$. | ||
| + | \end{itemize} | ||
| + | $C_{\pi}$ je zřejmě klika v $G$. Její velikost je náhodná veličina, | ||
| + | kterou označíme $X$. Nyní postupujeme jako obvykle: Ukážeme-li \[ | ||
| + | \E X\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)},\] | ||
| + | bude důkaz hotov, protože pak existuje konkrétní $C_{\pi}$, pro niž | ||
| + | je $X\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)}$. Pro každé $v\in V$ | ||
| + | definujeme\[ | ||
| + | X_{v}=\begin{cases} | ||
| + | 1 & v\in C_{\pi}\\ | ||
| + | 0 & v\notin C_{\pi}\end{cases}.\] | ||
| + | Potom\[ | ||
| + | \E X_{v}=\Pr(v\in C_{\pi})=\frac{1}{n-d_{G}(v)},\] | ||
| + | což nyní dokážeme. Aby $v\in C_{\pi}$, tak vrcholy, se kterými $v$ | ||
| + | není v hraně, musí být v permutaci $\pi$ umístěny až za ním. Na umístění | ||
| + | jeho sousedů nezáleží. Počet vrcholů, se kterými $v$ není v hraně, | ||
| + | a to včetně vrcholu $v$ samotného, je $n-d_{G}(v)$. Počet způsobů, | ||
| + | kterými lze $n-d_{G}(v)$ vrcholů uspořádat tak, aby $v$ byl na prvním | ||
| + | místě, je $\left(n-d_{G}(v)-1\right)!$. Počet všech uspořádání $n-d_{G}(v)$ | ||
| + | vrcholů je $\left(n-d_{G}(v)\right)!$, a proto\[ | ||
| + | \Pr(v\in C_{\pi})=\frac{\left(n-d_{G}(v)-1\right)!}{\left(n-d_{G}(v)\right)!}=\frac{1}{n-d_{G}(v)}\] | ||
| + | Konečně tedy můžeme vyčíslit\[ | ||
| + | \E X=\sum_{v\in V}X_{v}=\sum_{v\in V}\frac{1}{n-d_{G}(v)}.\] | ||
| + | |||
| + | \end{proof} | ||
| + | Důsledkem této věty je věta \ref{thm:odhad-alfa-G-pomoci-ro-G}, kterou | ||
| + | nyní dokážeme. | ||
| + | |||
| + | \begin{proof} | ||
| + | Nechť $G$ je libovolný graf. Potom podle předchozí věty je\[ | ||
| + | \omega(\bar{G})\geq\sum_{v\in V}\frac{1}{n-d_{\bar{G}}(v)},\] | ||
| + | přičemž platí $d_{\bar{G}}(v)=n-1-d_{G}(v)$ a $\alpha(G)=\omega(\bar{G})$. | ||
| + | Proto\begin{equation} | ||
| + | \alpha(G)\geq\sum_{v\in V}\frac{1}{1+d_{G}(v)}.\label{eq:odhad-alfa-G}\end{equation} | ||
| + | Protože funkce $\frac{1}{1+x}$ je na intervalu $[0,+\infty)$ konvexní, | ||
| + | můžeme podle Jensenovy nerovnosti \ref{lem:jensenova-nerovnost} provést | ||
| + | odhad\[ | ||
| + | \frac{n}{1+\frac{1}{n}\sum\limits _{i=1}^{n}x_{i}}\leq\sum_{i=1}^{n}\frac{1}{1+x_{i}}.\] | ||
| + | Pokud jej použijeme na vztah (\ref{eq:odhad-alfa-G}), dostaneme\[ | ||
| + | \alpha(G)\geq\sum_{v\in V}\frac{1}{1+d_{G}(v)}\geq\frac{n}{1+\frac{1}{n}\sum\limits _{v\in V}d_{G}(v)}=\frac{n}{1+\rho(G)}.\] | ||
| + | |||
| + | \end{proof} | ||
| + | Pomocí věty \ref{thm:odhad-omega-G} můžeme provést i alternativní | ||
| + | důkaz Turánovy věty \ref{thm:turan}, která říká: Pokud $G=(V,E)$ | ||
| + | neobsahuje kliku $K_{p}$, tak $\# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right)$ | ||
| + | . | ||
| + | |||
| + | Vyjdeme ze Schwarzovy nerovnosti na prostoru $\R^{n}$ se standardním | ||
| + | skalárním součinem. Pro $\vec{x},\vec{y}\in\R^{n}$ platí\[ | ||
| + | \left|\left(\vec{x},\vec{y}\right)\right|^{2}\leq\left\Vert \vec{x}\right\Vert ^{2}\left\Vert \vec{y}\right\Vert ^{2}.\] | ||
| + | Nechť $G=(V,E)$, $V=\hat{n}$. Označme $d_{i}=d_{G}(i)$ pro každé | ||
| + | $i\in V$ a zvolme konkrétně\begin{eqnarray*} | ||
| + | \vec{x} & = & \left(\frac{1}{\sqrt{n-d_{1}}},\frac{1}{\sqrt{n-d_{2}}},...,\frac{1}{\sqrt{n-d_{n}}}\right),\\ | ||
| + | \vec{y} & = & \left(\sqrt{n-d_{1}},\sqrt{n-d_{2}},...,\sqrt{n-d_{n}}\right).\end{eqnarray*} | ||
| + | Potom má Schwarzova nerovnost tvar\begin{equation} | ||
| + | n^{2}=\underbrace{\left(\sum_{i=1}^{n}\frac{1}{\sqrt{n-d_{i}}}\sqrt{n-d_{i}}\right)}_{\left|\left(\vec{x},\vec{y}\right)\right|^{2}}\leq\underbrace{\sum_{i=1}^{n}\frac{1}{n-d_{i}}}_{\left\Vert \vec{x}\right\Vert ^{2}}\underbrace{\sum_{j=1}^{n}(n-d_{j})}_{\left\Vert \vec{y}\right\Vert ^{2}}.\label{eq:schwarz-turan}\end{equation} | ||
| + | Protože podle předpokladu $G$ neobsahuje $K_{p}$, platí podle věty | ||
| + | \ref{thm:odhad-omega-G}\[ | ||
| + | \sum_{i=1}^{n}\frac{1}{n-d_{i}}\leq\omega(G)\leq p-1.\] | ||
| + | Po dosazení do \ref{eq:schwarz-turan} dostáváme\begin{eqnarray*} | ||
| + | n^{2} & \leq & (p-1)\left(n^{2}-2\# E\right)\\ | ||
| + | 2(p-1)\# E & \leq & (p-2)n^{2}\\ | ||
| + | \# E & \leq & \frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right).\end{eqnarray*} | ||
| + | |||
| + | |||
| + | \begin{thm} | ||
| + | \label{thm:posloupnost-nahod-grafu}Nechť $G_{n}$ označuje náhodný | ||
| + | graf na $n$ vrcholech% | ||
| + | \footnote{$G_{n}$ vznikne tak, že každé dva vrcholy spojíme hranou s pravděpodobností | ||
| + | $\frac{1}{2}$. ,,Náhodná veličina{}`` $G_{n}$ má potom rovnoměrné | ||
| + | rozdělení.% | ||
| + | }. Potom existuje posloupnost $\left(k_{n}\right)_{n\in\N}$ taková, | ||
| + | že\begin{equation} | ||
| + | \lim_{n\to\infty}\Pr\left(\left(\omega(G_{n})=k_{n}\right)\vee\left(\omega(G_{n})=k_{n}+1\right)\right)=1\label{eq:posloupnost_kn}\end{equation} | ||
| + | |||
| + | \end{thm} | ||
| + | \begin{rem*} | ||
| + | ~ | ||
| + | \begin{itemize} | ||
| + | \item Pro posloupnost $\left(k_{n}\right)_{n\in\N}$ platí řádově\[ | ||
| + | \lim_{n\to\infty}\frac{k_{n}}{2\log_{2}n}=1.\] | ||
| + | |||
| + | \item Je-li $G_{n}$ náhodný graf, potom $\bar{G}_{n}$ je také náhodný | ||
| + | graf, a přitom $\omega(\bar{G}_{n})=\alpha(G_{n})$. Proto je (\ref{eq:posloupnost_kn}) | ||
| + | ekvivalentní s\[ | ||
| + | \lim_{n\to\infty}\Pr\left(\left(\alpha(G_{n})=k_{n}\right)\vee\left(\alpha(G_{n})=k_{n}+1\right)\right)=1.\] | ||
| + | |||
| + | \end{itemize} | ||
| + | \end{rem*} | ||
Aktuální verze z 15. 1. 2012, 14:16
| [ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
| PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
| ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01ZTGA
| součást | akce | popis | poslední editace | soubor | |||
|---|---|---|---|---|---|---|---|
| Hlavní dokument | editovat | Hlavní stránka dokumentu 01ZTGA | Karel.brinda | 15. 1. 2012 | 23:45 | ||
| Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 13:51 | ||
| Header | editovat | Hlavičkový soubor | Karel.brinda | 15. 1. 2012 | 12:34 | header.tex | |
| Kapitola0 | editovat | Úvod | Karel.brinda | 15. 1. 2012 | 12:36 | cast0.tex | |
| Kapitola1_1 | editovat | Základní pojmy | Karel.brinda | 15. 1. 2012 | 12:46 | cast1_kapitola1.tex | |
| Kapitola1_2 | editovat | Souvislost | Karel.brinda | 15. 1. 2012 | 12:49 | cast1_kapitola2.tex | |
| Kapitola1_3 | editovat | Bipartitní grafy | Karel.brinda | 15. 1. 2012 | 12:50 | cast1_kapitola3.tex | |
| Kapitola1_4 | editovat | Stromy | Kubuondr | 5. 1. 2019 | 09:06 | cast1_kapitola4.tex | |
| Kapitola1_5 | editovat | Hledání minimální kostry grafu | Karel.brinda | 15. 1. 2012 | 12:51 | cast1_kapitola5.tex | |
| Kapitola1_6 | editovat | Jednotažky | Karel.brinda | 15. 1. 2012 | 12:53 | cast1_kapitola6.tex | |
| Kapitola1_7 | editovat | Hamiltonovské kružnice a grafy | Karel.brinda | 15. 1. 2012 | 13:34 | cast1_kapitola7.tex | |
| Kapitola1_8 | editovat | Párování v grafech | Karel.brinda | 15. 1. 2012 | 13:40 | cast1_kapitola8.tex | |
| Kapitola1_9 | editovat | Toky v sítích | Karel.brinda | 15. 1. 2012 | 13:44 | cast1_kapitola9.tex | |
| Kapitola1_10 | editovat | Hranové obarvení grafu | Karel.brinda | 15. 1. 2012 | 13:48 | cast1_kapitola10.tex | |
| Kapitola1_11 | editovat | Vrcholové obarvení grafu | Karel.brinda | 15. 1. 2012 | 13:52 | cast1_kapitola11.tex | |
| Kapitola1_12 | editovat | Planární grafy | Karel.brinda | 15. 1. 2012 | 13:56 | cast1_kapitola12.tex | |
| Kapitola1_13 | editovat | Vlastní čísla adjacenční matice grafu | Karel.brinda | 15. 1. 2012 | 13:57 | cast1_kapitola13.tex | |
| Kapitola2_1 | editovat | Brouwerova věta o pevném bodě | Karel.brinda | 15. 1. 2012 | 14:11 | cast2_kapitola1.tex | |
| Kapitola2_2 | editovat | Pravděpodobnostní důkazy v teorii grafů | Karel.brinda | 15. 1. 2012 | 14:12 | cast2_kapitola2.tex | |
| Kapitola2_3 | editovat | Extremální teorie grafů | Karel.brinda | 15. 1. 2012 | 14:16 | cast2_kapitola3.tex | |
| Kapitola2_4 | editovat | Ramseyovská čísla | Karel.brinda | 15. 1. 2012 | 14:18 | cast2_kapitola4.tex | |
| Kapitola3_1 | editovat | Obyčejné mocninné řady | Karel.brinda | 15. 1. 2012 | 14:22 | cast3_kapitola1.tex | |
| Kapitola3_2 | editovat | Exponenciální generující funkce | Karel.brinda | 15. 1. 2012 | 14:22 | cast3_kapitola2.tex | |
Zdrojový kód
%\wikiskriptum{01ZTGA} \section{Extremální teorie grafů} Věty z extremální teorie grafů vyjadřují vztahy typu \begin{itemize} \item ,,jistý počet něčeho už vynucuje něco{}`` nebo \item ,,kolik něčeho může být, aby platilo něco{}`` \end{itemize} \subsection{Turánova věta} \begin{thm} \textbf{\emph{\label{thm:turan}(Turán, 1943)}} Nechť $G=(V,E)$ je graf, který neobsahuje kliku velikosti $p$ (viz. definice \ref{def:klika-nez-mnozina}) , tj. $K_{p}$ není podgrafem $G$. Potom\begin{equation} \# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right).\label{eq:turan}\end{equation} \end{thm} Důkazů Turánovy věty existuje řada, my postupně provedeme důkaz založený na následujícím lemmatu: \begin{lem} Nechť $G$ je graf (na pevném počtu vrcholů) neobsahující $K_{p}$ s maximálním počtem hran. Potom v $G$ neexistuje trojice vrcholů $u,v,w$ takových, že $\{ v,w\}\in E$ a přitom $\{ u,v\}\notin E,\{ u,w\}\notin E$. \hfill{} \begin{center} %Title: turan_lemma.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 18:00:48 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.003 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 20.003 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 8.096 20.003 to 10.478 20.003 }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}w}% } [lB] at 10.835 19.884 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}v}% } [lB] at 7.499 19.884 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}% } [lB] at 9.167 20.360 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.286 20.955 }% \linethickness=0pt \putrectangle corners at 7.468 21.088 and 10.867 19.852 \endpicture} \end{center} \hfill{}~ \end{lem} \begin{proof} Nejprve proveďme pomocnou úvahu: Buď $G=(V,E)$ bez $K_{p}$, nechť $x\in V$. Sestrojme graf \[ G'=\left(V\cup\{ x'\},E\cup\left\{ \left.\{ v,x'\}\right|v\in V\wedge\{ v,x\}\in E\right\} \right),\] pro nějž $\forall v\in V$ platí $\{ x,v\}\in E(G')\Leftrightarrow\{ x',v\}\in E(G')$. Vrcholy $x$ a $x'$ jsou tedy v $G'$ zcela rovnocenné. Protože $\{ x,x'\}\notin E(G')$, tak $G'$ \underbar{nemůže obsahovat} $K_{p}$. V $K_{p}$ by totiž musel být buď jen vrchol $x$, nebo jen vrchol $x'$, což je spor, protože v tom případě by musela klika $K_{p}$ existovat už v $G$. Nyní postupujme sporem. Nechť v $G$ existuje trojice vrcholů $u,v,w$ daných vlastností. Potom mohou nastat dvě možnosti: \begin{enumerate} \item $d_{G}(u)<d_{G}(v)$ nebo $d_{G}(u)<d_{G}(w)$ (nechť BÚNO $d_{G}(u)<d_{G}(v)$). V tomto případě ke grafu $G$ přidáme právě popsaným způsobem vrchol $v'$ a ubereme vrchol $u$ (i se všemi hranami, které do něj vedly). Nově vytvořený graf neobsahuje $K_{p}$, ale přitom má o\[ d_{G}(v')-d_{G}(u)=d_{G}(v)-d_{G}(u)>0\] hran více než $G$, což je spor s maximálním počtem hran grafu $G$. \item $d_{G}(u)\geq d_{G}(v)$ a $d_{G}(u)\geq d_{G}(w)$. V tomto případě ke $G$ přidáme kopie $u',u''$ a ubereme vrcholy $v,w$. Nový graf opět neobsahuje $K_{p}$ a má o\[ 2d_{G}(u)-d_{G}(v)-d_{G}(w)+1>0\] hran více než $G$, což je spor. Jedničku přičítáme proto, že $\{ v,w\}\in E$, a odečtením stupňů vrcholů $v,w$ jsme tuto hranu odečetli od celkového počtu hran dvakrát. \end{enumerate} \end{proof} \begin{cor*} Relace $\oslash$ na množině vrcholů $V$ grafu $G$ s vlastnostmi z minulého lemmatu definovaná jako\[ \left(u\oslash v\right)\Leftrightarrow\{ u,v\}\notin E\] je ekvivalence na $V$. \end{cor*} \begin{proof} Symetrie a reflexivita relace $\oslash$ jsou zřejmé. Tranzitivitu pak vyjadřuje předchozí lemma:\[ \{ v,u\}\notin E\wedge\{ u,w\}\notin E\Rightarrow\{ v,w\}\notin E.\] \end{proof} Nyní přikročíme přímo k důkazu tvrzení Turánovy věty. \begin{proof} Mějme tedy $G=(V,E)$ bez $K_{p}$, s maximálním počtem hran. Bude-li platit (\ref{eq:turan}) pro tento $G$, bude platit i pro libovolný jiný graf bez $K_{p}$ (s nejvýše stejným počtem hran). $V$ je rozdělena na třídy ekvivalence podle relace $\oslash$\[ V=V_{1}\cup V_{2}\cup...\cup V_{s},\] přičemž z definice $\oslash$ platí: \begin{itemize} \item \begin{equation} \left(\forall i\in\hat{s}\right)\left(\forall u,v\in V_{i}\right)\left(\{ u,v\}\notin E\right),\label{eq:turan-podm1}\end{equation} \item \begin{equation} \left(\forall i,j\in\hat{s},i\neq j\right)\left(\forall u\in V_{i}\right)\left(\forall v\in V_{j}\right)\left(\{ u,v\}\in E\right).\label{eq:turan-podm2}\end{equation} \end{itemize} Mezi každými dvěma vrcholy z různých tříd tedy vedou hrany, ale v jedné třídě není hrana mezi žádnými dvěma vrcholy. Počet tříd je $s=p-1$. Kdyby jich totiž bylo alespoň $p$, bylo by možné vybrat z každé z nich jeden vrchol, a vybraná podmnožina $V$ by tvořila kliku velikosti $s\geq p$, takže by v $G$ existovala i $K_{p}\subset K_{s}\subset G$. Kdyby jich naopak bylo méně než $p-1$, potom bychom mohli jednu třídu ekvivalence rozbít na dvě (přidat hrany mezi odpovídajícími množinami vrcholů), a stále by graf neobsahoval $K_{p}$ (je jasné, že různé vrcholy z $K_{p}$ musí ležet v různých třídách $V_{i}$). To by ale byl spor s maximalitou počtu hran v $G$. $V$ se tedy skládá z $p-1$ podmnožin $V_{1},...,V_{p-1}$ s vlastnostmi (\ref{eq:turan-podm1}) a (\ref{eq:turan-podm2}). Označme si $k_{i}=\# V_{i}$ pro každé $i\in\widehat{p-1}$. Potom\[ n=\sum_{i=1}^{p-1}k_{i}.\] Počet hran mezi $V_{i}$ a $V_{j}$ pro $i\neq j$ je zřejmě $k_{i}k_{j}$, takže počet hran v celém grafu je\begin{equation} \sum_{1\leq i<j\leq p-1}k_{i}k_{j}\label{eq:turan-pocet-hran}\end{equation} a přitom v $G$ je počet hran maximální mezi všemi grafy na $n=\# V$ vrcholech, které neobsahují $K_{p}$. Je tedy maximální i mezi takovými z nich, které mají stejný ,,tvar{}`` jako $G$: jejich množina vrcholů je nějak rozdělena na $p-1$ neprázdných disjunktních podmnožin, které splňují (\ref{eq:turan-podm1}) a (\ref{eq:turan-podm2}). Přitom každý graf, který splňuje tyto podmínky, neobsahuje $K_{p}$. Každý z těchto grafů je navíc jednoznačně (až na izomorfismus) určen $(p-1)$-ticí $(k_{1},...,k_{p-1})$. Počet hran v $G$ je potom možno vyjádřit jako\[ \max\left(\sum_{1\leq i<j\leq p-1}k_{i}k_{j}\right)\] za podmínky\[ n=\sum_{i=1}^{p-1}k_{i}\,,\; k_{i}\in\N_{0}.\] Maxima počtu hran se však nabyde právě tehdy, když počet ,,nehran{}`` (dvojic vrcholů, mezi nimiž nevede hrana) bude minimální. Ekvivalentně tak lze hledat\[ \min\left(\sum_{i=1}^{p-1}\binom{k_{i}}{2}\right)\] za stejných podmínek, což bude jednodušší. Protože chceme pouze shora odhadnout skutečný počet hran v $G$, vyřešíme úlohu minima bez podmínky na celočíselnost proměnných $k_{i}$. Hledáme tedy vázaný extrém funkce\[ f(x_{1},...,x_{p-1})=\sum_{i=1}^{p-1}\binom{x_{i}}{2}=\sum_{i=1}^{p-1}\frac{1}{2}x_{i}(x_{i}-1)\] za podmínky\[ \sum_{i=1}^{p-1}x_{i}=n.\] Sestavíme Lagrangeovu funkci\[ \Lambda(x_{1},...,x_{p-1})=f(x_{1},...,x_{p-1})-\lambda\left(\sum_{i=1}^{p-1}x_{i}-n\right)\] a po zderivování a položení $\left(\forall i\in\widehat{p-1}\right)\left(\partial_{i}\Lambda=0\right)$ dostaneme\[ 0=\frac{\partial\Lambda}{\partial x_{i}}=x_{i}-\frac{1}{2}-\lambda\;\Rightarrow x_{i}=\lambda+\frac{1}{2}.\] Pokud dosadíme do podmínky vazby, vyjde $\lambda=\frac{n}{p-1}-\frac{1}{2}$, takže pro všechna $x_{i}$ platí \[ x_{i}=\frac{n}{p-1}.\] Lze snadno ověřit, že se skutečně jedná o minimum, výpočtem (tzv. Hessovy) matice $\vec{H}=\left(\frac{\partial^{2}\Lambda}{\partial x_{i}\partial x_{j}}\right)$. Platí $\vec{H}=\vec{I}$, což je zřejmě pozitivně definitní matice. Dosadíme-li nyní za $x_{i}$ do $\sum_{1\leq i<j\leq p-1}x_{i}x_{j}$, získáme horní odhad skutečného počtu hran (\ref{eq:turan-pocet-hran}). Všechny sčítance v sumě jsou stejné a jejich počet je $\binom{p-1}{2}$, takže horní odhad počtu hran vychází jako\[ \left(\frac{n}{p-1}\right)^{2}\binom{p-1}{2}=\frac{n^{2}}{(p-1)^{2}}\frac{(p-1)(p-2)}{2}=\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right),\] což je přesně (\ref{eq:turan}). \end{proof} \begin{rem*} Důkaz Turánovy věty také ukazuje, jak graf s co největším počtem hran, a přitom bez $K_{p}$, zkonstruovat. Například graf neobsahující $K_{3}$ s maximálním počtem hran bude úplný bipartitní s množinou vrcholů $V$ rozdělenou na podmnožiny s počty vrcholů $\left[\frac{n+1}{2}\right]$ a $\left[\frac{n}{2}\right]$. \end{rem*} V následujícím ukážeme jednu z aplikací Turánovy věty. \begin{defn*} Nechť $S=\{ x_{1},...,x_{n}\}\subset\R^{2}$ je množina bodů v rovině. \textbf{Průměrem} (diametrem) množiny $S$ rozumíme číslo\[ \mathrm{diam}\, S=\max_{i,j\in\hat{n}}\left\Vert x_{i}-x_{j}\right\Vert .\] \end{defn*} \begin{rem*} Nechť $S=\{ x_{1},...,x_{n}\}\subset\R^{2}$, $\mathrm{diam}\, S\leq1$, $d\in(0,1)$. Otázkou je, kolik párů bodů $x_{i},x_{j}$ má vzdálenost $\geq d$, a jestli tento počet lze jiným uspořádáním bodů $x_{1},...,x_{n}$ zvýšit. Jako příklad si vezměme $n=6,d=\frac{\sqrt{3}}{2}-\varepsilon$, $\varepsilon>0$. Potom existuje $\binom{6}{2}=15$ různých párů. Na obrázku \ref{cap:vzdalene-pary} jsou páry od sebe vzdálených bodů spojeny čarami. Vlevo má $9$ párů vzdálenost $\geq d$ a $6$ párů vzdálenost $<d$, vpravo má $12$ párů vzdálenost $\geq d$ a jen $3$ páry vzdálenost $<d$. Obecně omezuje počet vzdálených párů následující věta. % \begin{figure} \begin{center} %Title: diameter1.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:47:04 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 15.001 20.479 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 16.311 17.264 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 16.669 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 14.525 20.479 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 13.216 17.264 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.857 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.857 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.191 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.191 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 16.669 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.905:1.905 360 degrees from 11.430 18.574 center at 9.525 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 20.479 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{1,0,0}\putrule from 13.214 17.266 to 16.311 17.266 \plot 16.311 17.266 15.001 20.479 / \plot 15.001 20.479 12.859 17.621 / \putrule from 12.859 17.621 to 16.669 17.621 \plot 16.669 17.621 14.525 20.479 / \plot 14.525 20.479 13.214 17.266 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{1,0,0}\plot 14.525 20.479 12.859 17.621 / \plot 12.859 17.621 16.311 17.266 / \plot 16.311 17.266 14.525 20.479 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{1,0,0}\plot 15.001 20.479 13.214 17.266 / \plot 13.214 17.266 16.669 17.621 / \plot 16.669 17.621 15.001 20.479 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{1,0,0}\putrule from 9.525 20.479 to 9.525 16.669 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{1,0,0}\plot 7.857 17.621 11.191 19.526 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{1,0,0}\putrule from 7.857 19.526 to 11.191 19.526 \plot 11.191 19.526 9.525 16.669 / \plot 9.525 16.669 7.857 19.526 / \plot 7.857 19.526 11.191 17.621 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{1,0,0}\putrule from 7.857 17.621 to 11.191 17.621 \plot 11.191 17.621 9.525 20.479 / \plot 9.525 20.479 7.857 17.621 / }% \linethickness=0pt \putrectangle corners at 7.603 20.612 and 16.804 16.535 \endpicture} \end{center} \caption{\label{cap:vzdalene-pary}Páry vzdálených bodů v rovině} \end{figure} \end{rem*} \begin{thm} \label{thm:vzdalene-pary}Nechť $d\in\left(\frac{1}{\sqrt{2}},1\right)$. Potom počet párů z $n$-prvkové množiny $S\subset\R^{2}$ s průměrem $\mathrm{diam}\, S\leq1$, které mají vzdálenost alespoň $d$, je nejvýše $\left[\frac{n^{2}}{3}\right]$. Přitom tohoto počtu lze vhodným uspořádáním bodů vždy dosáhnout. \end{thm} Než dokážeme tuto větu, která je snadným důsledkem Turánovy věty, připravíme si ješte malé lemma. \begin{lem} Z libovolných čtyř bodů v rovině lze vybrat tři tak, že tvoří pravoúhlý nebo tupoúhlý trojúhelník (přitom přímku považujeme za tupoúhlý trojúhelník s úhlem $180^{\circ}$). \end{lem} \begin{proof} Mohou nastat dva případy: \begin{enumerate} \item Jeden bod $x$ leží v konvexním obalu zbylých tří bodů $y_{1},y_{2},y_{3}$. Potom součet vrcholových úhlů $\measuredangle y_{1}xy_{2}$,$\measuredangle y_{2}xy_{3}$,$\measuredangle y_{3}xy_{1}$ je $360^{\circ}$, takže jeden z nich musí být dokonce $\geq120^{\circ}$. \item Všechny čtyři body tvoří konvexní čtyřúhelník. Protože v něm je součet úhlů $360^{\circ}$, musí tam existovat jeden $\geq90^{\circ}$. \end{enumerate} \end{proof} \begin{proof} (věty \ref{thm:vzdalene-pary}) Definujme graf $G=(S,E)$, kde $\{ x_{i},x_{j}\}\in E\Leftrightarrow\left\Vert x_{i}-x_{j}\right\Vert \geq d$. Potom $G$ neobsahuje kliku $K_{4}$. Jestliže totiž čtyři body (vrcholy $G$) tvoří $K_{4}$, tak jsou každé dva z nich od sebe dál než $d$. Podle předchozího lemmatu lze vybrat tři, které tvoří tupoúhlý trojúhelník. Obě ,,odvěsny{}`` tohoto trojúhelníka jsou delší než $d\geq\frac{1}{\sqrt{2}}$, a tak je ,,přepona{}`` delší než $1$, což je spor. Podle Turánovy věty pro $p=4$ potom platí\[ \# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right)=\frac{n^{2}}{3}.\] Nyní zbývá dokázat, že této mezi se lze přiblížit. Za tím účelem se podívejme na důkaz Turánovy věty. Počtu hran $\frac{n^{2}}{3}$ se dosahuje, jestliže graf $G$ je rozdělen do $p-1=3$ ,,knedlíků{}``, v nichž nevedou hrany (body z jednoho ,,knedlíku{}`` jsou v rovině blízko sebe) a mezi nimiž naopak vedou všechny hrany (celé ,,knedlíky{}`` jsou v rovině daleko od sebe), a jestliže počet vrcholů v každém ,,knedlíku{}`` je $\frac{n}{p-1}=\frac{n}{3}$. Protože to však nemusí být celé číslo, lze ve skutečnosti dosáhnout počtu hran jen $\left[\frac{n^{2}}{3}\right]$. Dodejme, že popsané uspořádání přesně odpovídá pravé části obrázku \ref{cap:vzdalene-pary}. \end{proof} \subsection{Erdösova věta} \begin{lem*} \textbf{\emph{\label{lem:jensenova-nerovnost}(Jensenova nerovnost)}} Nechť $f:[a,b]\mapsto\R$ je konvexní funkce, tj.\[ \left(\forall x_{1},x_{2}\in[a,b]\right)\left(\forall\lambda\in[0,1]\right)\left(\lambda f(x_{1})+(1-\lambda)f(x_{2})\geq f(\lambda x_{1}+(1-\lambda)x_{2}\right).\] Nechť $\alpha_{i}\in\R_{0}^{+}$ pro každé $i\in\hat{n}$, $\sum_{i=1}^{n}\alpha_{i}=1$ a nechť $x_{i}\in[a,b]$ pro každé $i\in\hat{n}$. Potom\[ \sum_{i=1}^{n}\alpha_{i}f(x_{i})\geq f\left(\sum_{i=1}^{n}\alpha_{i}x_{i}\right).\] \end{lem*} \begin{proof} Snadno se ukáže indukcí podle $n$, byl proveden například v \cite{TIN}. \end{proof} \begin{cor*} Za stejných předpokladů platí i\begin{equation} \frac{1}{n}\sum_{i=1}^{n}f(x_{i})\geq f\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}\right).\label{eq:konvexni-fce}\end{equation} \end{cor*} \begin{proof} Položíme $\alpha_{i}=\frac{1}{n}$ pro každé $i\in\hat{n}$. \end{proof} \begin{thm} \textbf{\emph{(Erdös)}} Nechť $G=(V,E)$ je graf, který neobsahuje jako svůj podgraf $K_{r,r}$ (úplný bipartitní graf na $r+r$ vrcholech). Potom\[ \# E\leq C_{r}\cdot n^{2-\frac{1}{r}},\] kde $C_{r}$ je konstanta nezávislá na $n=\# V$. \end{thm} \begin{rem*} Vždy platí $\# E\leq\binom{n}{2}\leq\frac{n^{2}}{2}$. Turánova věta omezuje počet hran grafu bez $K_{p}$ podle vztahu (\ref{eq:turan}), tj. řádově stejně. Erdösova věta však udává řádově \emph{menší} omezení. \end{rem*} \begin{proof} Nechť $G=(V,E)$, kde BÚNO $V=\hat{n}$, je graf bez $K_{r,r}$. Vytvoříme nový bipartitní graf $G'$, který bude definován na základě grafu $G$ jako $G'=(V_{1}\cup V_{2},E')$, kde $V_{1}=V$ a $V_{2}=\binom{V}{r}$ je množina všech $r$-prvkových podmnožin $V$. Přitom \[ \{\underbrace{i}_{\in V_{1}},\underbrace{\{ k_{1},...,k_{r}\}}_{\in V_{2}}\}\in E',\] právě když $\{ k_{1},...,k_{r}\}\subset N(i)$ v grafu $G$, tj, právě když $\left(\forall j\in\hat{r}\right)\left(\{ i,k_{j}\}\in E\right)$. Základem odvození požadované nerovnosti bude vyjádření počtu hran v grafu $G'$ dvěma různými způsoby, a to jednak jako počet hran vycházejících z $V_{1}$, a jednak jako \emph{odhad} počtu hran vycházejících z $V_{2}$: \begin{enumerate} \item Z definice $E'$ plyne, že z $i\in V_{1}$ vede v $G'$ tolik hran, kolik je $r$-prvkových podmnožin množiny sousedů vrcholu $i$:\[ d_{G'}(i)=\binom{d_{G}(i)}{r}.\] Přitom pokud $d_{G}(i)=\# N_{G}(i)<r$, pak $d_{G'}(i)=0$, což je v souladu s definicí kombinačního čísla. Počet všech hran v $G'$ je tedy\[ \sum_{i=1}^{n}\binom{d_{G}(i)}{r}.\] \item Platí $d_{G'}(\{ k_{1},...,k_{r}\})\leq r-1$. V opačném případě by totiž z definice $E'$ existovalo (alespoň) $r$ vrcholů $l_{1},...,l_{r}$ v grafu $G$ různých od $k_{1},...,k_{r}$, které by byly napojeny na všechny vrcholy $k_{1},...,k_{r}$. To by ale znamenalo, že $G$ obsahuje $K_{r,r}$. Různost vrcholů, tj. skutečnost, že\[ \left(\forall j\in\hat{r}\right)\left(l_{j}\notin\{ k_{1},...,k_{r}\}\right)\] plyne z toho, že žádný vrchol v $G$ není v hraně sám se sebou. Proto žádný $k_{j}\in V_{1}$ nemůže být v grafu $G'$ spojen hranou s vrcholem $\{ k_{1},...,k_{r}\}\in V_{2}$. Z uvedené úvahy plyne, že počet hran v $G'$ musí být menší nebo roven než\[ (r-1)\underbrace{\binom{n}{r}}_{\# V_{2}}.\] \end{enumerate} Srovnáním obou vyjádření dostáváme nerovnost\begin{equation} \sum_{i=1}^{n}\binom{d_{G}(i)}{r}\leq(r-1)\binom{n}{r},\label{eq:erdos-nerovnost1}\end{equation} kterou již budeme jen dále odhadovat a upravovat do požadovaného tvaru. Pokud \[ \frac{1}{n}\underbrace{\sum_{i=1}^{n}d_{G}(i)}_{2\# E}\leq r-1,\] tak potom \[ \# E\leq\frac{1}{2}(r-1)n\leq\underbrace{(r-1)}_{C_{r}}n^{2-\frac{1}{r}}\] a není co dokazovat. Předpokládejme proto \begin{equation} \frac{1}{n}\sum_{i=1}^{n}d_{G}(i)\geq r.\label{eq:erdos-predp}\end{equation} Definujme konvexní funkci\[ f(x)=\begin{cases} \binom{x}{r} & x\geq r\\ 0 & x<r\end{cases},\] kde dodefinování nulou je potřebné jen pro $x$ neceločíselné. Potom $f\left(d_{G}(i)\right)=\binom{d_{G}(i)}{r}$ a podle (\ref{eq:konvexni-fce}) platí\[ n\cdot\binom{\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)}{r}=n\cdot f\left(\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)\right)\leq\sum_{i=1}^{n}f(d_{G}(i))=\sum_{i=1}^{n}\binom{d_{G}(i)}{r},\] přičemž levá strana je nenulová, takže ji lze použít k dalším odhadům (proto je důležitý předpoklad \ref{eq:erdos-predp}). Použijeme-li tento odhad v (\ref{eq:erdos-nerovnost1}), dostaneme\[ n\cdot\binom{\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)}{r}\leq(r-1)\binom{n}{r},\] neboli při označení $m=\# E$\begin{equation} n\cdot\binom{2m/n}{r}\leq(r-1)\binom{n}{r}.\label{eq:erdos-nerovnost2}\end{equation} Kombinační číslo $\binom{n}{k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$ lze odhadnout zdola a shora\[ \frac{(n-k+1)^{k}}{k!}\leq\binom{n}{k}\leq\frac{n^{k}}{k!},\] což pro náš případ znamená\[ n\frac{\left(\frac{2m}{n}-r+1\right)^{r}}{r!}\leq n\binom{2m/n}{r}\leq(r-1)\binom{n}{r}\leq(r-1)\frac{n^{r}}{r!}.\] Vynásobíme $\frac{r!}{n}$ a odmocníme $\sqrt[r]{...}$, takže dostaneme\[ \frac{2m}{n}-r+1\leq\sqrt[r]{r-1}n^{1-\frac{1}{r}}\] a už jen upravujeme:\[ m\leq\frac{n}{2}\left(\sqrt[r]{r-1}n^{1-\frac{1}{r}}+r-1\right)=\frac{1}{2}\sqrt[r]{r-1}n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n\leq\frac{1}{2}\sqrt[r]{r-1}n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n^{2-\frac{1}{r}}\leq\] \[ \leq\frac{1}{2}(r-1)n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n^{2-\frac{1}{r}}\leq\underbrace{(r-1)}_{C_{r}}n^{2-\frac{1}{r}}\] \end{proof} \begin{rem*} Pro $r=2$, tj. pro graf bez $K_{2,2}=C_{4}$ máme odhad\[ \# E\leq C_{r}\cdot n^{3/2}.\] Nerovnost (\ref{eq:erdos-nerovnost2}) lze však v tomto případě upravovat šikovněji, a tak získat (trochu) přísnější odhad:\begin{eqnarray*} n\frac{\frac{1}{n}2m\left(\frac{1}{n}2m-1\right)}{2} & \leq & \frac{n(n-1)}{2}\\ 2m(2m-n) & \leq & n^{3}-n^{2}\\ 4m^{2}-2nm-n^{3}+n^{2} & \leq & 0\end{eqnarray*} Kvadratickou rovnici pro počet hran $m$ vyřešíme:\[ m_{1,2}=\frac{2n\pm\sqrt{4n^{2}-16(-n^{3}+n^{2})}}{8}=\frac{n\pm n\sqrt{4n-3}}{4}.\] Jeden kořen je záporný, takže nehraje roli. Dostáváme tedy odhad\begin{equation} \# E\leq\frac{n+n\sqrt{4n-3}}{4}=\frac{1}{4}n\left(1+\sqrt{4n-3}\right).\label{eq:odhad-E-bez-K22}\end{equation} V následujícím ukážeme, jak se mu lze vhodnou konstrukcí grafu přiblížit. \end{rem*} \subsection{Graf s $\# E$ blízkým Erdösovu odhadu} Zkonstruujeme graf $G=(V,E)$ neobsahující $K_{2,2}=C_{4}$ s počtem hran blížícím se odhadu (\ref{eq:odhad-E-bez-K22}). V následujícím velmi pěkném postupu se využije mnoho znalostí z různých partií matematiky. Nechť $p$ je prvočíslo. Uvažujme těleso zbytkových tříd $\Z_{p}=\{0,1,2,...,p-1\}$ a vektorový prostor $\Z_{p}^{3}$ nad tělesem $\Z_{p}$. Vrcholy grafu $G$ budou představovat přímky v $\Z_{p}^{3}$ procházející počátkem. V tomto prostoru má každá taková přímka právě $p$ bodů, protože ji lze vyjádřit jako lineární obal jejího směrového vektoru, který je z definice roven\[ [\underbrace{(x_{1},x_{2},x_{3})}_{\vec{x}}]_{\lambda}=\left\{ \left.(kx_{1},kx_{2},kx_{3})\right|k\in\Z_{p}\right\} .\] Různých nenulových vektorů v $\Z_{p}^{3}$ je zřejmě $p^{3}-1$. Protože každá přímka má $p$ bodů, z nichž $p-1$ jsou nenulové vektory, je možné ji reprezentovat libovolným z $p-1$ směrových vektorů. Proto počet všech přímek procházejících počátkem je roven\[ \# V=\frac{p^{3}-1}{p-1}=p^{2}+p+1.\] Označme si (vybrané) směrové vektory přímek ( = vrcholů grafu $G$) $v_{1},v_{2},...,v_{p^{2}+p+1}$ po řadě jako $\vec{x}_{1},...,\vec{x}_{p^{2}+p+1}$, tj. nechť platí\[ \left(\forall i\in\{1,...,p^{2}+p+1\}\right)\left(v_{i}=[\vec{x}_{i}]_{\lambda}\right).\] Dále definujme ,,pseudoskalární{}`` součin vektorů $\vec{x}=(x_{1},x_{2},x_{3})$ a $\vec{y}=(y_{1},y_{2},y_{3})$ z prostoru $\Z_{p}^{3}$ jako\[ \left\langle \vec{x},\vec{y}\right\rangle =x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}.\] Řekneme, že vektor $\vec{x}$ je kolmý na vektor $\vec{y}$, jestliže $\left\langle \vec{x},\vec{y}\right\rangle =0$. Protože existují vektory, které jsou kolmé samy na sebe, nejedná se o pravý skalární součin. Nyní množinu hran $E$ definujeme jako\[ E=\left\{ \left.\{ v_{i},v_{j}\}\right|i\neq j\wedge\left\langle \vec{x}_{i},\vec{x}_{j}\right\rangle =0\right\} .\] \begin{example*} Abychom si dobře uvědomili, jak je graf $G$ definován, ukážeme si jej pro $p=2$. Na obrázku \ref{cap:konstrukce-Z2} jsou jednotlivé vrcholy grafu označeny svými směrovými vektory. Je vidět, že například vektor $(1,1,0)$ je kolmý sám na sebe.% \begin{figure} \begin{center} %Title: konstrukce_Z2.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:35:44 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 20.955 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.715 20.003 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.715 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 20.955 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 19.526 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 8.572 19.526 to 8.572 20.973 \putrule from 8.572 20.955 to 12.876 20.955 \putrule from 12.859 20.955 to 12.859 17.621 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 8.572 20.955 10.715 20.003 / \putrule from 10.715 20.003 to 10.715 18.574 \plot 10.715 18.574 12.859 17.621 / \putrule from 12.859 17.621 to 8.555 17.621 \putrule from 8.572 17.621 to 8.572 19.526 \plot 8.572 19.526 10.715 20.003 / }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,1,1)$}% } [lB] at 13.214 17.503 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,0,1)$}% } [lB] at 9.167 18.455 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,0,1)$}% } [lB] at 7.023 19.408 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,1,0)$}% } [lB] at 11.070 19.884 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,1,1)$}% } [lB] at 13.214 20.836 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,0,0)$}% } [lB] at 7.023 20.836 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,1,0)$}% } [lB] at 7.023 17.503 \linethickness=0pt \putrectangle corners at 6.991 21.207 and 13.246 17.344 \endpicture} \end{center} \caption{\label{cap:konstrukce-Z2}Konstrukce $G$ pro $p=2$} \end{figure} \end{example*} Ukážeme, že pro libovolné prvočíslo $p$ takto definovaný graf $G$ neobsahuje $K_{2,2}=C_{4}$. Kdyby $G$ obsahoval $C_{4}$, existovaly by v něm vrcholy $v_{i},v_{j}$ spojené hranami s dalšími dvěma vrcholy takto: \hfill{} \begin{center} %Title: konstrukce_kolmost.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:16:56 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.479 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.479 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.955 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 9.049 20.955 7.620 20.479 / \plot 7.620 20.479 9.049 20.003 / \plot 9.049 20.003 10.478 20.479 / \plot 10.478 20.479 9.049 20.955 / }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}% } [lB] at 10.952 20.360 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}% } [lB] at 6.905 20.360 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.003 }% \linethickness=0pt \putrectangle corners at 6.873 21.088 and 10.983 19.869 \endpicture} \end{center} \hfill{}~ \noindent Podívejme se však, kolik vrcholů může být hranami napojeno na $v_{i}$ i na $v_{j}$. Označme $\vec{x}_{i}=(\alpha_{1},\alpha_{2},\alpha_{3})$, $\vec{x}_{j}=(\beta_{1},\beta_{2},\beta_{3})$ a hledejme $\vec{y}=(\gamma_{1},\gamma_{2},\gamma_{3})$ kolmý na $\vec{x}_{i}$ i na $\vec{x}_{j}$. Pro $\vec{y}$ musí platit\begin{eqnarray*} 0=\left\langle \vec{x}_{i},\vec{y}\right\rangle & = & \alpha_{1}\gamma_{1}+\alpha_{2}\gamma_{2}+\alpha_{3}\gamma_{3}\\ 0=\left\langle \vec{x}_{j},\vec{y}\right\rangle & = & \beta_{1}\gamma_{1}+\beta_{2}\gamma_{2}+\beta_{3}\gamma_{3},\end{eqnarray*} což znamená, že $\gamma_{1},\gamma_{2},\gamma_{3}$ jsou řešením homogenní soustavy lineárních rovnic s maticí\[ \left(\begin{array}{ccc} \alpha_{1} & \alpha_{2} & \alpha_{3}\\ \beta_{1} & \beta_{2} & \beta_{3}\end{array}\right).\] Protože $\vec{x}_{i},\vec{x}_{j}$ jsou směrové vektory různých přímek, jsou lineárně nezávislé, a tato matice má tedy hodnost $2$. Podle Frobeniovy věty o řešení soustav lineárních rovnic pak existuje jediné lineárně nezávislé řešení $\vec{y}$ této soustavy. Existuje tedy jediná přímka se směrovým vektorem $\vec{y}$, která je kolmá na obě přímky $v_{i},v_{j}$, neboli tato přímka jako vrchol grafu $G$ je jediná, která je hranami spojena s $v_{i}$ i s $v_{j}$. Proto $G$ neobsahuje $C_{4}$. Nyní postupně vyčíslíme počet hran v grafu $G$. Hledejme stupeň $d_{G}(v_{i})$ nějakého pevného vrcholu $v_{i}\in V$, neboli počet různých přímek, které jsou kolmé na $v_{i}$. Ten je roven počtu \emph{různých} vektorů $\vec{y}$ kolmých na $\vec{x}_{i}$, přičemž dva takové vektory jsou \emph{různé}, když jsou lineárně nezávislé (to ovšem neznamená, že všechny tyto vektory mají tvořit LN soubor). Použijeme-li již zavedené značení pro $\vec{x}_{i}$ a $\vec{y}$, musí $\vec{y}$ splňovat rovnici\[ 0=\left\langle \vec{x}_{i},\vec{y}\right\rangle =\alpha_{1}\gamma_{1}+\alpha_{2}\gamma_{2}+\alpha_{3}\gamma_{3},\] která má $2$ LN řešení $\vec{y}_{1},\vec{y}_{2}$. Počet všech řešení této soustavy je $p^{2}$, protože jsou to právě vektory\[ \vec{y}=k_{1}\vec{y}_{1}+k_{2}\vec{y}_{2}\ ,\; k_{1},k_{2}\in\Z_{p}.\] Máme tedy $p^{2}-1$ nenulových řešení, ale vždy $p-1$ z nich je kolineárních, tj. jedná se o směrové vektory téže přímky. \underbar{Počet různých přímek kolmých na $v_{i}$}, tj. počet \emph{různých} vektorů $\vec{y}$ kolmých na $\vec{x}_{i}$, je tedy\[ \frac{p^{2}-1}{p-1}=p+1.\] Tento výsledek si pro pozdější použití dobře zapamatujme. Nejedná se totiž ještě o $d_{G}(v_{i})$, protože záleží na tom, zda $\vec{x}_{i}$ je kolmý sám na sebe. Zatím tedy můžeme shrnout:\[ \left(\forall i\in\{1,...,p^{2}+p+1\}\right)\left(d_{G}(v_{i})=\begin{cases} p+1 & \left\langle \vec{x}_{i},\vec{x}_{i}\right\rangle \neq0\\ p & \left\langle \vec{x}_{i},\vec{x}_{i}\right\rangle =0\end{cases}\right).\] Dalším naším úkolem je zjistit, v kolika případech je $\vec{x}_{i}$ kolmý sám na sebe. Jestliže to dokážeme, bude už snadné vyjádřit celkový počet hran grafu $G$. Definujme čtvercovou matici $\vec{A}$ řádu $p^{2}+p+1$, jejíž prvky mají hodnotu\[ \vec{A}_{ij}=\begin{cases} 1 & \left\langle \vec{x}_{i},\vec{x}_{j}\right\rangle =0\\ 0 & \textrm{jinak}.\end{cases}\] Potom $\vec{A}_{ii}=1$, právě když $\vec{x}_{i}$ je kolmý sám na sebe. Hledaný počet přímek kolmých na sebe sama je tedy roven počtu nenulových prvků na diagonále matice $\vec{A}$, neboli její stopě $\Tr\vec{A}$. Protože náš pseudoskalární součin je symetrický, je i matice $\vec{A}$ symetrická, a tedy diagonalizovatelná. Podobnostní transformace zachovává stopu, a proto $\Tr\vec{A}$ je rovna součtu vlastních čísel $\vec{A}$. $\vec{A}$ nemá zrovna jednoduchý tvar. Pro určení vlastních čísel proto sestavíme $\vec{A}^{2}$, která vypadá mnohem lépe. Z definice maticového násobení máme\[ \vec{A}_{ij}^{2}=\sum_{k=1}^{p^{2}+p+1}\vec{A}_{ik}\vec{A}_{kj},\] což znamená, že\[ \vec{A}_{ij}^{2}=\#\left\{ \left.k\right|\left\langle \vec{x}_{k},\vec{x}_{i}\right\rangle =0\wedge\left\langle \vec{x}_{k},\vec{x}_{j}\right\rangle =0\right\} ,\] tj. $\vec{A}_{ij}^{2}$ je počet přímek kolmých na $v_{i}$ i $v_{j}$. My už ale víme, že pro $i\neq j$ je taková přímka právě jedna a pro $i=j$ je těchto přímek $p+1$. Proto\[ \vec{A}^{2}=\left(\begin{array}{cccc} p+1 & 1 & \cdots & 1\\ 1 & p+1 & \cdots & 1\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & \cdots & p+1\end{array}\right)=p\vec{I}+\vec{J},\] kde $\vec{J}_{ij}=1$ pro každé $i,j$. Vlastní čísla matice $\vec{A}$ jsou posunuta o $p$ vzhledem k vlastním číslům matice $\vec{J}$:\[ \left(\vec{J}\vec{x}=\lambda\vec{x}\right)\Leftrightarrow\left(\vec{A}^{2}\vec{x}=(p\vec{I}+\vec{J})\vec{x}=(p+\lambda)\vec{x}\right)\] Protože $\vec{J}$ má zřejmě hodnost $1$, má $\vec{J}$ jediné nenulové vlastní číslo $\lambda$ a pak vlastní číslo $0$ s násobností (řád matice$-1$), tj. $p^{2}+p$. Nenulové vlastní číslo $\vec{J}$ je rovno řádu matice, tj. $\lambda=p^{2}+p+1$, protože\[ \vec{J}\left(\begin{array}{c} 1\\ 1\\ \vdots\\ 1\end{array}\right)=\left(\begin{array}{c} p^{2}+p+1\\ p^{2}+p+1\\ \vdots\\ p^{2}+p+1\end{array}\right)=(p^{2}+p+1)\left(\begin{array}{c} 1\\ 1\\ \vdots\\ 1\end{array}\right).\] Matice $\vec{A}^{2}$ má tedy vlastní číslo $(p^{2}+p+1)+p=(p+1)^{2}$ s násobností $1$ a vlastní číslo $0+p=p$ s násobností $p^{2}+p$. Matice $\vec{A}$ má vlastní čísla rovná odmocninám z vlastních čísel $\vec{A}^{2}$, tj. \begin{itemize} \item $p+1$ s násobností $1$ \item $\sqrt{p}$ s násobností $r$ \item $-\sqrt{p}$ s násobností $s$ \end{itemize} \begin{rem*} Vlastní číslo $p+1$ jsme mohli u matice zjistit rovnou podle\[ \vec{A}\left(\begin{array}{c} 1\\ 1\\ \vdots\\ 1\end{array}\right)=\left(\begin{array}{c} p+1\\ p+1\\ \vdots\\ p+1\end{array}\right)=(p+1)\left(\begin{array}{c} 1\\ 1\\ \vdots\\ 1\end{array}\right),\] protože počet jedniček v každém ($i$-tém) řádku $\vec{A}$, což je počet přímek kolmých na $v_{i}$, je roven $p+1$. \end{rem*} Když nyní známe vlastní čísla $\vec{A}$, můžeme konečne vyjádřit\[ \Tr\vec{A}=(p+1)+(r-s)\sqrt{p},\] a protože stopa celočíselné matice nemůže být neceločíselná (přitom $p$ je prvočíslo, takže $\sqrt{p}\notin\N)$, musí nutně $r=s$ a tedy\[ \Tr\vec{A}=p+1.\] Nyní tedy víme, že počet vrcholů $G$ se stupněm $p$ je $p+1$. Ostatních $p^{2}$ vrcholů má stupeň $p+1$. Proto již lze určit počet hran v grafu $G$:\[ 2\# E=\sum_{v\in V}d_{G}(v)=(p+1)p+p^{2}(p+1)=p(p+1)^{2},\] \[ \# E=\frac{p(p+1)^{2}}{2}.\] Abychom mohli $\# E$ srovnat s (\ref{eq:odhad-E-bez-K22}), musíme jej vyjádřit pomocí $n=\# V$. Z rovnosti \begin{equation} n=p^{2}+p+1\label{eq:konstrukce-pocet-vrcholu}\end{equation} tedy získáme\[ p=\frac{-1+\sqrt{4n-3}}{2}\] a po vhodné úpravě, která umožní dosadit za $p^{2}+p$ z (\ref{eq:konstrukce-pocet-vrcholu}), dostaneme\[ \# E=\frac{p(p+1)^{2}}{2}=\frac{p+1}{2}(p^{2}+p)=\frac{1+\sqrt{4n-3}}{4}(n-1)=\frac{1}{4}(n-1)\left(1+\sqrt{4n-3}\right).\] Přitom z Erdösovy věty máme odhad\[ \# E\leq\frac{1}{4}n\left(1+\sqrt{4n-3}\right).\] Je tedy vidět, že pro $n=p^{2}+p+1$, kde $p$ je prvočíslo, je tento odhad docela těsný. \subsection{Počet $K_{3}$ a $\bar{K}_{3}$ v grafu} \begin{thm} Nechť $G=(V,E)$ je graf na $n$ vrcholech. Potom počet klik $K_{3}$ a podgrafů $\bar{K}_{3}$ v grafu $G$ je alespoň \[ \frac{n(n-1)(n-5)}{24}.\] \end{thm} \begin{proof} Tři vrcholy z $n$ vrcholů lze vybrat $\binom{n}{3}$ způsoby. Až na izomorfismus existují pouze $4$ podgrafy (tj. $4$ \emph{typy} podgrafů), které mohou být indukované těmito třemi vrcholy. Jestliže obrázkem podgrafu umístěným do kroužku rozumíme počet podgrafů tohoto typu v grafu $G$, můžeme zapsat následující rovnici: \hfill{} \begin{center} %Title: K3_rovnice1.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:48:56 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 15.953 18.754 center at 15.418 18.754 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.716 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.121 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.420 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 13.811 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 13.513 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 14.110 18.574 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 14.347 18.754 center at 13.811 18.754 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 12.738 18.754 center at 12.203 18.754 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.501 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 11.906 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.205 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.596 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.298 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.894 18.574 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 11.132 18.754 center at 10.596 18.754 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 15.716 18.574 to 15.119 18.574 \plot 15.119 18.574 15.418 19.111 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 13.513 18.574 to 14.108 18.574 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 10.298 18.574 10.596 19.111 / \plot 10.596 19.111 10.892 18.574 / \putrule from 10.892 18.574 to 10.298 18.574 }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\binom{n}{3}}$}% } [lB] at 16.133 18.633 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% } [lB] at 14.465 18.633 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% } [lB] at 11.250 18.633 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% } [lB] at 12.859 18.633 \linethickness=0pt \putrectangle corners at 10.029 19.321 and 16.165 18.186 \endpicture} \end{center} \hfill{}~ \noindent Vezměme nyní vrchol $v\in V$. Z něj vede hrana do $d_{G}(v)$ vrcholů a do dalších $n-1-d_{G}(v)$ z něj hrana nevede. Počet \emph{uspořádaných} trojic $(v,u,w)$ takových, že $\{ v,u\}\in E$ a zároveň $\{ v,w\}\notin E$, je tedy\[ \sum_{v\in V}d_{G}(v)\left(n-1-d_{G}(v)\right).\] Každé trojici vrcholů z $V$, která v grafu $G$ indukuje podgrafy \begin{center} %Title: K3_podgraf3.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:10:40 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.298 26.312 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.597 26.848 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 0.296 26.312 to 0.893 26.312 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.893 26.312 }% \linethickness=0pt \putrectangle corners at 0.222 26.922 and 0.969 26.238 \endpicture} \end{center} nebo \begin{center} %Title: K3_podgraf4.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:10:56 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.298 26.312 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.597 26.848 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 0.891 26.314 to 0.296 26.314 \plot 0.296 26.314 0.595 26.848 / }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.893 26.312 }% \linethickness=0pt \putrectangle corners at 0.222 26.922 and 0.969 26.238 \endpicture}, \end{center} však přísluší právě dva různé výběry vrcholu $v$, tj. právě dvě \emph{uspořádané} trojice $(v,u,w)$ daných vlastností. Proto \noindent \hfill{} \begin{center} %Title: K3_rovnice2.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:29:20 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.561 26.253 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.263 25.718 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.857 25.718 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 3.095 25.897 center at 2.559 25.897 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 1.488 25.897 center at 0.953 25.897 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 1.251 25.718 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.654 25.718 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.953 26.253 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 2.857 25.718 to 2.261 25.718 \plot 2.261 25.718 2.559 26.255 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 0.654 25.718 to 1.249 25.718 }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% } [lB] at 1.607 25.777 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\frac{1}{2}\sum_{v \in V}d_{G}(v)\left(n-1-d_{G}(v)\right).}$}% } [lB] at 3.274 25.777 \linethickness=0pt \putrectangle corners at 0.385 26.513 and 3.306 25.330 \endpicture} \end{center} \hfill{}~ Toto číslo nyní odhadneme shora. Všechny členy sumy, které jsou tvaru $x(n-1-x)$, jsou $\leq\left(\frac{n-1}{2}\right)^{2}$, protože graf funkce $x(n-1-x)=-\left(x-\frac{n-1}{2}\right)^{2}+\left(\frac{n-1}{2}\right)^{2}$ je parabola s maximem $\left(\frac{n-1}{2}\right)^{2}$ v bodě $x=\frac{n-1}{2}$. Tím současně odhadneme zdola počet $K_{3}$ a $\bar{K}_{3}$ v grafu $G$: \hfill{} \begin{center} %Title: K3_rovnice3.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:50:40 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 16.908 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 16.609 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 17.204 18.574 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 17.441 18.754 center at 16.906 18.754 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 15.835 18.754 center at 15.299 18.754 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.598 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.001 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.299 19.109 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 17.204 18.574 to 16.607 18.574 \plot 16.607 18.574 16.906 19.111 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 15.001 18.574 to 15.596 18.574 }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% } [lB] at 15.953 18.633 % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 11.132 18.754 center at 10.596 18.754 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.894 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.298 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.596 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.205 19.109 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 11.906 18.574 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.501 18.574 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees from 12.738 18.754 center at 12.203 18.754 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 10.298 18.574 10.596 19.111 / \plot 10.596 19.111 10.892 18.574 / \putrule from 10.892 18.574 to 10.298 18.574 }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\Bigg)\geq$}% } [lB] at 17.560 18.633 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\binom{n}{3}}-\Bigg($}% } [lB] at 12.918 18.633 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}% } [lB] at 11.250 18.633 \linethickness=0pt \putrectangle corners at 10.029 19.321 and 17.592 18.186 \endpicture} \end{center} \hfill{}~ \noindent \[ \geq\frac{n(n-1)(n-2)}{6}-n\cdot\frac{1}{2}\left(\frac{n-1}{2}\right)^{2}=\frac{n(n-1)\left(4(n-2)-3(n-1)\right)}{24}=\frac{n(n-1)(n-5)}{24}\] \end{proof} \subsection{Odhady $\alpha(G)$ a $\omega(G)$} V této části přednášky se budeme zabývat odhady maximální velikosti kliky a nezávislé množiny v grafu. Zopakujte si proto definici \ref{def:klika-nez-mnozina} z první kapitoly. \begin{obs} Pro libovolný graf $G=(V,E)$, $n=\# V$, platí\[ \alpha(G)\geq\frac{n}{\Delta(G)+1}.\] \end{obs} \begin{proof} Ukážeme konstrukci nezávislé množiny o velikosti alespoň $\frac{n}{\Delta(G)+1}$. \begin{enumerate} \item $S:=\emptyset$, $W:=V$. \item Vezmeme libovolný vrchol $v\in W$ a přesuneme jej z množiny $W$ do množiny $S$. Všechny sousedy $v$ v grafu $G$ odstraníme z $W$. Celkem tedy z $W$ odstraníme nejvýše $\Delta(G)+1$ vrcholů. \item Krok 2 opakujeme, dokud $W\neq\emptyset$. \end{enumerate} Je zřejmé, že po provedení popsaného postupu bude $S$ nezávislá množina, přičemž \[ \# S\geq\frac{n}{\Delta(G)+1}.\] \end{proof} \begin{thm} \label{thm:odhad-alfa-G-pomoci-ro-G}Pro libovolný graf $G=(V,E)$ platí\[ \alpha(G)\geq\frac{n}{\rho(G)+1},\] kde $\rho(G)$ je průměrný stupeň grafu $G$ (viz. definice \ref{def:stupen-vrcholu}). \end{thm} Tuto větu dokážeme za chvíli, neboť snadno vyplyne z věty \ref{thm:odhad-omega-G}. Nejprve ukážeme slabší odhad $\alpha(G)$: \begin{thm} Nechť $G=(V,E)$ s průměrným stupněm $\rho(G)\geq1$. Potom\[ \alpha(G)\geq\frac{n}{2\Delta(G)}.\] \end{thm} \begin{proof} Provedeme pravděpodobnostní důkaz tohoto tvrzení. Nechť $G$ je pevně daný graf a označme jako vždy $n=\# V,m=\# E$. Sestrojme \underbar{indukovaný} podgraf $H\subset G$ tak, že každý $v\in V$ zařadíme do $V(H)$ nezávisle s pravděpodobností $p\in[0,1]$, kde $p$ zatím nespecifikujeme. Označme si náhodné veličiny \begin{lyxlist}{00.00.0000} \item [$X=\# V(H)$,]což je počet vrcholů grafu $H$, a \item [$Y=\# E(H)$,]což je počet hran v grafu $H$. \end{lyxlist} Vypočítáme střední hodnoty těchto veličin obvyklým způsobem. Pro každý $v\in V$ zavedeme elementární náhodnou veličinu\[ X_{v}=\begin{cases} 1 & v\in V(H)\\ 0 & v\notin V(H)\end{cases}.\] Potom\[ X=\sum_{v\in V}X_{v},\] \[ \E X_{v}=1\cdot\Pr(X_{v}=1)+0\cdot\Pr(X_{v}=0)=1\cdot p+0\cdot p=p\] a\[ \E X=\sum_{v\in V}\E X_{v}=np.\] Obdobně vypočítáme střední hodnotu počtu hran. Pro každou hranu $e\in E$, $e=\{ u,v\}$ zavedeme\[ Y_{e}=\begin{cases} 1 & e\in E(H)\\ 0 & e\notin E(H)\end{cases}.\] Potom\[ Y=\sum_{v\in V}Y_{e},\] \[ \E Y_{e}=\Pr(Y_{e}=1)=\Pr(u\in V(H)\wedge v\in V(H))=p^{2}\] a\[ \E Y=\sum_{e\in E}\E Y_{v}=mp^{2}.\] Platí ale \[ \rho(G)=\frac{1}{n}\sum_{v\in V}d_{G}(V)=\frac{2m}{n}\quad\Rightarrow\quad\E Y=p^{2}\frac{\rho(G)\cdot n}{2}.\] Zvolme nyní $p=\frac{1}{\rho(G)}$. Potom\[ \E(X-Y)=np-\frac{\rho(G)np^{2}}{2}=\frac{n}{\rho(G)}-\frac{n}{2\rho(G)}=\frac{n}{2\rho(G)}.\] To znamená, že existuje taková konkrétní realizace indukovaného podgrafu $H$, že\begin{equation} X-Y\geq\frac{n}{2\rho(G)}.\label{eq:rozdil-hran-vrch}\end{equation} Nyní odebereme všechny hrany z tohoto $H$ vždy společně s jedním jejich koncem. Z původní množiny vrcholů $V(H)$ tak vznikne množina vrcholů $S$, která je nezávislou množinou v grafu $G$. $H$ je totiž indukovaný podgraf, takže mezi vrcholy z $S$ již nevedou žádné hrany ani v grafu $G$. Po ubrání $Y$ hran spolu s $Y$ vrcholy zůstane v $S$ podle vztahu (\ref{eq:rozdil-hran-vrch}) alespoň $\frac{n}{2\rho(G)}$ vrcholů, čímž je věta dokázána. \end{proof} \begin{thm} \label{thm:odhad-omega-G}Pro libovolný graf $G=(V,E)$ platí\[ \omega(G)\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)}.\] \end{thm} \begin{proof} bude opět pravděpodobnostní. BÚNO předpokládejme $V=\hat{n}$. Náhodně vybereme permutaci $\pi\in S_{n}$, které přiřadíme množninu $C_{\pi}\subset V$ takto: \begin{itemize} \item $\pi(1)\in C_{\pi}$ \item pro $i>1$ dáme vrchol $\pi(i)$ do $C_{\pi}$, pokud $\left(\forall j<i\right)\left(\{\pi(i),\pi(j)\}\in E\right)$, tj. vrchol se dostane do $C_{\pi}$, jestliže je v hraně se všemi předchozími vrcholy při jejich uspořádání podle permutace $\pi$. \end{itemize} $C_{\pi}$ je zřejmě klika v $G$. Její velikost je náhodná veličina, kterou označíme $X$. Nyní postupujeme jako obvykle: Ukážeme-li \[ \E X\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)},\] bude důkaz hotov, protože pak existuje konkrétní $C_{\pi}$, pro niž je $X\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)}$. Pro každé $v\in V$ definujeme\[ X_{v}=\begin{cases} 1 & v\in C_{\pi}\\ 0 & v\notin C_{\pi}\end{cases}.\] Potom\[ \E X_{v}=\Pr(v\in C_{\pi})=\frac{1}{n-d_{G}(v)},\] což nyní dokážeme. Aby $v\in C_{\pi}$, tak vrcholy, se kterými $v$ není v hraně, musí být v permutaci $\pi$ umístěny až za ním. Na umístění jeho sousedů nezáleží. Počet vrcholů, se kterými $v$ není v hraně, a to včetně vrcholu $v$ samotného, je $n-d_{G}(v)$. Počet způsobů, kterými lze $n-d_{G}(v)$ vrcholů uspořádat tak, aby $v$ byl na prvním místě, je $\left(n-d_{G}(v)-1\right)!$. Počet všech uspořádání $n-d_{G}(v)$ vrcholů je $\left(n-d_{G}(v)\right)!$, a proto\[ \Pr(v\in C_{\pi})=\frac{\left(n-d_{G}(v)-1\right)!}{\left(n-d_{G}(v)\right)!}=\frac{1}{n-d_{G}(v)}\] Konečně tedy můžeme vyčíslit\[ \E X=\sum_{v\in V}X_{v}=\sum_{v\in V}\frac{1}{n-d_{G}(v)}.\] \end{proof} Důsledkem této věty je věta \ref{thm:odhad-alfa-G-pomoci-ro-G}, kterou nyní dokážeme. \begin{proof} Nechť $G$ je libovolný graf. Potom podle předchozí věty je\[ \omega(\bar{G})\geq\sum_{v\in V}\frac{1}{n-d_{\bar{G}}(v)},\] přičemž platí $d_{\bar{G}}(v)=n-1-d_{G}(v)$ a $\alpha(G)=\omega(\bar{G})$. Proto\begin{equation} \alpha(G)\geq\sum_{v\in V}\frac{1}{1+d_{G}(v)}.\label{eq:odhad-alfa-G}\end{equation} Protože funkce $\frac{1}{1+x}$ je na intervalu $[0,+\infty)$ konvexní, můžeme podle Jensenovy nerovnosti \ref{lem:jensenova-nerovnost} provést odhad\[ \frac{n}{1+\frac{1}{n}\sum\limits _{i=1}^{n}x_{i}}\leq\sum_{i=1}^{n}\frac{1}{1+x_{i}}.\] Pokud jej použijeme na vztah (\ref{eq:odhad-alfa-G}), dostaneme\[ \alpha(G)\geq\sum_{v\in V}\frac{1}{1+d_{G}(v)}\geq\frac{n}{1+\frac{1}{n}\sum\limits _{v\in V}d_{G}(v)}=\frac{n}{1+\rho(G)}.\] \end{proof} Pomocí věty \ref{thm:odhad-omega-G} můžeme provést i alternativní důkaz Turánovy věty \ref{thm:turan}, která říká: Pokud $G=(V,E)$ neobsahuje kliku $K_{p}$, tak $\# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right)$ . Vyjdeme ze Schwarzovy nerovnosti na prostoru $\R^{n}$ se standardním skalárním součinem. Pro $\vec{x},\vec{y}\in\R^{n}$ platí\[ \left|\left(\vec{x},\vec{y}\right)\right|^{2}\leq\left\Vert \vec{x}\right\Vert ^{2}\left\Vert \vec{y}\right\Vert ^{2}.\] Nechť $G=(V,E)$, $V=\hat{n}$. Označme $d_{i}=d_{G}(i)$ pro každé $i\in V$ a zvolme konkrétně\begin{eqnarray*} \vec{x} & = & \left(\frac{1}{\sqrt{n-d_{1}}},\frac{1}{\sqrt{n-d_{2}}},...,\frac{1}{\sqrt{n-d_{n}}}\right),\\ \vec{y} & = & \left(\sqrt{n-d_{1}},\sqrt{n-d_{2}},...,\sqrt{n-d_{n}}\right).\end{eqnarray*} Potom má Schwarzova nerovnost tvar\begin{equation} n^{2}=\underbrace{\left(\sum_{i=1}^{n}\frac{1}{\sqrt{n-d_{i}}}\sqrt{n-d_{i}}\right)}_{\left|\left(\vec{x},\vec{y}\right)\right|^{2}}\leq\underbrace{\sum_{i=1}^{n}\frac{1}{n-d_{i}}}_{\left\Vert \vec{x}\right\Vert ^{2}}\underbrace{\sum_{j=1}^{n}(n-d_{j})}_{\left\Vert \vec{y}\right\Vert ^{2}}.\label{eq:schwarz-turan}\end{equation} Protože podle předpokladu $G$ neobsahuje $K_{p}$, platí podle věty \ref{thm:odhad-omega-G}\[ \sum_{i=1}^{n}\frac{1}{n-d_{i}}\leq\omega(G)\leq p-1.\] Po dosazení do \ref{eq:schwarz-turan} dostáváme\begin{eqnarray*} n^{2} & \leq & (p-1)\left(n^{2}-2\# E\right)\\ 2(p-1)\# E & \leq & (p-2)n^{2}\\ \# E & \leq & \frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right).\end{eqnarray*} \begin{thm} \label{thm:posloupnost-nahod-grafu}Nechť $G_{n}$ označuje náhodný graf na $n$ vrcholech% \footnote{$G_{n}$ vznikne tak, že každé dva vrcholy spojíme hranou s pravděpodobností $\frac{1}{2}$. ,,Náhodná veličina{}`` $G_{n}$ má potom rovnoměrné rozdělení.% }. Potom existuje posloupnost $\left(k_{n}\right)_{n\in\N}$ taková, že\begin{equation} \lim_{n\to\infty}\Pr\left(\left(\omega(G_{n})=k_{n}\right)\vee\left(\omega(G_{n})=k_{n}+1\right)\right)=1\label{eq:posloupnost_kn}\end{equation} \end{thm} \begin{rem*} ~ \begin{itemize} \item Pro posloupnost $\left(k_{n}\right)_{n\in\N}$ platí řádově\[ \lim_{n\to\infty}\frac{k_{n}}{2\log_{2}n}=1.\] \item Je-li $G_{n}$ náhodný graf, potom $\bar{G}_{n}$ je také náhodný graf, a přitom $\omega(\bar{G}_{n})=\alpha(G_{n})$. Proto je (\ref{eq:posloupnost_kn}) ekvivalentní s\[ \lim_{n\to\infty}\Pr\left(\left(\alpha(G_{n})=k_{n}\right)\vee\left(\alpha(G_{n})=k_{n}+1\right)\right)=1.\] \end{itemize} \end{rem*}
