Verze z 15. 1. 2012, 12:41

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Základní pojmy}
 
\begin{notation*}
Nechť $r\in\N$, nechť $V$ je konečná množina. Potom počet prvků
množiny $V$ značíme symbolem $\# V$. Dále značíme\[
\binom{V}{r}=\left\{ \left.A\subset V\right|\# A=r\right\} .\]
To znamená, že $\binom{V}{r}$ označuje množinu všech $r$-prvkových
podmnožin množiny $V$. Dále budeme používat označení\[
\hat{n}=\{1,2,3,...,n\}.\]
 
\end{notation*}
\begin{obs*}
Platí $\#\binom{V}{r}=\binom{\# V}{r}$.
\end{obs*}
 
\subsection{Graf, izomorfismus grafů, samokomplementární grafy}
 
\begin{defn}
Nechť $V$ je konečná množina, $E\subset\binom{V}{2}$. Uspořádaná
dvojice $G=(V,E)$ se nazývá (neorientovaný) \textbf{graf}. $V$ nazýváme
množinou \textbf{vrcholů} (z anglického \textbf{v}ertex), $E$ množinou
\textbf{hran} (z anglického \textbf{e}dge).
\end{defn}
\begin{rem*}
Grafy si zpravidla představujeme tak jako na obrázku \ref{cap:schema-grafu}.
Vrcholy se znázorňují jako body (mohou představovat například města).
Hrany, což jsou dvouprvkové množiny vrcholů. se zobrazují jako úsečky
nebo křivky spojující dané vrcholy (mohou představovat například cesty
mezi danými městy). Řada úloh z teorie grafů má velmi konkrétní využití
v praxi, což si uvědomíme, hned jak si pod vrcholy a hranami představíme
skutečné objekty, jako to ukazují uvedené příklady. Důkazy některých
vět nás však přesvědčí, že strukturu grafu lze mnohdy vybudovat i
nad objekty, které mají daleko do právě popsané geometrické představy
grafu.%
\begin{figure}
\begin{center}\input{figures1/graf.pictex}\end{center}
 
 
\caption{Schéma grafu $V=\{ a,b,c,d\},E=\left\{ \{ a,b\},\{ a,c\},\{ a,d\},\{ c,d\}\right\} $\label{cap:schema-grafu}}
\end{figure}
 
\end{rem*}
\begin{notation*}
Později se ve výkladu vyskytne formálně nesprávné značení, které má
však intuitivní význam. Buďte $G=(V,E)$, $H=(U,F)$ grafy, $v\in V$,
$e\in E$. Potom definujeme:
\begin{itemize}
\item $G\cup H=(V\cup U,E\cup F)$ (tj. oba grafy spojíme do jednoho),
\item $G\backslash F=(V,E\backslash F)$, pokud $F\subset\binom{V}{2}$,
resp. $F\subset E$ (tj. z grafu $G$ ubereme hrany, které leží v
$F$),
\item $G\backslash U=\left(V\backslash U,E\cap\binom{V\backslash U}{2}\right)$
(tj. z grafu $G$ ubereme všechny vrcholy, které leží v $U$, a všechny
hrany, které z nich vedou),
\item $v\equiv\{ v\},e\equiv\{ e\}$ (prvek ztotožníme s jednoprvkovou množinou),
pokud nemůže dojít k nedorozumnění.
\end{itemize}
Dále se vyskytne případ, kdy budeme mluvit o grafu $G$, aniž specifikujeme
množiny jeho vrcholů a hran. Proto nyní zaveďme označení $E(G)$ pro
množinu hran grafu $G$ a označení $V(G)$ pro množinu vrcholů grafu
$G$.
\end{notation*}
\begin{rem*}
Obvykle budeme používat písmena $m,n$ ve smyslu $n=\# V$ a $m=\# E$.
Podle předchozího pozorování můžeme říci, že počet různých grafů na
$n$ vrcholech je\[
2^{\binom{n}{2}},\]
neboť to je počet všech různých podmnožin $E\subset\binom{V}{2}$.
\end{rem*}
\begin{defn}
Nechť $G=(V,E)$, $H=(U,F)$ jsou grafy. Řekneme, že graf $G$ je
\textbf{izomorfní} s grafem $H$ a značíme\[
G\sim H,\]
jestliže existuje bijekce $\Pi:V\mapsto U$ taková, že platí\[
\left(\forall u,v\in V\right)\left(\{ u,v\}\in E\Leftrightarrow\{\Pi(u),\Pi(v)\}\in F\right).\]
 
\end{defn}
\begin{rem*}
Grafy jsou spolu izomorfní, jestliže jsou stejné až na označení svých
vrcholů. Bijekce $\Pi$ provádí právě ono přeznačení vrcholů grafu
$G$ na vrcholy grafu $H$.
\end{rem*}
\begin{rem}
Na tříprvkové množině jsou 4 navzájem různé neizomorfní grafy. Izomorfismus
grafů je ekvivalence na množině všech grafů o $n$ vrcholech. V jedné
třídě ekvivalence je maximálně $n!$ grafů, neboť tolik je různých
bijekcí (permutací) na dvou $n$-prvkových množinách. Neizomorfních
grafů na $n$ vrcholech je tedy více nebo rovno než\[
\frac{2^{\binom{n}{2}}}{n!},\]
přičemž pro $n\to\infty$ je s užitím Stirlingovy formule%
\footnote{$n!\approx n^{n}\e^{-n}\sqrt{2\pi n}$%
} pro vyjádření faktoriálu\[
\frac{2^{\binom{n}{2}}}{n!}\approx\frac{2^{\frac{n(n-1)}{2}}}{n^{n}e^{-n}\sqrt{2\pi n}}=\frac{2^{\frac{n(n-1)}{2}}}{2^{n\log_{2}n-n\log_{2}e+\frac{1}{2}\log_{2}(2\pi n)}}\to+\infty.\]
 
\end{rem}
\begin{defn}
Nechť $G=(V,E)$ je graf. Potom graf\[
\bar{G}=\left(V,\binom{V}{2}\backslash E\right)\]
nazveme \textbf{doplňkem} (angl. \emph{complement}) grafu $G$. Platí-li
$G\sim\bar{G}$, říkáme, že $G$ je \textbf{samokomplementární} (angl.
\emph{self-complementary}).
\end{defn}
\begin{obs*}
~\\
 
\begin{itemize}
\item Platí $\bar{\bar{G}}=G$
\item Na třech vrcholech neexistuje žádný samokomplementární graf.
\end{itemize}
\end{obs*}
\begin{rem*}
Nechť $G\sim\bar{G}$. Potom musí pro $m=\# E\in\N_{0}$ platit\[
m=\binom{n}{2}-m,\]
z čehož plyne\[
m=\frac{1}{2}\binom{n}{2}=\frac{n(n-1)}{4}\in\N_{0}.\]
Proto pro $n=2$ a $n=3$ samokomplementární graf neexistuje, existuje
však pro $n=4$ a $n=5.$ Jednoduché samokomplementární grafy vidíme
na obrázku \ref{cap:Samokomplement}.%
\begin{figure}
\begin{center}\input{figures1/samokompl.pictex}\end{center}
 
 
\caption{\label{cap:Samokomplement}Samokomplementární grafy}
\end{figure}
 
\end{rem*}
 
 
\begin{rem*}
Existuje-li samokomplementární graf na $n$ vrcholech, potom platí
$n\equiv0$ (mod $4$) nebo $n\equiv1$. Platí i obrácená implikace?
\end{rem*}
 
\subsection{Stupeň vrcholu, skóre}
 
\begin{defn}
\label{def:stupen-vrcholu}Buď $G=(V,E)$ graf, $v\in V$. Číslo\[
d_{G}(v)=\#\left\{ \left.u\in V\right|\{ u,v\}\in E\right\} \]
nazýváme \textbf{stupněm} (angl. \emph{degree}) vrcholu $v$. Je to
počet hran, které vedou z vrcholu $v$. Dále definujeme \textbf{minimální
stupeň} grafu $G$ jako\[
\delta(G)=\min_{v\in V}d_{G}(v),\]
 \textbf{maximální stupeň} grafu $G$ jako\[
\Delta(G)=\max_{v\in V}d_{G}(v)\]
a \textbf{průměrný stupeň} grafu $G$ jako\[
\rho(G)=\frac{1}{n}\sum_{i=1}^{n}d_{G}(v_{i}).\]
 
\end{defn}
\begin{rem*}
Pro každý $v\in V$ platí $0\leq\delta(G)\leq d_{G}(v)\leq\Delta(G)\leq n-1$.
\end{rem*}
\begin{thm}
\label{thm:suma_stupnu}\[
\sum_{v\in V}d_{G}(v)=2\# E.\]
 
\end{thm}
\begin{proof}
Tvrzení je zřejmé. Každá hrana $e=\{ u,v\}$ přispěje jedničkou ke
stupni dvou vrcholů $u,v$.
\end{proof}
\begin{cor*}
Součet stupňů $\sum_{v\in V}d_{G}(v)$ je vždy sudý.
\end{cor*}
\begin{defn}
Posloupnost čísel $(d_{1},d_{2},...,d_{n})$ nazveme \textbf{skóre},
existuje-li graf $G=(V,E)$ na vrcholech $V=\{ v_{1},v_{2},...,v_{n}\}$
takový, že \[
\left(\forall i\in\hat{n}\right)\left(d_{i}=d_{G}(v_{i})\right).\]
 
\end{defn}
\begin{example*}
~\\
 
\begin{itemize}
\item $(1,3,3,4,6,6,6)$ není skóre, protože součet $\sum d_{i}$ je lichý. 
\item $(1,1,3,3,3,3,5,6,8,9)$ není skóre, protože poslední vrchol $v_{10}$
by byl napojen hranou na všechny předchozí, vrchol $v_{9}$ by pak
byl napojen na všechny kromě jednoho. Oba vrcholy $v_{1}$a $v_{2}$
tedy nemohou mít stupeň roven $1$.
\end{itemize}
\end{example*}
\begin{thm}
Nechť $(d_{1},d_{2},...,d_{n})$ je $n$-tice nezáporných celých čísel
taková, že $d_{1}\geq d_{2}\geq...\geq d_{n}$. Potom $(d_{1},d_{2},...,d_{n})$
je skóre, právě když $(d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{n})$
je skóre.
\end{thm}
\begin{rem*}
S pomocí uvedené věty lze o libovolné $n$-tici rozhodnout, zda je
to skóre. Iteraci zastavíme s odpovědí ,,ne{}``, jestliže nám v
průběhu výpočtu vznikne záporné číslo. Dojdeme-li v $p$-té iteraci
až k jedinému číslu $\left(d_{1}^{(p)}\right)$, tak původní $n$-tice
je skóre, právě když $d_{1}^{(p)}=0$.
\end{rem*}
\begin{proof}
$\boxed{{\Leftarrow:}}$
 
Nechť existuje graf se skóre $(d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{n})$.
K tomuto grafu přidáme nový vrchol, který hranami spojíme s prvními
$d_{1}$ vrcholy. Tak získáme graf, který bude mít skóre $(d_{1},d_{2},...,d_{n})$.
 
$\boxed{{\Rightarrow:}}$
 
Mějme graf se skóre $(d_{1},d_{2},...,d_{n})$, chceme zkonstruovat
graf se skóre $(d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{n})$.
Mohou nastat dva případy:
\begin{enumerate}
\item Hrany z vrcholu $v_{1}$ vedou právě do následujících $d_{1}$ vrcholů
$v_{2},v_{3},...,v_{d_{1}+1}$. V tom případě vrchol $v_{1}$ odebereme
a získáme graf se skóre $(d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{n})$.
\item Existuje $i\in\{2,3,...,d_{1}+1\}$ takové, že $\{ v_{1},v_{i}\}\notin E$.
To znamená, že rovněž existuje $j\in\{ d_{1}+2,...,n\}$ takové, že
$\{ v_{1},v_{j}\}\in E$. Pro každé $k\notin\{1,i,j\}$ tak může nastat
právě jeden z případů na následujícím obrázku. Přerušované čáry označují,
že mezi vrcholy nevede hrana. Na existenci hrany mezi vrcholy $v_{1}$
a $v_{k}$ nezáleží, a proto ji v rozlišování jednotlivých případů
neuvažujeme.
\end{enumerate}
\noindent \hfill{}\input{figures1/skore.pictex}\hfill{}
 
Alespoň pro jedno $k$ však musí nastat případ 4. Kdyby totiž nastávaly
pouze případy 1, 2 a 3, přispěl by každý další vrchol $v_{k}$ ke
stupni $d_{j}=d_{G}(v_{j})$ alespoň tolik jako ke stupni $d_{i}=d_{G}(v_{i})$.
Protože však předpokládáme $\{ v_{1},v_{j}\}\in E$ a přitom $\{ v_{1},v_{i}\}\notin E$,
platilo by $d_{i}<d_{j}$, což je spor s uspořádáním čísel $d_{1},...,d_{n}$.
 
Vezměmě tedy $k$ takové, pro nějž nastává případ 4. Vyrobíme nyní
nový graf, jenž vznikne záměnou hran provedenou takto:
 
\noindent \hfill{}\input{figures1/skore_zmena.pictex}\hfill{}
 
Tento nový graf bude mít zřejmě stejné skóre jako graf původní. Liší
se však tím, že z $v_{1}$ vede oproti původnímu grafu více hran do
vrcholů $v_{2},v_{3},...,v_{d_{1}+1}$. Potom buď nastává případ (1),
nebo stále existuje $i\in\{2,3,...,d_{1}+1\}$ takové, že $\{ v_{1},v_{i}\}\notin E$,
takže můžeme úvahu provedenou v případu (2) opakovat.
\end{proof}
\begin{rem*}
~
\begin{itemize}
\item Rozhodovací algoritmus založený na předchozí větě má složitost maximálně
$O(n^{2})$.
\item Podle důkazu implikace $\boxed{{\Leftarrow:}}$ lze snadno pro dané
skóre nalézt odpovídající graf.
\end{itemize}
\end{rem*}
\begin{thm}
Buď $(d_{1},d_{2},...,d_{n})$ $n$-tice nezáporných celých čísel
takových, že $d_{1}\geq d_{2}\geq...\geq d_{n}$. Potom je-li $(d_{1},d_{2},...,d_{n})$
skóre, tak pro každé $i\in\{1,2,...,n\}$ platí\[
\sum_{k=1}^{i}d_{k}\leq i(i-1)+\sum_{k=i+1}^{n}\min\{ i,d_{k}\}.\]
 
\end{thm}
\begin{proof}
Mějme graf $G$ na vrcholech $V=\{1,2,...,n\}$ s daným skóre. Pro
pevné $i\in\hat{n}$ diskutujme, které hrany přispívají do součtu
prvních $i$ stupňů $d_{1},...,d_{i}$ v grafu $G$:
\begin{enumerate}
\item Hrany, které vedou mezi vrcholy $\{1,...,i\}$, přispívají k sumě
$\sum_{k=1}^{i}d_{k}$ dvojkou. Proto maximální součet stupňů dosažený
pouze pomocí těchto hran je $2\binom{i}{2}=i(i-1)$ (viz. věta \ref{thm:suma_stupnu}).
\item Další hrany, které přispívají k dané sumě, vedou mezi vrcholy $u,v$,
kde $u\in\{1,...,i\}$ a $v\in\{ i+1,...,n\}$. Tyto vrcholy přispívají
k sumě jen jedničkou. Přitom z každého vrcholu $v$ z uvedené množiny
nemůže zřejmě vést do prvních $i$ vrcholů více hran, než je $i$,
ale ani více hran, než je $d(v)$.
\end{enumerate}
\end{proof}
\begin{rem*}
Pokud navíc je $\sum_{i=1}^{n}d_{i}$ sudé číslo, platí ve větě ekvivalence.
\end{rem*}
\begin{defn}
Buď $G=(V,E)$ graf. Graf $G'=(V',E')$ takový, že $V'\subset V$
a $E'\subset\left(E\cap\binom{V'}{2}\right)$, nazýváme \textbf{podgrafem}
(angl. \emph{subgraph}) grafu $G$. Jestliže $G'\neq G$, pak se $G'$
nazývá \textbf{vlastním podgrafem} (angl. \emph{proper subgraph})
grafu $G$.
 
Graf $G[V']=\left(V',E\cap\binom{V'}{2}\right)$ se nazývá podgraf
$G$ \textbf{indukovaný} (množinou vrcholů) $V'$. Obecně, jestliže
pro podgraf $G'=(V',E')$ grafu $G$ platí $E'=\left(E\cap\binom{V'}{2}\right)$,
nazýváme $G'$ \textbf{indukovaným podgrafem} (angl. \emph{induced
subgraph}) grafu $G$.
\end{defn}
\begin{rem*}
Je-li $G'$ podgrafem $G$, tak občas též říkáme, že $G$ je \textbf{nadgrafem}
$G'$ (angl. \emph{supergraph}). Pro relaci ,,být podgrafem{}``
používáme množinové označení $G'\subset G$.
\end{rem*}
\begin{defn}
\label{def:specialni-grafy}Zavádíme následující pojmenování a označení
pro tyto speciální typy grafů:
\begin{itemize}
\item \textbf{Úplný} (angl. \emph{complete}) graf na $n$ vrcholech\[
K_{n}=\left(\{1,2,...,n\},\left\{ \left.\{ i,j\}\right|i,j\in\{1,2,...,n\},i\neq j\right\} \right)=\left(\hat{n},\binom{\hat{n}}{2}\right).\]
 
\item \textbf{Cesta} (angl. \emph{path}) délky $n$ na $n+1$ vrcholech\[
P_{n}=\left(\hat{n}\cup\{0\},\left\{ \left.\{ i-1,i\}\right|i\in\hat{n}\right\} \right).\]
 
\item ,,Hvězda{}``\[
S_{n}=\left(\hat{n}\cup\{0\},\left\{ \left.\{0,i\}\right|i\in\hat{n}\right\} \right)\]
 
\item \textbf{Kružnice} (angl. \emph{cycle}) délky $n$\[
C_{n}=\left(\hat{n},\left\{ \left.\{ i,i+1\}\right|i\in\{1,2,...,n-1\}\right\} \cup\left\{ \{1,n\}\right\} \right).\]
 
\end{itemize}
\end{defn}
 
\subsection{Zobecněná definice grafu, adjacenční matice grafu}
 
\begin{defn}
\label{def:zobecneny_graf}Buďte $V,E$ konečné množiny.\\
Buď $\varphi:E\mapsto\binom{V}{2}\cup\binom{V}{1}$. Potom uspořádanou
trojici $G=(V,E,\varphi)$ nazýváme \textbf{graf}.
\begin{itemize}
\item $E$ jsou jen ,,jména{}`` hran.
\item $\varphi$ každé hraně přiřazuje její koncové vrcholy.
\item Připouští se násobné hrany i hrany z vrcholu do sebe sama.%
\begin{figure}
\begin{center}\input{figures1/zobec_graf.pictex}\end{center}
 
 
\caption{Zobecněný graf definovaný takto:$\protect\begin{array}{cc}
V=\{1,2,3,4\} & E=\{ a,b,c,d,e,f\}\protect\\
\varphi(a)=\{1,2\} & \varphi(d)=\{1\}\protect\\
\varphi(b)=\{1,2\} & \varphi(e)=\{1,4\}\protect\\
\varphi(c)=\{1,2\} & \varphi(f)=\{1,3\}\protect\end{array}$}
\end{figure}
 
\end{itemize}
\end{defn}
 
 
\begin{defn}
\textbf{(Zobecněná definice orientovaného grafu)} Buďte $V,A$ konečné
množiny.\\
Buď $\varphi:A\mapsto\binom{V}{2}\cup\left(V\times V\right)$. Potom
uspořádanou trojici $D=(V,A,\varphi)$ nazýváme \textbf{orientovaný
graf} (angl. \emph{directed graph}).
\begin{itemize}
\item tato definice připouští orientované hrany (z $V\times V$) i neorientované
hrany (z $\binom{V}{2}$).
\item hrana z vrcholu $v$ do sebe sama může být reprezentována uspořádanou
dvojicí $(v,v)$.
\end{itemize}
\end{defn}
 
 
\begin{defn}
\label{def:adjacencni-matice}Buď $G=(V,E)$ graf, $n=\# V$. \textbf{Adjacenční
maticí} (angl. \emph{adjacency matrix}) grafu $G$ (maticí sousedností)
rozumíme matici $\vec{A}_{G}\in\{0,1\}^{n,n}$, pro jejíž prvky platí\[
\left(\vec{A}_{G}\right)_{ij}=\begin{cases}
1 & \textrm{pro }\{ v_{i},v_{j}\}\in E\\
0 & \textrm{jinak}\end{cases}\]
 
\end{defn}
\begin{rem}
Adjacenční matice má následující zřejmé vlastnosti:
\begin{itemize}
\item $\vec{A}_{G}$ je symetrická, a tedy diagonalizovatelná, s reálným
spektrem. Pro takovou matici platí $\Tr\vec{A}_{G}=\sum\lambda_{i}$
, kde $\lambda_{i}$ jsou všechna vlastní čísla matice $\vec{A}_{G}$.
Protože ovšem $\left(\forall i\in\hat{n}\right)\left(\left(\vec{A}_{G}\right)_{ii}=0\right)$,
tak $0=\Tr\vec{A}_{G}=\sum\lambda_{i}$.
\item Uvědomíme-li si, jakým způsobem vzniká $(i,j)$-tý prvek matice $\vec{A}_{G}\vec{A}_{G}=\vec{A}_{G}^{2}$,
tak ze symetrie $\vec{A}_{G}$ plyne $\left(\vec{A}_{G}^{2}\right)_{ii}=d_{G}(v_{i})$.
Z toho dále plyne\[
\sum_{i=1}^{n}\lambda_{i}^{2}=\Tr\left(\vec{A}_{G}^{2}\right)=\sum_{i=1}^{n}d_{G}(v_{i})=2\# E.\]
 
\end{itemize}
\end{rem}