\documentclass[a4paper,10pt]{article}
\usepackage[czech]{babel}
\usepackage{amsmath, amsthm, amsfonts, amssymb} %basic mathematical fonts and symbols
\usepackage{graphicx} %inclusion of pictures
\usepackage{fnpct} %proper footnotes spacing after commas and dots
\usepackage{footnotebackref} 		%Footnotes reference back to the original text
\usepackage{hyperref}						%references are clickable
\hypersetup{colorlinks=true, linkcolor=red, urlcolor=blue, citecolor=blue, pdfpagemode=UseNone, pdfstartview=FitH, bookmarksopen=true}
\hypersetup{pdftitle=Discrete Mathematics}
\usepackage[utf8]{inputenc}
\usepackage[inline]{enumitem}

\newcommand{\abs}[1]{\left|#1\right|} % absolute value
\newcommand{\lnorm}[2]{{\left\|#2\right\|_#1}}% an l_p norm
\newcommand{\norm}[1]{\left\|#1\right\|} % a norm
\newcommand{\R}{\mathbb{R}} 	%real numbers
\newcommand{\Z}{\mathbb{Z}} 	%integers
\newcommand{\N}{\mathbb{N}} 	%natural numbers
\newcommand{\Q}{\mathbb{Q}} 	%rational numbers
\newcommand{\C}{\mathbb{C}} 	%complex numbers

%opening
\title{}
\author{}
\usepackage{fullpage}

\begin{document}
\section*{Čtrnáctá série domácích úkolů \\z diskrétní matematiky (závěrečná všehochuť)}
\subsection*{Deadline: 29. 1. 2020; 23:59:59.99}

U každého příkladu nezapomeňte svá řešení pořádně zdůvodnit. 
\subsection*{Zadání}
\begin{enumerate}
\item\relax[2b] Jaká je pravděpodobnost, že náhodný graf na dané $n$-prvkové množině $V$ neobsahuje vrchol stupně $0$? (Předpokláme, že každý z $2^{\binom{n}{2}}$ grafů má stejnou pravděpodobnost býti vybrán.)
\item\relax[3b] Dokažte, že dva grafy $G$ a $H$ jsou izomorfní právě tehdy, pokud existuje permutační matice\footnote{Matice je permutační, pokud je čtvercová a v každém řádku i sloupci má právě jednu jedničku a všechny ostatní čísla jsou nuly.} $P$ taková, že $A_H = PA_GP^T$, kde $A_G$ značí matici sousednosti pro graf $G$, a podobně $A_H$ pro graf $H$.

\item\relax[1b] Nechť $G$ je graf. Víme, že pokud ho chceme obarvit tak, aby sousední vrcholy neměly stejnou barvu, potřebujeme alespoň $k$ barve. Dokažte, že $G$ má alespoň $\binom{k}{2}$ hran.

\item\relax[bonus+5] Buďte $(P,\leq_P)$ a $(Q,\leq_Q)$ částečně uspořádané množiny a $f\colon P\to Q$ a $g\colon Q\to P$ dvě zobrazení taková, že pro všechna $p\in P$ a $q\in Q$ platí \[f(p)\leq_Q q\Leftrightarrow p\leq_P g(Q).\]
Dokažte, že $f$ i $g$ jsou monotonní, tj. splňují $p_1\leq  p_2\Rightarrow f(p_1)\leq f(p_2)$.
\end{enumerate}


\subsection*{Pokyny}
Řešení posílejte na ppatak@seznam.cz s předmětem ``diskretka''.
Řešení mohou být v jakémkoli formátu (v ideálním případě pdf z \LaTeX{u}, ale stačí i naskenované, nafocené pdf, jpeg), 
snažte se, aby byla řešení čitelná.
U bonusových příkladů se Vám body započítavají, 
ale body z bonusového příkladu se nepočítají do celkového maximálního počtu bodů.
Příklady můžete zaslat i opakovaně, počítá se nejlepší dosažení počet bodů.
\end{document}
