01ZTGA:Kapitola1 2: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Založena nová stránka: %\wikiskriptum{01ZTGA})
 
 
Řádka 1: Řádka 1:
 
%\wikiskriptum{01ZTGA}
 
%\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}

Aktuální verze z 15. 1. 2012, 12:49

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{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}