\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\addtolength\textwidth{4cm}
\addtolength\hoffset{-2.5cm}
\addtolength\textheight{4.5cm}
\setlength\topmargin{-2.5cm}

\usepackage{amssymb}
\usepackage{wasysym}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
6. gyakorlat, 2005. március 25.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{10mm}
\textbf{\LARGE Folyamok}
\end{center}

\vspace*{5mm}

\begin{enumerate}

\setcounter{enumi}{61}

\item Adjuk meg az alábbi hálózatokban a maximális folyamot!
\vspace*{7.5cm}

\item Osszunk szét három $1$-es, három $2$-es és három $3$-as kapacitást az
alábbi gráf élein úgy, hogy a maximális folyam a lehető
\begin{enumerate}
\item legnagyobb
\item legkisebb
\end{enumerate}
legyen.
\vspace*{1.2cm}

\item
\begin{enumerate}
\item Igaz-e, hogy ha egy irányított gráfban minden él kapacitása páros,
akkor létezik olyan maximális folyam, amelynek értéke minden élen páros?
\item Ugyanez páros helyett mindenütt páratlannal.
\end{enumerate}

\item Egy kisváros úthálózata csupa egyirányú utcából áll. A polgármester
minden hétköznap reggel autóval megy otthonról a városházára. A fejébe veszi,
hogy úgy szeretné ezt megtenni, hogy minden utcán egy hét alatt legfeljebb
egyszer menjen végig (a hazafelé utak nem számítanak).
\begin{enumerate}
\item Adjunk meg olyan algoritmust, amely a kisváros térképe alapján eldönti,
hogy ez megtehető-e!
\item Mi a helyzet, ha vannak kétirányú utcák is?
\end{enumerate}

\item Legyenek egy irányított gráf pontjai az $n \in \mathbb{Z^+}$
hosszú 0–1 vektorok. Az $a$ csúcsból akkor mutasson a $b$ csúcsba
él, ha $a$-ban kevesebb 1-es van, mint $b$-ben. Egy ilyen élre
kapacitásként írjuk rá $a$-ban lévő egyesek száma és a $b$-ben
lévő egyesek száma közti különbséget. Legyesn $s=(0,0,\dots,0)$ és
$t=(1,1,\dots,1)$. Jelölje $F_n$ a maximális folyam nagyságát.
Számoljuk ki:
\begin{enumerate}
\item $F_3$ értékét! \item $F_n$ értékét tetszőleges $n \in
\mathbb{Z^+}$-ra!
\end{enumerate}

\item Adott egy város, ahol fiúk és lányok élnek, néhányan
közülük barátságban vannak, ezek köthetnek házasságot. Továbbá a
városban vannak közvetítő irodák is, és a fiúk (esetleg több)
közvetítőhöz is beadták papírjaikat. Házasságot csak
házasságközvetítő szervezhet, de egy közvetítő legfeljebb $m$-et.
Mutassunk algoritmust, melynek segítségével meghatározható a
városban köthető legtöbb házasság.
%(Segítség: készítsünk egy
%gráfot, melyben a barátságok és a ``melyik fiú hova adta be a
%papírjait'' kapcsolat is ábrázolható. Utána fogalmazzuk át a
%feladatot folyamproblémává.)


\end{enumerate}

\end{document}
