\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{graphics}

\usepackage{fullpage}
%\addtolength{\textheight}{2 cm}


\begin{document}

\begin{center}
{\Large \bf Számítástudomány alapjai 2003/2004 tavasz\\
7. gyakorlat: Irányított gráfok, legrövidebb utak, folyamproblémák}
\end{center}

\begin{enumerate}

\item Bizonyítsuk be, hogy ha egy irányított gráfban nincs irányított
kör, akkor van forrás és nyelő.

\item Hány olyan irányítása lehet az $n$ pontú teljes gráfnak, amiben 
nincs irányított kör?

\item Igazoljuk, hogy egy körmérkőzés-gráfban van Hamilton-út
($n$ hosszú irányított út)? 

\item Bizonyítsuk be, hogy minden körmérkőzés-eredmény esetén van
olyan csapat, amely minden más csapatot vagy legyőzött vagy legyőzte annak
egy legyőzőjét.


\item Határozzuk meg a Dijkstra algoritmussal a legrövidebb utat $s$
  és $t$ között és mutassuk meg az algoritmust lépésről lépésre az
alábbi két gráfban.

\begin{figure}[h!]
\begin{center}
\includegraphics{sza07ut1.eps}
\hskip 2cm
\includegraphics{sza07ut2.eps}
\end{center}
\end{figure}

\item Mekkora a legrövidebb irányított út hossza $A$-ból $E$-be? És az
  összes pontpár között?
\begin{figure}[h!]
\begin{center}
\includegraphics{sza07ut3.eps}
\end{center}
\end{figure}

\item Oldjuk meg a következő folyamproblémákat!
\begin{figure}[h!]
\scalebox{0.75}{\includegraphics{sza07foly1.eps}}
\scalebox{0.75}{\includegraphics{sza07foly2.eps}}
%\scalebox{0.75}{\includegraphics{sza07foly3.eps}}
\end{figure}

\end{enumerate}
 
\end{document}


