01ZTGA:Kapitola1 2

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.
ZIP			Kompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součást	akce		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{Souvislost}
 
\begin{defn}
Buď $G=(V,E)$ graf. Posloupnost vrcholů $v_{0},v_{1},...,v_{k}$
nazýváme \textbf{sledem} (angl. \emph{walk}) délky $k$, jestliže
platí\[
\left(\forall i\in\hat{k}\right)\left(\{ v_{i-1},v_{i}\}\in E\right).\]
Sled $v_{0},v_{1},...,v_{k}$ nazveme \textbf{cestou} (angl. \emph{path})
délky $k$, pokud navíc \[
\left(\forall i,j\in\{0,1,2...,k\}\right)\left(i\neq j\Rightarrow v_{i-1}\neq v_{i}\right).\]
Sled $v_{0},v_{1},...,v_{k}$, pro který platí $v_{0}=v_{k}$, nazýváme
\textbf{cyklem} (angl. \emph{closed path}) délky $k$. Cyklus $v_{0},v_{1},...,v_{k}$
nazveme \textbf{kružnicí} (angl. \emph{cycle} (\textbf{!})) délky
$k$, pokud \[
\left(\forall i,j\in\{0,1,2...,k-1\}\right)\left(i\neq j\Rightarrow v_{i-1}\neq v_{i}\right).\]
 
\end{defn}
 
 
\begin{defn}
Buď $G=(V,E)$ graf, $u,v\in V$. Řekneme, že vrcholy $u$ a $v$
\textbf{jsou spojeny} (angl. \emph{linked}) v $G$, existuje-li sled
v $G$ s počátečním vrcholem $u$ a koncovým vrcholem $v$, tj. sled\[
u=v_{0},v_{1},...,v_{k-1},v_{k}=v.\]
 
\end{defn}
\begin{rem*}
Relace ,,být spojen{}`` je ekvivalence na množině vrcholů $V$.
Přitom každý vrchol je spojen sám se sebou sledem délky $0$.
\end{rem*}
\begin{defn}
Třídy ekvivalence podle uvedené relace nazýváme \textbf{komponenty}
(angl. \emph{component}) grafu $G$. Jejich počet značíme $c(G)$.
Jestliže $c(G)=1$, říkáme, že graf $G$ je \textbf{souvislý} (angl.
\emph{connected}).
\end{defn}
\begin{rem*}
Graf $G$ je souvislý, právě když mezi dvěma libovolnými vrcholy existuje
sled.
\end{rem*}
\begin{example*}
Z $8$ grafů na $3$ vrcholech jsou $4$ souvislé. Přitom pro $\# V=3$
platí, že $G$ je souvislý, právě když $\bar{G}$ není souvislý.
\end{example*}
\begin{rem}
Platí: $G$ není souvislý $\Rightarrow$ $\bar{G}$ je souvislý. Opačná
implikace neplatí.
\end{rem}
\begin{proof}
Množinu vrcholů grafu $G$ rozdělíme na jednu komponentu $V_{1}\subset V$
a zbytek $V_{2}\subset V$. Potom mezi těmito dvěma podmnožinami neexistují
žádné hrany. Naopak v doplňku grafu $G$ existují hrany mezi libovolným
$u\in V_{1}$ a $v\in V_{2}$. Proto mezi libovolnými dvěma vrcholy
existuje sled, a to maximálně délky $2$.
 
Příkladem vyvracejícím platnost opačné implikace jsou grafy $H$ a
$\bar{H}$ na obrázku \ref{cap:Samokomplement}.
\end{proof}
 
\subsection{Počet souvislých grafů na $n$ vrcholech}
 
Označme $s_{n}$ počet různých souvislých grafů na $n$ vrcholech.
 
\begin{example*}
Obrázek \ref{cap:Souvisle} ukazuje všechny typy souvislých grafů
na $4$ vrcholech, přičemž čísla pod jednotlivými grafy udávají počet
izomorfních grafů stejného typu. I když to není pro výklad důležité,
ukážeme pro úplnost, jakým způsobem lze na uvedená čísla přijít (grafy
okomentujeme zleva doprava):
\begin{enumerate}
\item Jasné.
\item Chybí jedna hrana. Možností, jak z úplného grafu odebrat hranu, je
zjevně $6$.
\item Dvě různé dvojice nejsou spojeny hranou. První dvojici vybereme $\binom{4}{2}=6$
způsoby, druhá je již jednoznačně dána. Pořadí výběru dvojic však
nehraje roli, proto je počet souvislých grafů tohoto typu roven $\frac{6}{2}=3$.
\item Z jednoho vrcholu (,,zdroje{}``) nevedou dvě hrany (do dvou vrcholů
,,cílů{}``). Zdroj lze vybrat $4$ způsoby, cíle lze vybrat $\binom{3}{2}=3$
způsoby.
\item Prostřední hrana (mezi vrcholy \textbf{a},\textbf{b}) lze vybrat $6$
způsoby, hrany do zbylé dvojice vrcholů lze zvolit $2$ způsoby.
\item Jeden vrchol je spojen se třemi ostatními. Tento vrchol lze vybrat
$4$ způsoby.
\end{enumerate}
Celkem máme na $4$ vrcholech\[
s_{4}=1+6+3+12+12+4=38\]
souvislých grafů. Jak snadno spočítat $s_{n}$ pro libovolné $n$
ukazuje následující věta.%
\begin{figure}
\begin{center}
%Title: souvisle_grafy.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 21:01:36 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.148}}} at  1.484 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  0.516 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at 10.185 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at 10.185 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at 11.153 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at 11.153 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  9.218 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  9.218 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  8.253 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  8.253 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  6.318 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  6.318 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  7.286 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  7.286 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  5.351 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  5.351 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  4.384 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  4.384 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  2.451 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  2.451 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  3.416 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  3.416 25.597
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  1.484 24.587
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.148}}} at  0.516 24.587
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 11.153 25.597 to 10.185 25.597
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.185 24.587 to 10.185 25.597
\plot 10.185 25.597 11.153 24.587 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  8.253 24.587 to  8.253 25.614
\putrule from  8.253 25.597 to  9.236 25.597
\putrule from  9.218 25.597 to  9.218 24.587
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  7.286 24.587 to  6.301 24.587
\putrule from  6.318 24.587 to  6.318 25.614
\putrule from  6.318 25.597 to  7.286 25.597
\plot  7.286 25.597  6.318 24.587 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  4.384 25.597 to  4.384 24.570
\putrule from  4.384 24.587 to  5.369 24.587
\putrule from  5.351 24.587 to  5.351 25.614
\putrule from  5.351 25.597 to  4.366 25.597
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  2.451 25.597 to  2.451 24.570
\putrule from  2.451 24.587 to  3.434 24.587
\putrule from  3.416 24.587 to  3.416 25.614
\putrule from  3.416 25.597 to  2.451 25.597
\plot  2.451 25.597  3.416 24.587 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.516 24.587  1.484 25.597 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  0.516 25.597 to  0.516 24.570
\putrule from  0.516 24.587 to  1.501 24.587
\putrule from  1.484 24.587 to  1.484 25.614
\putrule from  1.484 25.597 to  0.516 25.597
\plot  0.516 25.597  1.484 24.587 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4x}%
} [lB] at 10.530 23.660
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}12x}%
} [lB] at  8.528 23.660
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}12x}%
} [lB] at  6.593 23.660
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3x}%
} [lB] at  4.729 23.660
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}6x}%
} [lB] at  2.796 23.660
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1x}%
} [lB] at  0.861 23.660
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at 11.377 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  9.864 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  9.864 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at 11.377 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  9.445 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  7.929 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  7.929 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  9.445 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  7.510 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  5.997 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  5.997 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  7.510 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  5.575 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  4.062 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  4.062 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  5.575 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  3.643 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  2.127 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  2.127 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  3.643 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  1.708 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  0.195 24.329
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  0.195 25.648
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  1.708 25.648
\linethickness=0pt
\putrectangle corners at  0.163 26.067 and 11.409 23.628
\endpicture}
 
\end{center}
 
 
\caption{\label{cap:Souvisle}Souvislé grafy na $4$ vrcholech}
\end{figure}
 
\end{example*}
\begin{thm}
Buď $s_{n}$ počet souvislých grafů na $n$ vrcholech. Potom platí\[
n\cdot2^{\binom{n}{2}}=\sum_{k=1}^{n}\binom{n}{k}ks_{k}2^{\binom{n-k}{2}}.\]
 
\end{thm}
\begin{proof}
Uvedenou rovnost dokážeme zajímavou úvahou. Vyjádříme počet všech
uspořádaných dvojic $(G,x)$ kde $G$ je graf na $n$ vrcholech a
$x$ je jeden z vrcholů tohoto grafu, a to dvěma způsoby.
\begin{enumerate}
\item Počet všech grafů je $2^{\binom{n}{2}}$, v každém z nich lze vrchol
$x$ zvolit $n$ způsoby, uvedených dvojic je tedy $P=n\cdot2^{\binom{n}{2}}$.
\item Zvolme pevně $k\in\hat{n}$. Počet dvojic $(G,x)$, kde $x$ se nachází
v komponentě grafu $G$, která má $k$ vrcholů, je \[
p_{k}=\binom{n}{k}ks_{k}2^{\binom{n-k}{2}},\]
protože:
 
\begin{enumerate}
\item $\binom{n}{k}$ způsoby lze vybrat $k$ vrcholů z $n$,
\item $k$ způsoby lze z vybraných vrcholů zvolit vrchol $x$,
\item $s_{k}$ je počet různých komponent (souvislých podgrafů), které lze
na vybraných $k$ vr\-cholech vytvořit
\item a $2^{\binom{n-k}{2}}$ je počet všech grafů (na $n-k$ vrcholech),
které mohou být vytvořeny na vrcholech, které jsme nevybrali.
\end{enumerate}
\end{enumerate}
Protože pro pro každou dvojici $(G,x)$ se $x$ zřejmě nachází v komponentě
o počtu vrcholů alespoň $1$ a nejvýše $n$, platí\[
n\cdot2^{\binom{n}{2}}=P=\sum_{k=1}^{n}p_{k}.\]
 
\end{proof}
\begin{rem*}
Po vydělení $n$ přejde rovnost na tvar\[
2^{\binom{n}{2}}=\sum_{k=1}^{n}\binom{n-1}{k-1}s_{k}2^{\binom{n-k}{2}}.\]
 
\end{rem*}
\begin{example*}
Protože už víme, že \[
s_{1}=1,s_{2}=1,s_{3}=4,\]
lze dosazením do rekurentního vzorce pro $n=4$ získat postupně\begin{eqnarray*}
2^{\binom{4}{2}} & = & \sum_{k=1}^{4}\binom{3}{k-1}s_{k}2^{\binom{4-k}{2}}\\
64 & = & 8+6+12+s_{4}\\
38 & = & s_{4}\end{eqnarray*}
Je vidět, že jsme se v našich úvahách předvedených v předchozím příkladu
nespletli.
\end{example*}
 
\subsection{Adjacenční matice souvislého grafu}
 
\begin{thm}
\label{thm:adjac-matice-pocet-sledu}Buď $\vec{A}_{G}$ adjacenční
matice grafu $G$, nechť $k\in\hat{n}$. Potom prvek $\left(\vec{A}_{G}^{k}\right)_{ij}$
je roven počtu sledů délky $k$ z vrcholu $v_{i}$ do vrcholu $v_{j}$.
\end{thm}
\begin{proof}
Tvrzení snadno dokážeme indukcí podle $k$:
\begin{itemize}
\item pro $k=1$: Podle definice platí \[
\left(\vec{A}_{G}\right)_{ij}=\begin{cases}
1 & \textrm{pro }\{ v_{i},v_{j}\}\in E\\
0 & \textrm{jinak},\end{cases}\]
což zjevně představuje počet sledů délky $1$ (což jsou přímo hrany)
z $v_{i}$ do $v_{j}$.
\item indukční krok $k\to k+1$: Platí\[
\left(\vec{A}_{G}^{k+1}\right)_{ij}=\sum_{l=1}^{n}\left(\vec{A}_{G}^{k}\right)_{il}\left(\vec{A}_{G}\right)_{lj}=\sum_{\begin{array}{c}
{\scriptstyle l=1}\\
{\scriptstyle \{ v_{l},v_{j}\}\in E}\end{array}}^{n}\underbrace{\left(\vec{A}_{G}^{k}\right)_{il}}_{\textrm{(*)}}.\]
$(*)$ představuje počet sledů délky $k$ z $v_{i}$ do $v_{l}$.
Sčítá se však pouze přes takové vrcholy $v_{l}$, z nichž vede hrana
do vrcholu $v_{j}$. Proto $(*)$ rovněž představuje počet sledů délky
$k+1$ z $v_{i}$ do $v_{j}$ takových, že předposledním vrcholem
v sledu je $v_{l}$. Součtem přes všechny takové $v_{l}$ dostaneme
celkový počet sledů délky $k+1$ z $v_{i}$ do $v_{j}$.
\end{itemize}
\end{proof}
\begin{cor*}
\label{cor:adjac-souvisly}Nechť $\vec{A}_{G}$ je adjacenční matice
grafu $G=(V,E),$$n=\# V$. Potom $G$ je souvislý právě tehdy, když\[
\sum_{k=0}^{n-1}\vec{A}_{G}^{k}>0,\]
tj. právě když všechny prvky uvedené matice jsou kladné.
\end{cor*}
\begin{proof}
Je zřejmé, že mezi dvěma různými vrcholy existuje sled, právě když
mezi nimi existuje cesta. (Ze sledu obsahujícího vícekrát stejný vrchol
lze odstranit všechny úseky, které leží mezi dvěma výskyty tohoto
vrcholu ve sledu, čímž nakonec získáme cestu.) Každá cesta v grafu
na $n$ vrcholech má délku maximálně $n-1$.
 
$\boxed{{\Rightarrow:}}$
 
$G$ je souvislý $\Rightarrow$ pro $\forall i,j\in\hat{n}$, $i\neq j$,
existuje cesta (a tedy i sled) z $v_{i}$ do $v_{j}$ nějaké délky
$k\leq n-1$. $\Rightarrow$$\left(\vec{A}_{G}^{k}\right)_{ij}>0$
$\Rightarrow$ $\left(\sum_{k=0}^{n-1}\vec{A}_{G}^{k}\right)_{ij}>0$.
Každý prvek uvedené matice je tedy kladný.
 
$\boxed{{\Leftarrow:}}$
 
$\forall i,j\in\hat{n}$$\left(\sum_{k=0}^{n-1}\vec{A}_{G}^{k}\right)_{ij}>0$.
$\Rightarrow$ $\exists k\in\{1,...,n-1\}$ tak, že $\left(\vec{A}_{G}^{k}\right)_{ij}>0$
$\Rightarrow$ existuje sled (délky $k$) z $v_{i}$ do $v_{j}$ $\Rightarrow$$G$
je souvislý.
\end{proof}