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

\setlength{\hoffset}{-3 cm}
\setlength{\voffset}{-4 cm}
\addtolength{\textwidth}{5 cm}
\addtolength{\textheight}{8 cm}

\newcommand{\defi}[1]{{\bf Def } {#1} \\}

\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
4. gyakorlat
}
\end{center}

\large

\defi {\emph{Erősen összefüggő}nek nevezünk egy irányított gráfot, ha
bármely pont\-já\-ból bármely másik pontba vezet irányított út.}

\defi {Egy irányított gráf egy $v$ pontját \emph{forrás}nak nevezzük, ha
$d_{\textrm{be}}(v)=0$; \emph{nyelő}nek, ha $d_{\textrm{ki}}(v)=0$ }

\defi{\emph{Körmérkőzésgráf}nak nevezzük egy teljes gráf egy
irányítását. (Mindenki mindenkivel játszik pontosan egy mérkőzést, az őket
összekötő élet a győztesből a vesztes felé irányítjuk.)}

\begin{enumerate}

\item Legalább hány éle van egy $n$ pontú erősen összefüggő gráfnak?

\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 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 Igaz-e, hogy ha egy körmérkőzés-gráfban nincs forrás (abszolút
győztes) és nincs nyelő (abszolút vesztes), akkor van Hamilton-kör
($n$ pontú körbeverés)? 

\item Bizonyítsuk be, hogy egy élhalmaz akkor és csak akkor
feszítőfa, ha olyan minimális élhalmaz, amely minden vágást
metsz. Bizonyítsuk be, hogy egy élhalmaz akkor és csak akkor
feszítőfa-komplementer, ha olyan minimális élhalmaz, amely minden kört
metsz.

\item Számítsuk ki az alábbi gráfokkal ábrázolt munkafolyamatok legkorábbi 
befejezési időit, és adjuk meg a kritikus utakat!

\includegraphics{sze4pert1.eps}

\input{sze4pert2.epic}

\end{enumerate}
 
\end{document}
