01ZTGA:Kapitola2 1: 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{Brouwerova věta o pevném bodě} | ||
+ | |||
+ | Následující věta má velmi zajímavý důkaz, který využívá jen jedinou | ||
+ | maličkost z teorie grafů, a sice že součet všech stupňů vrcholů grafu | ||
+ | je sudý. Přesto je zařazena do této přednášky jako příklad aplikace | ||
+ | teorie grafů tam, kde bychom to možná nečekali. | ||
+ | |||
+ | \begin{thm} | ||
+ | \textbf{\emph{(Brouwer)}} | ||
+ | |||
+ | Nechť $f$ je spojité zobrazení uzavřené koule $B\subset\R^{d}$ do | ||
+ | $B$. Potom $f$ má pevný bod, tj.\[ | ||
+ | \left(\exists x\in B\right)\left(f(x)=x\right).\] | ||
+ | |||
+ | \end{thm} | ||
+ | \begin{rem*} | ||
+ | Pokud $d=1$, je důkaz tvrzení snadný. Uzavřená koule reprezentuje | ||
+ | uzavřený interval na reálné ose. Vezměme tedy například\[ | ||
+ | f:[0,1]\mapsto[0,1].\] | ||
+ | Definujme\[ | ||
+ | g(x)=f(x)-x\] | ||
+ | a ptejme se, zda existuje $x\in[0,1]$ takové, že $g(x)=0$. Zřejmě | ||
+ | platí\begin{eqnarray*} | ||
+ | g(0)=f(0)-0 & \geq & 0,\\ | ||
+ | g(1)=f(1)-1 & \leq & 0.\end{eqnarray*} | ||
+ | Protože $f$ je spojitá funkce, je i $g$ spojitá a proto nutně $\left(\exists x\in[0,1]\right)\left(g(x)=0\right)$. | ||
+ | \end{rem*} | ||
+ | Skutečný důkaz Brouwerovy věty provedeme detailně jen pro $d=2$. | ||
+ | Pro obecné $d$ je myšlenka důkazu stejná, ale technické detaily jsou | ||
+ | komplikovanější: Ukážeme totiž platnost věty pro trojúhelník místo | ||
+ | pro kouli v $\R^{2}$ (což je kruh). Pro obecné $d$ bychom větu dokazovali | ||
+ | pro $d$-simplex místo pro kouli v $\R^{d}$. | ||
+ | |||
+ | Nejprve předvedeme, jak platnost tvrzení pro trojúhelník implikuje | ||
+ | jeho platnost pro kruh. Existuje totiž spojitá bijekce $\varphi$ | ||
+ | kruhu $B$ na trojúhelník $T$, což můžeme vidět na obrázku \ref{cap:brouwer1}. | ||
+ | Kruhu s poloměrem $r$ opíšeme libovolný trojúhelník. Každý bod $A$ | ||
+ | v kruhu $B$ kromě středu spojíme se středem $S$ polopřímkou $p$, | ||
+ | která protíná kružnici $B$ ve vzdálenosti $r$ od $S$ a trojúhelník | ||
+ | $T$ ve vzdálenosti $t$ od $S$. Hodnotu $\varphi(A)$ pak definujeme | ||
+ | jako bod na $p$ ve vzdálenosti $\frac{t}{r}\left|\overline{AS}\right|$ | ||
+ | od $S$.% | ||
+ | \begin{figure} | ||
+ | \begin{center} | ||
+ | %Title: brouwer.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:24:24 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.114}}} at 9.167 19.408 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.114}}} at 8.333 19.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.114}}} at 9.138 20.064 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.953:0.953 360 degrees | ||
+ | from 10.001 19.526 center at 9.049 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 9.049 19.526 10.001 18.574 / | ||
+ | % | ||
+ | % arrow head | ||
+ | % | ||
+ | \plot 9.534 18.825 10.001 18.574 9.750 19.041 / | ||
+ | % | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 9.049 19.526 9.286 20.955 / | ||
+ | % | ||
+ | % arrow head | ||
+ | % | ||
+ | \plot 9.353 20.429 9.286 20.955 9.052 20.479 / | ||
+ | % | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 9.049 19.526 7.620 19.050 / | ||
+ | % | ||
+ | % arrow head | ||
+ | % | ||
+ | \plot 8.054 19.355 7.620 19.050 8.150 19.066 / | ||
+ | % | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\putrule from 7.381 18.574 to 10.715 18.574 | ||
+ | \plot 10.715 18.574 9.049 21.431 / | ||
+ | \plot 9.049 21.431 7.381 18.574 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}S}% | ||
+ | } [lB] at 8.780 19.588 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}A}% | ||
+ | } [lB] at 8.215 19.408 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 7.334 21.478 and 10.761 18.527 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | |||
+ | |||
+ | \caption{\label{cap:brouwer1}Bijekce kruhu na trojúhelník} | ||
+ | \end{figure} | ||
+ | |||
+ | |||
+ | Nechť nyní $f:B\mapsto B$ je spojité zobrazení. Potom zobrazení $h=\varphi\circ f\circ\varphi^{-1}$ | ||
+ | je $h:T\mapsto T$ a je spojité. Podle Brouwerovy věty dokázané pro | ||
+ | trojúhelník existuje $x\in T$ takový, že $h(x)=x$, neboli $\varphi\left(f\left(\varphi^{-1}(x)\right)\right)=x$. | ||
+ | Potom ale\[ | ||
+ | f\left(\varphi^{-1}(x)\right)=\varphi^{-1}(x),\] | ||
+ | takže $\varphi^{-1}(x)\in B$ je pevným bodem zobrazení $f$. | ||
+ | |||
+ | Dále tedy budeme směřovat k důkazu Brouwerovy věty pro trojúhelník. | ||
+ | |||
+ | \begin{defn} | ||
+ | Nechť $T$ je trojúhelník. Trojúhelníky $T_{1},T_{2},...,T_{k}$ nazveme | ||
+ | \textbf{triangulizací} (angl. \emph{simplicial subdivision}) trojúhelníku | ||
+ | $T$, jestliže $\bigcup_{i=1}^{k}T_{i}=T$ a pro každé $i,j\in\hat{k},i\neq j$ | ||
+ | je $T_{i}\cap T_{j}$ buď $\emptyset$, nebo společný vrchol trojúhelníků | ||
+ | $T_{i}$ a $T_{j}$, nebo společná strana trojhelníků $T_{i}$ a $T_{j}$. | ||
+ | \end{defn} | ||
+ | \begin{example*} | ||
+ | V levém trojúhelníku na obrázku \ref{cap:triang1} je vytvořena triangulizace, | ||
+ | v pravém však nikoliv, neboť některé trojúhelníky mají průnik tvořící | ||
+ | jen část strany jednoho z nich.% | ||
+ | \begin{figure} | ||
+ | \begin{center} | ||
+ | %Title: triangulizace.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:27:28 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}}}) | ||
+ | \setdots < 0.1143cm> | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 10.833 21.907 center at 10.478 21.907 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setsolid | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 21.907 11.906 20.955 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 9.525 21.907 10.001 20.955 / | ||
+ | \plot 10.001 20.955 10.954 22.860 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 6.191 21.670 6.668 21.907 / | ||
+ | \plot 6.668 21.907 6.428 20.955 / | ||
+ | \plot 6.428 20.955 6.191 21.670 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 5.239 20.955 6.191 21.670 / | ||
+ | \putrule from 6.191 21.670 to 6.191 22.860 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 4.763 21.907 5.239 20.955 / | ||
+ | \plot 5.239 20.955 6.191 22.860 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 8.096 20.955 10.954 22.860 / | ||
+ | \plot 10.954 22.860 11.906 20.955 / | ||
+ | \putrule from 11.906 20.955 to 8.096 20.955 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 3.334 20.955 6.191 22.860 / | ||
+ | \plot 6.191 22.860 7.144 20.955 / | ||
+ | \putrule from 7.144 20.955 to 3.334 20.955 | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}ne}% | ||
+ | } [lB] at 9.881 20.242 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}ano}% | ||
+ | } [lB] at 4.881 20.242 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 3.287 22.907 and 11.953 20.210 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | |||
+ | |||
+ | \caption{\label{cap:triang1},,Správná{}`` a ,,nesprávná{}`` triangulizace} | ||
+ | \end{figure} | ||
+ | |||
+ | \end{example*} | ||
+ | \begin{defn} | ||
+ | Buď $T$ trojúhelník s vrcholy $e_{1},e_{2},e_{3}$, nechť $T_{1},T_{2},...,T_{k}$ | ||
+ | je jeho trianglulizace. Obarvení vrcholů trojúhelníků $T_{1},T_{2},...,T_{k}$ | ||
+ | barvami $1,2,3$ se nazývá vlastní, jestliže pro každé $i,j\in\{1,2,3\},i\neq j$ | ||
+ | platí | ||
+ | \begin{enumerate} | ||
+ | \item $e_{i}$ má barvu $i$, | ||
+ | \item vrcholy trojúhelníků ležící na úsečce $\overline{e_{i}e_{j}}$ mají | ||
+ | barvu $i$ nebo $j$. | ||
+ | \end{enumerate} | ||
+ | Barvy vrcholů uvnitř trojúhelníku $T$ nejsou důležité. | ||
+ | \end{defn} | ||
+ | \begin{lem} | ||
+ | \textbf{\emph{(Sperner, 1928)}} | ||
+ | |||
+ | Nechť $T$ je trojúhelník, $T_{1},T_{2},...,T_{k}$ jeho triangulizace. | ||
+ | Potom při každém vlastním obarvení vrcholů trojúhelníků $T_{1},T_{2},...,T_{k}$ | ||
+ | barvami $1,2,3$ existuje $i\in\hat{k}$ takové, že $T_{i}$ má vrcholy | ||
+ | obarveny všemi třemi barvami. | ||
+ | \end{lem} | ||
+ | \begin{proof} | ||
+ | Dané triangulizaci přiřadíme graf $G=(V,E)$, jenž bude zkonstruován | ||
+ | takto: | ||
+ | \begin{itemize} | ||
+ | \item Množina vrcholů $V$ grafu $G$ bude tvořena trojúhelníky $T,T_{1},T_{2},...,T_{k}$. | ||
+ | \item Množina hran bude splňovat následující dvě podmínky: | ||
+ | |||
+ | \begin{itemize} | ||
+ | \item $\{ T_{i},T_{j}\}\in E$, právě když $T_{i}\cap T_{j}$ je jejich | ||
+ | společná strana, jejíž konce jsou vrcholy (trojúhelníků) obarvené | ||
+ | právě oběma barvami $1$ a $2$. | ||
+ | \item $\{ T,T_{i}\}\in E$, právě když $T_{i}$ má stranu s koncovými vrcholy | ||
+ | obarvenými oběma barvami $1$ a $2$ a tato strana leží ve straně | ||
+ | trojúhelníka $T$ (jejíž koncové vrcholy jsou tedy také obarveny barvami | ||
+ | $1$ a $2$). | ||
+ | \end{itemize} | ||
+ | \end{itemize} | ||
+ | Je jasné, že pro stupně vrcholů $T_{i}$ grafu $G$ platí $0\leq d_{G}(T_{i})\leq2$ | ||
+ | pro každé $i\in\hat{k}$. Není totiž možné, aby všechny tři strany | ||
+ | trojúhelníka měly konce obarvené oběma barvami $1$ a $2$. Stupeň | ||
+ | $T$ jako vrcholu grafu $G$ je svázán s pokrytím strany $\overline{e_{1}e_{2}}$ | ||
+ | trojúhelníky z triangulizace: | ||
+ | |||
+ | \smallskip{} | ||
+ | \hfill{} | ||
+ | \begin{center} | ||
+ | %Title: triangulizace2.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:48:08 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 TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 7.620 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 8.810 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 9.644 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 10.715 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 11.549 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 12.383 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 13.096 18.218 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 14.288 18.216 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$e_{1}$}% | ||
+ | } [lB] at 7.620 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$e_{2}$}% | ||
+ | } [lB] at 14.167 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{2}$}% | ||
+ | } [lB] at 8.810 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{3}$}% | ||
+ | } [lB] at 9.525 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{4}$}% | ||
+ | } [lB] at 10.715 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{5}$}% | ||
+ | } [lB] at 11.549 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{6}$}% | ||
+ | } [lB] at 12.383 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{7}$}% | ||
+ | } [lB] at 13.096 18.931 | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 8.810 19.526 9.404 20.479 / | ||
+ | \plot 9.404 20.479 9.644 19.526 / | ||
+ | \plot 9.644 19.526 10.120 20.955 / | ||
+ | \plot 10.120 20.955 10.715 19.526 / | ||
+ | \plot 10.715 19.526 11.191 20.360 / | ||
+ | \plot 11.191 20.360 11.549 19.526 / | ||
+ | \plot 11.549 19.526 12.025 20.599 / | ||
+ | \plot 12.025 20.599 12.383 19.526 / | ||
+ | \plot 12.383 19.526 12.738 20.360 / | ||
+ | \plot 12.738 20.360 13.096 19.526 / | ||
+ | \plot 13.096 19.526 13.214 20.003 / | ||
+ | \plot 13.214 20.003 14.288 19.526 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 8.691 20.955 8.810 19.526 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 14.288 19.526 12.383 21.431 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 7.620 19.526 9.049 21.431 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\putrule from 7.620 19.526 to 14.288 19.526 | ||
+ | }% | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 7.573 21.478 and 14.334 18.184 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | \hfill{} | ||
+ | \smallskip{} | ||
+ | |||
+ | Předpokládejme, že na hraně $\overline{e_{1}e_{2}}$ jsou zleva doprava | ||
+ | uspořádány vrcholy \[ | ||
+ | e_{1}=a_{1},a_{2},....,a_{l-1},a_{l}=e_{2}.\] | ||
+ | Jestliže barva $a_{j}$ se liší od barvy $a_{j+1}$, tak podle definice | ||
+ | grafu $G$ je trojúhelník $T_{i}$ , který má jako jednu z hran úsečku | ||
+ | $\overline{a_{j}a_{j+1}}$, v hraně s $T$. Každá změna barvy vrcholu | ||
+ | $1\to2$ nebo $2\to1$ při procházení strany $\overline{e_{1}e_{2}}$ | ||
+ | zleva doprava tedy přispívá jedničkou ke stupni $T$. Protože ale | ||
+ | $e_{1}=a_{1}$ má barvu $1$ a $e_{2}=a_{l}$ má barvu $2$, tak těchto | ||
+ | změn je lichý počet. Stupeň $T$ je tedy lichý. Nyní využijeme, že\[ | ||
+ | \sum_{v\in V}d_{G}(v)=\sum_{i=1}^{k}d_{G}(T_{i})+d_{G}(T)=2\# E,\] | ||
+ | takže součet $\sum_{i=1}^{k}d_{G}(T_{i})+d_{G}(T)$ je sudý. Tím pádem | ||
+ | $\sum_{i=1}^{k}T_{i}$ je lichý. Existuje tedy další vrchol grafu | ||
+ | $G$ (tj. trojúhelník triangulace $T_{i}$) s lichým stupněm, který | ||
+ | tak musí být roven $1$. Jinými slovy, tento trojúhelník má v $G$ | ||
+ | jen jediného souseda, což znamená, že dva jeho vrcholy mají barvy | ||
+ | $1$ a $2$, ale třetí vrchol už musí mít barvu $3$: | ||
+ | |||
+ | \hfill{} | ||
+ | \begin{center} | ||
+ | %Title: triangulizace3.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:13: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 POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 5.715 23.336 4.286 21.431 / | ||
+ | \putrule from 4.286 21.431 to 7.620 21.431 | ||
+ | \plot 7.620 21.431 5.715 23.336 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}% | ||
+ | } [lB] at 7.857 21.313 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 5.596 23.575 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 3.929 21.313 | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=2pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 4.286 21.431 5.715 23.336 / | ||
+ | }% | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 3.897 24.100 and 7.889 21.281 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | \hfill{}~ | ||
+ | \end{proof} | ||
+ | Nyní už můžeme dokázat přímo Brouwerovu větu: | ||
+ | |||
+ | \begin{proof} | ||
+ | Mějme tedy trojúhelník $T$ s vrcholy $e_{1},e_{2},e_{3}$ v lineárním | ||
+ | prostoru $\R^{2}$. Každý bod $x\in T$ můžeme vyjádřit jako konvexní | ||
+ | kombinaci\[ | ||
+ | x=\alpha_{1}e_{1}+\alpha_{2}e_{2}+\alpha_{3}e_{3},\] | ||
+ | kde\[ | ||
+ | \alpha_{i}\geq0,\] | ||
+ | \begin{equation} | ||
+ | \alpha_{1}+\alpha_{2}+\alpha_{3}=1.\label{eq:konvex-sum1}\end{equation} | ||
+ | Označme si obecně pro libovolný $x\in T$ $i$-tou souřadnici bodu | ||
+ | $x$ v uvedené konvexní kombinaci jako $\alpha_{i}(x)$. Obdobně \[ | ||
+ | f(x)=\alpha_{1}'e_{1}+\alpha_{2}'e_{2}+\alpha_{3}'e_{3},\] | ||
+ | kde\[ | ||
+ | \alpha_{i}'\geq0,\] | ||
+ | \begin{eqnarray} | ||
+ | \alpha_{1}'+\alpha_{2}'+\alpha_{3}' & = & 1.\label{eq:konvex-sum2}\end{eqnarray} | ||
+ | Označme si obdobně $i$-tou souřadnici $f(x)$ v konvexní kombinaci | ||
+ | bodů $e_{1},e_{2},e_{3}$ jako $\alpha_{i}'(x)$. Je-li $x$ pevným | ||
+ | bodem zobrazení $f$, potom $\alpha_{i}'(x)=\alpha_{i}(x)$ pro každé | ||
+ | $i\in\{1,2,3\}$. | ||
+ | |||
+ | Postupujme sporem, tj. předpokládejme, že $f$ nemá pevný bod. Potom | ||
+ | lze korektně definovat obarvení každého bodu $x\in T$ jako zobrazení\begin{equation} | ||
+ | b(x):=\min\left\{ \left.i\in\{1,2,3\}\right|\alpha_{i}(x)>\alpha_{i}'(x)\right\} .\label{eq:brouwer-obarveni}\end{equation} | ||
+ | Pro toto obarvení platí: | ||
+ | \begin{itemize} | ||
+ | \item $\left(\forall i\in\{1,2,3\}\right)\left(b(e_{i})=i\right)$. Například | ||
+ | $e_{1}=1\cdot e_{1}+0\cdot e_{2}+0\cdot e_{3}$, takže s přihlédnutím | ||
+ | k (\ref{eq:konvex-sum1}) a (\ref{eq:konvex-sum2}) nutně $\alpha_{1}(e_{1})>\alpha_{1}'(e_{1})$. | ||
+ | \item Dále $\left(\forall i,j\in\{1,2,3\},i\neq j\right)\left(x\in\overline{e_{i}e_{j}}\Rightarrow b(x)\in\{ i,j\}\right)$. | ||
+ | Například každé $x\in\overline{e_{1}e_{2}}$ má barvu $1$ nebo $2$. | ||
+ | Pro takové $x$ je totiž $\alpha_{3}(x)=0$, takže nemůže být $\alpha_{3}(x)>\alpha_{3}'(x)$. | ||
+ | \end{itemize} | ||
+ | Zvolme nyní posloupnost triangulací trojúhelníku $T$ označenou\[ | ||
+ | T_{1}^{(n)},T_{2}^{(n)},...,T_{k_{n}}^{(n)}\] | ||
+ | tak, že pro $n\to\infty$ jde maximum obvodů trojúhelníků z $n$-té | ||
+ | triangulace k nule. Obarvíme-li všechny vrcholy v triangulizaci podle | ||
+ | zobrazení $b$, bude se jednat o vlastní obarvení. Podle Spernerova | ||
+ | lemmatu existuje pro každé $n$ trojúhelník $T_{i_{n}}^{(n)}$, který | ||
+ | má vrcholy obarveny všemi třemi barvami. Označme | ||
+ | \begin{lyxlist}{00.00.0000} | ||
+ | \item [$x_{n}$]vrchol $T_{i_{n}}^{(n)}$ s barvou $1$, | ||
+ | \item [$y_{n}$]vrchol $T_{i_{n}}^{(n)}$ s barvou $2$, | ||
+ | \item [$z_{n}$]vrchol $T_{i_{n}}^{(n)}$ s barvou $3$. | ||
+ | \end{lyxlist} | ||
+ | Protože $T$ je kompaktní množina, existuje konvergentní podposloupnost | ||
+ | $\left(x_{j_{n}}\right)_{n\in\N}$ vybraná z $\left(x_{n}\right)_{n\in\N}$, | ||
+ | kterou budeme nadále označovat opět jako $\left(x_{n}\right)_{n\in\N}$. | ||
+ | To samé platí pro posloupnosti $\left(y_{n}\right)_{n\in\N}$ a $\left(z_{n}\right)_{n\in\N}$. | ||
+ | Nechť $w$ je limita posloupnosti $\left(x_{n}\right)_{n\in\N}$. | ||
+ | Potom však\[ | ||
+ | y_{n}=\underbrace{y_{n}-x_{n}}_{\to0}+x_{n}\xrightarrow[n\to\infty]{}w\] | ||
+ | a stejně tak \[ | ||
+ | z_{n}\xrightarrow[n\to\infty]{}w.\] | ||
+ | |||
+ | |||
+ | Protože $x_{n}$ má pro každé $n$ barvu $1$, tak podle (\ref{eq:brouwer-obarveni}) | ||
+ | platí $\alpha_{1}(x)>\alpha_{1}'(x)$. Protože $f$ je spojitá, je | ||
+ | i souřadnice $\alpha_{1}'(x)$ spojitou funkcí $\alpha_{1}(x)$ (a | ||
+ | rovněž ostatních souřadnic), takže v limitě platí\begin{eqnarray*} | ||
+ | \alpha_{1}(w) & \geq & \alpha_{1}'(w).\end{eqnarray*} | ||
+ | Pro ostatní souřadnice však dostaneme z vlastností $y_{n}$ a $z_{n}$ | ||
+ | stejný vztah:\begin{eqnarray*} | ||
+ | \alpha_{2}(w) & \geq & \alpha_{2}'(w),\\ | ||
+ | \alpha_{2}(w) & \geq & \alpha_{2}'(w).\end{eqnarray*} | ||
+ | Po sečtení všech nerovností dostaneme\[ | ||
+ | 1=\alpha_{1}(w)+\alpha_{2}(w)+\alpha_{3}(w)\geq\alpha_{1}'(w)+\alpha_{2}'(w)+\alpha_{3}'(w)=1\] | ||
+ | a proto musí platit rovnosti $\alpha_{i}(w)=\alpha_{i}'(w)$ pro každé | ||
+ | $i\in\{1,2,3\}$. To ale znamená, že $f(w)=w$, což je spor. | ||
+ | \end{proof} |
Aktuální verze z 15. 1. 2012, 14:11
[ 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{Brouwerova věta o pevném bodě} Následující věta má velmi zajímavý důkaz, který využívá jen jedinou maličkost z teorie grafů, a sice že součet všech stupňů vrcholů grafu je sudý. Přesto je zařazena do této přednášky jako příklad aplikace teorie grafů tam, kde bychom to možná nečekali. \begin{thm} \textbf{\emph{(Brouwer)}} Nechť $f$ je spojité zobrazení uzavřené koule $B\subset\R^{d}$ do $B$. Potom $f$ má pevný bod, tj.\[ \left(\exists x\in B\right)\left(f(x)=x\right).\] \end{thm} \begin{rem*} Pokud $d=1$, je důkaz tvrzení snadný. Uzavřená koule reprezentuje uzavřený interval na reálné ose. Vezměme tedy například\[ f:[0,1]\mapsto[0,1].\] Definujme\[ g(x)=f(x)-x\] a ptejme se, zda existuje $x\in[0,1]$ takové, že $g(x)=0$. Zřejmě platí\begin{eqnarray*} g(0)=f(0)-0 & \geq & 0,\\ g(1)=f(1)-1 & \leq & 0.\end{eqnarray*} Protože $f$ je spojitá funkce, je i $g$ spojitá a proto nutně $\left(\exists x\in[0,1]\right)\left(g(x)=0\right)$. \end{rem*} Skutečný důkaz Brouwerovy věty provedeme detailně jen pro $d=2$. Pro obecné $d$ je myšlenka důkazu stejná, ale technické detaily jsou komplikovanější: Ukážeme totiž platnost věty pro trojúhelník místo pro kouli v $\R^{2}$ (což je kruh). Pro obecné $d$ bychom větu dokazovali pro $d$-simplex místo pro kouli v $\R^{d}$. Nejprve předvedeme, jak platnost tvrzení pro trojúhelník implikuje jeho platnost pro kruh. Existuje totiž spojitá bijekce $\varphi$ kruhu $B$ na trojúhelník $T$, což můžeme vidět na obrázku \ref{cap:brouwer1}. Kruhu s poloměrem $r$ opíšeme libovolný trojúhelník. Každý bod $A$ v kruhu $B$ kromě středu spojíme se středem $S$ polopřímkou $p$, která protíná kružnici $B$ ve vzdálenosti $r$ od $S$ a trojúhelník $T$ ve vzdálenosti $t$ od $S$. Hodnotu $\varphi(A)$ pak definujeme jako bod na $p$ ve vzdálenosti $\frac{t}{r}\left|\overline{AS}\right|$ od $S$.% \begin{figure} \begin{center} %Title: brouwer.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:24:24 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.114}}} at 9.167 19.408 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.114}}} at 8.333 19.289 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.114}}} at 9.138 20.064 }% % % Fig ELLIPSE % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.953:0.953 360 degrees from 10.001 19.526 center at 9.049 19.526 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 9.049 19.526 10.001 18.574 / % % arrow head % \plot 9.534 18.825 10.001 18.574 9.750 19.041 / % }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 9.049 19.526 9.286 20.955 / % % arrow head % \plot 9.353 20.429 9.286 20.955 9.052 20.479 / % }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 9.049 19.526 7.620 19.050 / % % arrow head % \plot 8.054 19.355 7.620 19.050 8.150 19.066 / % }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 7.381 18.574 to 10.715 18.574 \plot 10.715 18.574 9.049 21.431 / \plot 9.049 21.431 7.381 18.574 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}S}% } [lB] at 8.780 19.588 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}A}% } [lB] at 8.215 19.408 \linethickness=0pt \putrectangle corners at 7.334 21.478 and 10.761 18.527 \endpicture} \end{center} \caption{\label{cap:brouwer1}Bijekce kruhu na trojúhelník} \end{figure} Nechť nyní $f:B\mapsto B$ je spojité zobrazení. Potom zobrazení $h=\varphi\circ f\circ\varphi^{-1}$ je $h:T\mapsto T$ a je spojité. Podle Brouwerovy věty dokázané pro trojúhelník existuje $x\in T$ takový, že $h(x)=x$, neboli $\varphi\left(f\left(\varphi^{-1}(x)\right)\right)=x$. Potom ale\[ f\left(\varphi^{-1}(x)\right)=\varphi^{-1}(x),\] takže $\varphi^{-1}(x)\in B$ je pevným bodem zobrazení $f$. Dále tedy budeme směřovat k důkazu Brouwerovy věty pro trojúhelník. \begin{defn} Nechť $T$ je trojúhelník. Trojúhelníky $T_{1},T_{2},...,T_{k}$ nazveme \textbf{triangulizací} (angl. \emph{simplicial subdivision}) trojúhelníku $T$, jestliže $\bigcup_{i=1}^{k}T_{i}=T$ a pro každé $i,j\in\hat{k},i\neq j$ je $T_{i}\cap T_{j}$ buď $\emptyset$, nebo společný vrchol trojúhelníků $T_{i}$ a $T_{j}$, nebo společná strana trojhelníků $T_{i}$ a $T_{j}$. \end{defn} \begin{example*} V levém trojúhelníku na obrázku \ref{cap:triang1} je vytvořena triangulizace, v pravém však nikoliv, neboť některé trojúhelníky mají průnik tvořící jen část strany jednoho z nich.% \begin{figure} \begin{center} %Title: triangulizace.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:27:28 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}}}) \setdots < 0.1143cm> {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 10.833 21.907 center at 10.478 21.907 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setsolid {\color[rgb]{0,0,0}\plot 10.478 21.907 11.906 20.955 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 9.525 21.907 10.001 20.955 / \plot 10.001 20.955 10.954 22.860 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 6.191 21.670 6.668 21.907 / \plot 6.668 21.907 6.428 20.955 / \plot 6.428 20.955 6.191 21.670 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 5.239 20.955 6.191 21.670 / \putrule from 6.191 21.670 to 6.191 22.860 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 4.763 21.907 5.239 20.955 / \plot 5.239 20.955 6.191 22.860 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 8.096 20.955 10.954 22.860 / \plot 10.954 22.860 11.906 20.955 / \putrule from 11.906 20.955 to 8.096 20.955 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 3.334 20.955 6.191 22.860 / \plot 6.191 22.860 7.144 20.955 / \putrule from 7.144 20.955 to 3.334 20.955 }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}ne}% } [lB] at 9.881 20.242 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}ano}% } [lB] at 4.881 20.242 \linethickness=0pt \putrectangle corners at 3.287 22.907 and 11.953 20.210 \endpicture} \end{center} \caption{\label{cap:triang1},,Správná{}`` a ,,nesprávná{}`` triangulizace} \end{figure} \end{example*} \begin{defn} Buď $T$ trojúhelník s vrcholy $e_{1},e_{2},e_{3}$, nechť $T_{1},T_{2},...,T_{k}$ je jeho trianglulizace. Obarvení vrcholů trojúhelníků $T_{1},T_{2},...,T_{k}$ barvami $1,2,3$ se nazývá vlastní, jestliže pro každé $i,j\in\{1,2,3\},i\neq j$ platí \begin{enumerate} \item $e_{i}$ má barvu $i$, \item vrcholy trojúhelníků ležící na úsečce $\overline{e_{i}e_{j}}$ mají barvu $i$ nebo $j$. \end{enumerate} Barvy vrcholů uvnitř trojúhelníku $T$ nejsou důležité. \end{defn} \begin{lem} \textbf{\emph{(Sperner, 1928)}} Nechť $T$ je trojúhelník, $T_{1},T_{2},...,T_{k}$ jeho triangulizace. Potom při každém vlastním obarvení vrcholů trojúhelníků $T_{1},T_{2},...,T_{k}$ barvami $1,2,3$ existuje $i\in\hat{k}$ takové, že $T_{i}$ má vrcholy obarveny všemi třemi barvami. \end{lem} \begin{proof} Dané triangulizaci přiřadíme graf $G=(V,E)$, jenž bude zkonstruován takto: \begin{itemize} \item Množina vrcholů $V$ grafu $G$ bude tvořena trojúhelníky $T,T_{1},T_{2},...,T_{k}$. \item Množina hran bude splňovat následující dvě podmínky: \begin{itemize} \item $\{ T_{i},T_{j}\}\in E$, právě když $T_{i}\cap T_{j}$ je jejich společná strana, jejíž konce jsou vrcholy (trojúhelníků) obarvené právě oběma barvami $1$ a $2$. \item $\{ T,T_{i}\}\in E$, právě když $T_{i}$ má stranu s koncovými vrcholy obarvenými oběma barvami $1$ a $2$ a tato strana leží ve straně trojúhelníka $T$ (jejíž koncové vrcholy jsou tedy také obarveny barvami $1$ a $2$). \end{itemize} \end{itemize} Je jasné, že pro stupně vrcholů $T_{i}$ grafu $G$ platí $0\leq d_{G}(T_{i})\leq2$ pro každé $i\in\hat{k}$. Není totiž možné, aby všechny tři strany trojúhelníka měly konce obarvené oběma barvami $1$ a $2$. Stupeň $T$ jako vrcholu grafu $G$ je svázán s pokrytím strany $\overline{e_{1}e_{2}}$ trojúhelníky z triangulizace: \smallskip{} \hfill{} \begin{center} %Title: triangulizace2.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:48:08 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 TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 7.620 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 8.810 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 9.644 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 10.715 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 11.549 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 12.383 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 13.096 18.218 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 14.288 18.216 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$e_{1}$}% } [lB] at 7.620 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$e_{2}$}% } [lB] at 14.167 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{2}$}% } [lB] at 8.810 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{3}$}% } [lB] at 9.525 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{4}$}% } [lB] at 10.715 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{5}$}% } [lB] at 11.549 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{6}$}% } [lB] at 12.383 18.931 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$a_{7}$}% } [lB] at 13.096 18.931 % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 8.810 19.526 9.404 20.479 / \plot 9.404 20.479 9.644 19.526 / \plot 9.644 19.526 10.120 20.955 / \plot 10.120 20.955 10.715 19.526 / \plot 10.715 19.526 11.191 20.360 / \plot 11.191 20.360 11.549 19.526 / \plot 11.549 19.526 12.025 20.599 / \plot 12.025 20.599 12.383 19.526 / \plot 12.383 19.526 12.738 20.360 / \plot 12.738 20.360 13.096 19.526 / \plot 13.096 19.526 13.214 20.003 / \plot 13.214 20.003 14.288 19.526 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 8.691 20.955 8.810 19.526 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 14.288 19.526 12.383 21.431 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 7.620 19.526 9.049 21.431 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 7.620 19.526 to 14.288 19.526 }% \linethickness=0pt \putrectangle corners at 7.573 21.478 and 14.334 18.184 \endpicture} \end{center} \hfill{} \smallskip{} Předpokládejme, že na hraně $\overline{e_{1}e_{2}}$ jsou zleva doprava uspořádány vrcholy \[ e_{1}=a_{1},a_{2},....,a_{l-1},a_{l}=e_{2}.\] Jestliže barva $a_{j}$ se liší od barvy $a_{j+1}$, tak podle definice grafu $G$ je trojúhelník $T_{i}$ , který má jako jednu z hran úsečku $\overline{a_{j}a_{j+1}}$, v hraně s $T$. Každá změna barvy vrcholu $1\to2$ nebo $2\to1$ při procházení strany $\overline{e_{1}e_{2}}$ zleva doprava tedy přispívá jedničkou ke stupni $T$. Protože ale $e_{1}=a_{1}$ má barvu $1$ a $e_{2}=a_{l}$ má barvu $2$, tak těchto změn je lichý počet. Stupeň $T$ je tedy lichý. Nyní využijeme, že\[ \sum_{v\in V}d_{G}(v)=\sum_{i=1}^{k}d_{G}(T_{i})+d_{G}(T)=2\# E,\] takže součet $\sum_{i=1}^{k}d_{G}(T_{i})+d_{G}(T)$ je sudý. Tím pádem $\sum_{i=1}^{k}T_{i}$ je lichý. Existuje tedy další vrchol grafu $G$ (tj. trojúhelník triangulace $T_{i}$) s lichým stupněm, který tak musí být roven $1$. Jinými slovy, tento trojúhelník má v $G$ jen jediného souseda, což znamená, že dva jeho vrcholy mají barvy $1$ a $2$, ale třetí vrchol už musí mít barvu $3$: \hfill{} \begin{center} %Title: triangulizace3.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:13: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 POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 5.715 23.336 4.286 21.431 / \putrule from 4.286 21.431 to 7.620 21.431 \plot 7.620 21.431 5.715 23.336 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}% } [lB] at 7.857 21.313 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 5.596 23.575 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 3.929 21.313 % % Fig POLYLINE object % \linethickness=2pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}}) {\color[rgb]{0,0,0}\plot 4.286 21.431 5.715 23.336 / }% \linethickness=0pt \putrectangle corners at 3.897 24.100 and 7.889 21.281 \endpicture} \end{center} \hfill{}~ \end{proof} Nyní už můžeme dokázat přímo Brouwerovu větu: \begin{proof} Mějme tedy trojúhelník $T$ s vrcholy $e_{1},e_{2},e_{3}$ v lineárním prostoru $\R^{2}$. Každý bod $x\in T$ můžeme vyjádřit jako konvexní kombinaci\[ x=\alpha_{1}e_{1}+\alpha_{2}e_{2}+\alpha_{3}e_{3},\] kde\[ \alpha_{i}\geq0,\] \begin{equation} \alpha_{1}+\alpha_{2}+\alpha_{3}=1.\label{eq:konvex-sum1}\end{equation} Označme si obecně pro libovolný $x\in T$ $i$-tou souřadnici bodu $x$ v uvedené konvexní kombinaci jako $\alpha_{i}(x)$. Obdobně \[ f(x)=\alpha_{1}'e_{1}+\alpha_{2}'e_{2}+\alpha_{3}'e_{3},\] kde\[ \alpha_{i}'\geq0,\] \begin{eqnarray} \alpha_{1}'+\alpha_{2}'+\alpha_{3}' & = & 1.\label{eq:konvex-sum2}\end{eqnarray} Označme si obdobně $i$-tou souřadnici $f(x)$ v konvexní kombinaci bodů $e_{1},e_{2},e_{3}$ jako $\alpha_{i}'(x)$. Je-li $x$ pevným bodem zobrazení $f$, potom $\alpha_{i}'(x)=\alpha_{i}(x)$ pro každé $i\in\{1,2,3\}$. Postupujme sporem, tj. předpokládejme, že $f$ nemá pevný bod. Potom lze korektně definovat obarvení každého bodu $x\in T$ jako zobrazení\begin{equation} b(x):=\min\left\{ \left.i\in\{1,2,3\}\right|\alpha_{i}(x)>\alpha_{i}'(x)\right\} .\label{eq:brouwer-obarveni}\end{equation} Pro toto obarvení platí: \begin{itemize} \item $\left(\forall i\in\{1,2,3\}\right)\left(b(e_{i})=i\right)$. Například $e_{1}=1\cdot e_{1}+0\cdot e_{2}+0\cdot e_{3}$, takže s přihlédnutím k (\ref{eq:konvex-sum1}) a (\ref{eq:konvex-sum2}) nutně $\alpha_{1}(e_{1})>\alpha_{1}'(e_{1})$. \item Dále $\left(\forall i,j\in\{1,2,3\},i\neq j\right)\left(x\in\overline{e_{i}e_{j}}\Rightarrow b(x)\in\{ i,j\}\right)$. Například každé $x\in\overline{e_{1}e_{2}}$ má barvu $1$ nebo $2$. Pro takové $x$ je totiž $\alpha_{3}(x)=0$, takže nemůže být $\alpha_{3}(x)>\alpha_{3}'(x)$. \end{itemize} Zvolme nyní posloupnost triangulací trojúhelníku $T$ označenou\[ T_{1}^{(n)},T_{2}^{(n)},...,T_{k_{n}}^{(n)}\] tak, že pro $n\to\infty$ jde maximum obvodů trojúhelníků z $n$-té triangulace k nule. Obarvíme-li všechny vrcholy v triangulizaci podle zobrazení $b$, bude se jednat o vlastní obarvení. Podle Spernerova lemmatu existuje pro každé $n$ trojúhelník $T_{i_{n}}^{(n)}$, který má vrcholy obarveny všemi třemi barvami. Označme \begin{lyxlist}{00.00.0000} \item [$x_{n}$]vrchol $T_{i_{n}}^{(n)}$ s barvou $1$, \item [$y_{n}$]vrchol $T_{i_{n}}^{(n)}$ s barvou $2$, \item [$z_{n}$]vrchol $T_{i_{n}}^{(n)}$ s barvou $3$. \end{lyxlist} Protože $T$ je kompaktní množina, existuje konvergentní podposloupnost $\left(x_{j_{n}}\right)_{n\in\N}$ vybraná z $\left(x_{n}\right)_{n\in\N}$, kterou budeme nadále označovat opět jako $\left(x_{n}\right)_{n\in\N}$. To samé platí pro posloupnosti $\left(y_{n}\right)_{n\in\N}$ a $\left(z_{n}\right)_{n\in\N}$. Nechť $w$ je limita posloupnosti $\left(x_{n}\right)_{n\in\N}$. Potom však\[ y_{n}=\underbrace{y_{n}-x_{n}}_{\to0}+x_{n}\xrightarrow[n\to\infty]{}w\] a stejně tak \[ z_{n}\xrightarrow[n\to\infty]{}w.\] Protože $x_{n}$ má pro každé $n$ barvu $1$, tak podle (\ref{eq:brouwer-obarveni}) platí $\alpha_{1}(x)>\alpha_{1}'(x)$. Protože $f$ je spojitá, je i souřadnice $\alpha_{1}'(x)$ spojitou funkcí $\alpha_{1}(x)$ (a rovněž ostatních souřadnic), takže v limitě platí\begin{eqnarray*} \alpha_{1}(w) & \geq & \alpha_{1}'(w).\end{eqnarray*} Pro ostatní souřadnice však dostaneme z vlastností $y_{n}$ a $z_{n}$ stejný vztah:\begin{eqnarray*} \alpha_{2}(w) & \geq & \alpha_{2}'(w),\\ \alpha_{2}(w) & \geq & \alpha_{2}'(w).\end{eqnarray*} Po sečtení všech nerovností dostaneme\[ 1=\alpha_{1}(w)+\alpha_{2}(w)+\alpha_{3}(w)\geq\alpha_{1}'(w)+\alpha_{2}'(w)+\alpha_{3}'(w)=1\] a proto musí platit rovnosti $\alpha_{i}(w)=\alpha_{i}'(w)$ pro každé $i\in\{1,2,3\}$. To ale znamená, že $f(w)=w$, což je spor. \end{proof}