01ZTGA:Kapitola2 1

Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 14:11, kterou vytvořil Karel.brinda (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
PDF [ 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.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214: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}

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01ZTGA:Kapitola2_1&oldid=4531“