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

\usepackage{amsmath}
\usepackage{amssymb}

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


\begin{document}
\begin{center}
{\Large \bf Számítástudomány alapjai 2003/2004 tavasz\\
Gyakorlás}
\end{center}

\begin{enumerate}


\item Van-e olyan 5, illetve 6 pontú (egyszerű) gráf, amelyre $G$
izomorf $\overline G$-vel.

\item Rajzoljuk fel az összes 3, 4 ill. 5 pontú fát! (Az izomorfakat
csak egyszer!)

\item Bizonyítsuk be, hogy ha egy $2n$ csúcsú egyszerű gráf minden
pontjának foka legalább $n$, akkor a gráf összefüggő.

\item Van-e olyan (legalább két pontú egyszerű) gráf, amiben minden pont foka
különböző?

\item Hány három pontú egyszerű irányított gráf van? (Oda-vissza élek
megengedettek.)

\item Igazoljuk, hogy egy fának nem lehet két különböző teljes párosítása.

\item Legyen $G$ teljes gráf, amelynek csúcsai az 1, 2,\dots 100 számok.
Egy él súlya a végpontjainak összege. Hány minimális súlyú feszítőfája 
van $G$-nek?


%%%%%%%%


\item Készítsünk olyan algoritmust, amely egy (élsúlyok nélküli) gráfban
  meghatározza, hányféle legrövidebb út van két adott pont között!


\item Adjunk polinom rendű algoritmust, amely meghatározza egy gráf
  legrövidebb körének (köreinek) hosszát!



\end{enumerate}
 
\end{document}

