\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*{Osmá série domácích úkolů\\z diskrétní matematiky}
\subsection*{Deadline: 4. 12. 2020; 23:59:59.99}

U každého příkladu nezapomeňte svá řešení pořádně zdůvodnit. 
\subsection*{Zadání}
Uvažme následující (orientovaný) graf, kde každé hraně je přiřazené nějaké číslo.
\begin{center}
\includegraphics{edgelabels}
\end{center}
\begin{enumerate}
 \item\relax[2b] Spočtěte počet orientovaných cest z~bodu A do bodu B.
 \item\relax[2b] Pokud ona čísla určují délku hrany, najděte nejkratší cestu z~A do B (a dokažte, že je nejkratší).
 \item\relax[2b] Pokud ona čísla určují maximální šířku vozidla, určete, jak široký náklad můžeme přepravit z~bodu A do B. 
 Vyznačte též nějakou cestou, po které lze takový náklad přepravit.
 \item\relax[bonus+2] Uvažme nyní ten samý graf, kde ale zapomeneme na orientaci hran. Ona čísla nyní určují cenu za stavbu silnice mezi koncovými body/městy (v~ milionech euro). Chceme nyní postavit silnice tak, aby se dalo dostat z~každého města do každého. Jaké jsou minimální náklady, za jakých se nám to podaří? Jaké silnice v~tom případě postavíme?
 \item\relax[3body] Buď $G=(V,E)$ konečný (orientovaný) multigraf, kde každá hrana má přiřazenou nějakou délku. Buď $A$ matice $V\times V$, kde na pozici $a_{uv}$ je délka nejkratší hrany z~vrcholu $u$ do $v$ a $+\infty$, pokud žádná hrana z $u$ do $v$ nevede. Dále se dohodněme, že $a_{vv}=0$ pro každý vrchol $v\in V(G)$.
 
 Definujme nyní ``divné násobení'' matic\footnote{Odborně se takovémuto násobení říká \emph{tropické}, protože místo v~tělese $(\R,+,\cdot)$ probíhá v~tzv. \emph{tropickém polookruhu} $(\R,\max,+)$.}, ve kterém postupujeme jako v  normálním násobení matic, jen všechny součiny čísel nahradíme součty a všechny sumy maximem. Označme toto nové násobení matic třeba $\circledast$.
 Matice $D=B\circledast C$ tak bude splňovat $d_{ij}=\max\{b_{ik}+c_{kj}\mid k=1,2,\ldots\}$ (pokud bude definována). Co při této definici násobení značí hodnota prvku $x_{uv}$ v~matici $X=\underbrace{A\circledast A\circledast A\cdots \circledast A}_{k-\text{times}}$?
 
\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}
