01ZTGA:Kapitola1 1

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{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}
%Title: graf.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:20:40 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.250}}} at  0.656 24.276
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  0.656 26.014
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  2.396 26.014
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  2.396 24.276
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  0.656 25.891 to  0.656 24.258
\putrule from  0.656 24.276 to  2.396 24.276
\plot  2.396 24.276  0.656 26.014 /
\putrule from  0.656 26.014 to  2.396 26.014
}%
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  0.159 24.401
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  2.769 24.401
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  0.159 26.264
%
% Fig TEXT object
%
\put{\SetFigFont{9}{10.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  2.769 26.264
\linethickness=0pt
\putrectangle corners at  0.127 26.520 and  2.800 24.134
\endpicture}
 
\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}
%Title: samokompl.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:54:56 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}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  9.286 26.314
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.452 25.480
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.120 25.480
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  9.762 24.528
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.810 24.528
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.191 24.528
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.144 24.528
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.499 25.480
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  5.834 25.480
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.668 26.314
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.405 26.194
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.405 24.765
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  2.976 24.765
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  2.976 26.194
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  0.476 26.194
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  0.476 24.765
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  1.905 24.765
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  1.905 26.194
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  9.286 26.314  8.810 24.528 /
\plot  8.810 24.528 10.120 25.480 /
\putrule from 10.120 25.480 to  8.452 25.480
\plot  8.452 25.480  9.762 24.528 /
\plot  9.762 24.528  9.286 26.314 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  6.668 26.314  5.834 25.480 /
\plot  5.834 25.480  6.191 24.528 /
\putrule from  6.191 24.528 to  7.144 24.528
\plot  7.144 24.528  7.499 25.480 /
\plot  7.499 25.480  6.668 26.314 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  2.976 24.765  4.405 26.194 /
\putrule from  4.405 26.194 to  2.976 26.194
\plot  2.976 26.194  4.405 24.765 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from  0.476 26.194 to  0.476 24.747
\putrule from  0.476 24.765 to  1.923 24.765
\putrule from  1.905 24.765 to  1.905 26.194
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bar{H}$}%
} [lB] at  9.167 23.694
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$H$}%
} [lB] at  6.547 23.696
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bar{G}$}%
} [lB] at  3.571 23.694
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G$}%
} [lB] at  0.953 23.694
\linethickness=0pt
\putrectangle corners at  0.326 26.463 and 10.270 23.495
\endpicture}
\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{}
%Title: skore.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 20:37: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 TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at  3.175 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at  0.794 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at  1.852 26.088
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  1.852 23.178
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at  6.615 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at  4.233 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at  5.292 26.088
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  5.292 23.178
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at 10.054 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at  7.673 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at  8.731 26.088
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  8.731 23.178
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at 13.494 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at 11.113 24.634
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 12.171 26.088
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at 12.171 23.178
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  5.586 25.692
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  4.925 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  6.217 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  5.556 23.840
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  5.556 25.692  6.217 24.765 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1270cm>
{\color[rgb]{0,0,0}\plot  5.556 25.692  4.894 24.765 /
\plot  4.894 24.765  5.556 23.840 /
\plot  5.556 23.840  6.217 24.765 /
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  9.025 25.692
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  8.365 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  9.656 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  8.996 23.840
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  8.996 25.692  9.656 24.765 /
\plot  9.656 24.765  8.996 23.840 /
\plot  8.996 23.840  8.333 24.765 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1270cm>
{\color[rgb]{0,0,0}\plot  8.996 25.692  8.333 24.765 /
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at 12.465 25.692
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at 11.805 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at 13.096 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at 12.435 23.840
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 12.435 25.692 13.096 24.765 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 11.773 24.765 12.435 23.840 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1270cm>
{\color[rgb]{0,0,0}\plot 12.435 25.692 11.773 24.765 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 13.096 24.765 12.435 23.840 /
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  2.146 25.692
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  1.486 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  2.777 24.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.207}}} at  2.117 23.840
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  2.117 25.692  2.777 24.765 /
\plot  2.777 24.765  2.117 23.840 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1270cm>
{\color[rgb]{0,0,0}\plot  2.117 25.692  1.454 24.765 /
\plot  1.454 24.765  2.117 23.840 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at  2.117 22.384
%
% Fig TEXT object
%
\put{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at  5.556 22.384
%
% Fig TEXT object
%
\put{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}%
} [lB] at  8.996 22.384
%
% Fig TEXT object
%
\put{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}%
} [lB] at 12.435 22.384
\linethickness=0pt
\putrectangle corners at  0.762 26.395 and 13.526 22.352
\endpicture}
 
\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{}
%Title: skore_zmena.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:50:48 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.250}}} at  7.497 25.559
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  6.703 24.448
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  8.255 24.448
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  7.461 23.336
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  2.417 25.559
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  1.623 24.448
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  3.175 24.448
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.250}}} at  2.381 23.336
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1270cm>
{\color[rgb]{0,0,0}\plot  6.668 24.448  7.461 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot  7.461 25.559  8.255 24.448 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setsolid
{\color[rgb]{0,0,0}\plot  7.461 25.559  6.668 24.448 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  8.255 24.448  7.461 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  2.381 25.559  3.175 24.448 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  1.587 24.448  2.381 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1270cm>
{\color[rgb]{0,0,0}\plot  2.381 25.559  1.587 24.448 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot  3.175 24.448  2.381 23.336 /
}%
%
% Fig POLYLINE object
%
\linethickness=2pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'161}}})
\setsolid
{\color[rgb]{0,0,0}\putrule from  4.445 24.448 to  5.398 24.448
%
% arrow head
%
\plot  4.890 24.289  5.398 24.448  4.890 24.606 /
%
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at  8.731 24.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at  5.874 24.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at  7.144 26.035
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  7.144 22.543
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at  3.651 24.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at  0.794 24.289
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at  2.064 26.035
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  2.064 22.543
\linethickness=0pt
\putrectangle corners at  0.762 26.397 and  8.763 22.388
\endpicture}
 
\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}
%Title: zobec_graf.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=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  3.689 25.838
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  3.334 24.528
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  1.905 24.289
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  0.953 26.075
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.953 26.075  1.905 24.289 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.953 26.075  3.334 24.528 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.953 26.075  0.948 26.082 /
\plot  0.948 26.082  0.940 26.096 /
\plot  0.940 26.096  0.927 26.120 /
\plot  0.927 26.120  0.906 26.154 /
\plot  0.906 26.154  0.878 26.200 /
\plot  0.878 26.200  0.847 26.251 /
\plot  0.847 26.251  0.809 26.310 /
\plot  0.809 26.310  0.770 26.369 /
\plot  0.770 26.369  0.728 26.429 /
\plot  0.728 26.429  0.684 26.486 /
\plot  0.684 26.486  0.639 26.539 /
\plot  0.639 26.539  0.595 26.585 /
\plot  0.595 26.585  0.548 26.623 /
\plot  0.548 26.623  0.502 26.655 /
\plot  0.502 26.655  0.453 26.674 /
\plot  0.453 26.674  0.404 26.681 /
\plot  0.404 26.681  0.356 26.670 /
\plot  0.356 26.670  0.320 26.649 /
\plot  0.320 26.649  0.286 26.617 /
\plot  0.286 26.617  0.258 26.577 /
\plot  0.258 26.577  0.231 26.535 /
\plot  0.231 26.535  0.210 26.490 /
\plot  0.210 26.490  0.191 26.444 /
\plot  0.191 26.444  0.171 26.397 /
\plot  0.171 26.397  0.157 26.350 /
\plot  0.157 26.350  0.142 26.306 /
\plot  0.142 26.306  0.129 26.259 /
\plot  0.129 26.259  0.119 26.213 /
\plot  0.119 26.213  0.106 26.168 /
\plot  0.106 26.168  0.097 26.122 /
\plot  0.097 26.122  0.087 26.075 /
\plot  0.087 26.075  0.080 26.027 /
\plot  0.080 26.027  0.074 25.978 /
\plot  0.074 25.978  0.070 25.929 /
\putrule from  0.070 25.929 to  0.070 25.880
\plot  0.070 25.880  0.072 25.834 /
\plot  0.072 25.834  0.080 25.789 /
\plot  0.080 25.789  0.095 25.749 /
\plot  0.095 25.749  0.119 25.718 /
\plot  0.119 25.718  0.152 25.694 /
\plot  0.152 25.694  0.195 25.684 /
\putrule from  0.195 25.684 to  0.243 25.684
\plot  0.243 25.684  0.294 25.692 /
\plot  0.294 25.692  0.349 25.707 /
\plot  0.349 25.707  0.404 25.730 /
\plot  0.404 25.730  0.464 25.758 /
\plot  0.464 25.758  0.523 25.789 /
\plot  0.523 25.789  0.584 25.825 /
\plot  0.584 25.825  0.643 25.864 /
\plot  0.643 25.864  0.703 25.902 /
\plot  0.703 25.902  0.758 25.938 /
\plot  0.758 25.938  0.809 25.974 /
\plot  0.809 25.974  0.855 26.005 /
\plot  0.855 26.005  0.891 26.031 /
\plot  0.891 26.031  0.919 26.050 /
\plot  0.919 26.050  0.938 26.065 /
\plot  0.938 26.065  0.948 26.071 /
\plot  0.948 26.071  0.953 26.075 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.953 26.075  0.955 26.077 /
\plot  0.955 26.077  0.959 26.082 /
\plot  0.959 26.082  0.969 26.092 /
\plot  0.969 26.092  0.982 26.105 /
\plot  0.982 26.105  1.001 26.124 /
\plot  1.001 26.124  1.027 26.149 /
\plot  1.027 26.149  1.058 26.181 /
\plot  1.058 26.181  1.096 26.217 /
\plot  1.096 26.217  1.141 26.259 /
\plot  1.141 26.259  1.190 26.306 /
\plot  1.190 26.306  1.242 26.355 /
\plot  1.242 26.355  1.300 26.405 /
\plot  1.300 26.405  1.361 26.458 /
\plot  1.361 26.458  1.425 26.513 /
\plot  1.425 26.513  1.490 26.568 /
\plot  1.490 26.568  1.558 26.621 /
\plot  1.558 26.621  1.628 26.672 /
\plot  1.628 26.672  1.700 26.723 /
\plot  1.700 26.723  1.772 26.772 /
\plot  1.772 26.772  1.846 26.818 /
\plot  1.846 26.818  1.922 26.860 /
\plot  1.922 26.860  2.002 26.899 /
\plot  2.002 26.899  2.083 26.935 /
\plot  2.083 26.935  2.167 26.964 /
\plot  2.167 26.964  2.252 26.992 /
\plot  2.252 26.992  2.343 27.011 /
\plot  2.343 27.011  2.434 27.023 /
\plot  2.434 27.023  2.525 27.030 /
\plot  2.525 27.030  2.618 27.026 /
\plot  2.618 27.026  2.714 27.013 /
\plot  2.714 27.013  2.805 26.990 /
\plot  2.805 26.990  2.889 26.958 /
\plot  2.889 26.958  2.968 26.920 /
\plot  2.968 26.920  3.040 26.877 /
\plot  3.040 26.877  3.105 26.829 /
\plot  3.105 26.829  3.164 26.776 /
\plot  3.164 26.776  3.219 26.721 /
\plot  3.219 26.721  3.270 26.662 /
\plot  3.270 26.662  3.319 26.600 /
\plot  3.319 26.600  3.361 26.535 /
\plot  3.361 26.535  3.404 26.469 /
\plot  3.404 26.469  3.442 26.403 /
\plot  3.442 26.403  3.478 26.336 /
\plot  3.478 26.336  3.512 26.268 /
\plot  3.512 26.268  3.541 26.204 /
\plot  3.541 26.204  3.569 26.141 /
\plot  3.569 26.141  3.594 26.082 /
\plot  3.594 26.082  3.617 26.029 /
\plot  3.617 26.029  3.636 25.980 /
\plot  3.636 25.980  3.651 25.940 /
\plot  3.651 25.940  3.664 25.906 /
\plot  3.664 25.906  3.675 25.878 /
\plot  3.675 25.878  3.681 25.859 /
\plot  3.681 25.859  3.685 25.849 /
\plot  3.685 25.849  3.689 25.840 /
\putrule from  3.689 25.840 to  3.689 25.838
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.953 26.075  0.955 26.077 /
\plot  0.955 26.077  0.961 26.079 /
\plot  0.961 26.079  0.972 26.086 /
\plot  0.972 26.086  0.988 26.094 /
\plot  0.988 26.094  1.012 26.107 /
\plot  1.012 26.107  1.044 26.122 /
\plot  1.044 26.122  1.079 26.143 /
\plot  1.079 26.143  1.124 26.164 /
\plot  1.124 26.164  1.175 26.190 /
\plot  1.175 26.190  1.232 26.217 /
\plot  1.232 26.217  1.291 26.247 /
\plot  1.291 26.247  1.357 26.276 /
\plot  1.357 26.276  1.425 26.306 /
\plot  1.425 26.306  1.494 26.336 /
\plot  1.494 26.336  1.568 26.365 /
\plot  1.568 26.365  1.643 26.395 /
\plot  1.643 26.395  1.719 26.422 /
\plot  1.719 26.422  1.797 26.448 /
\plot  1.797 26.448  1.880 26.471 /
\plot  1.880 26.471  1.962 26.494 /
\plot  1.962 26.494  2.047 26.513 /
\plot  2.047 26.513  2.136 26.530 /
\plot  2.136 26.530  2.229 26.543 /
\plot  2.229 26.543  2.322 26.551 /
\plot  2.322 26.551  2.421 26.558 /
\putrule from  2.421 26.558 to  2.519 26.558
\plot  2.519 26.558  2.618 26.551 /
\plot  2.618 26.551  2.722 26.539 /
\plot  2.722 26.539  2.819 26.520 /
\plot  2.819 26.520  2.908 26.496 /
\plot  2.908 26.496  2.991 26.471 /
\plot  2.991 26.471  3.065 26.439 /
\plot  3.065 26.439  3.133 26.408 /
\plot  3.133 26.408  3.196 26.372 /
\plot  3.196 26.372  3.251 26.333 /
\plot  3.251 26.333  3.304 26.295 /
\plot  3.304 26.295  3.353 26.255 /
\plot  3.353 26.255  3.397 26.213 /
\plot  3.397 26.213  3.440 26.170 /
\plot  3.440 26.170  3.478 26.128 /
\plot  3.478 26.128  3.514 26.086 /
\plot  3.514 26.086  3.545 26.046 /
\plot  3.545 26.046  3.575 26.005 /
\plot  3.575 26.005  3.603 25.969 /
\plot  3.603 25.969  3.624 25.938 /
\plot  3.624 25.938  3.645 25.908 /
\plot  3.645 25.908  3.660 25.885 /
\plot  3.660 25.885  3.670 25.868 /
\plot  3.670 25.868  3.679 25.853 /
\plot  3.679 25.853  3.685 25.845 /
\plot  3.685 25.845  3.687 25.840 /
\plot  3.687 25.840  3.689 25.838 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  0.953 26.075  3.689 25.838 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}e}%
} [lB] at  1.666 24.765
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}f}%
} [lB] at  2.500 25.241
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}c}%
} [lB] at  2.620 26.075
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}b}%
} [lB] at  2.500 26.670
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}a}%
} [lB] at  2.261 27.146
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}d}%
} [lB] at  0.119 25.241
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}%
} [lB] at  2.024 23.575
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}%
} [lB] at  3.452 23.813
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at  3.929 25.123
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at  0.713 25.480
\linethickness=0pt
\putrectangle corners at  0.023 27.741 and  3.960 23.544
\endpicture}
\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}