\documentclass[a4paper,11pt]{article}
\usepackage[latin2]{inputenc}
\usepackage{graphics}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.2cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
2. feladatsor (2002. szept. 19.)}
\end{center}
\ \\
\begin{enumerate}
\item Vannak-e izomorfak az alábbi gráfok között? \rule[-3mm]{0mm}{10mm}\\
\raisebox{1.3cm}{\hbox{$\left(\textup{a}\right)$\ }}
\resizebox*{!}{3cm}{\includegraphics{abrak/hetszog_negyregularis_1.eps}}
\hspace{1.4cm} \raisebox{1.3cm}{\hbox{$\left(\textup{b}\right)$\
}}
\resizebox*{!}{3cm}{\includegraphics{abrak/hetszog_negyregularis_2.eps}}
\hspace{1.4cm} \raisebox{1.3cm}{\hbox{$\left(\textup{c}\right)$\
}}
\resizebox*{!}{3cm}{\includegraphics{abrak/hetszog_negyregularis_3.eps}}

\item Legyen a $G$ egyszerű gráfban minden pont foka legalább $k$.
Mutassuk meg, hogy $G$-ben van egy legalább $k$ hosszúságú út!

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

\item Melyik fa Prüfer-kódja a 447741 számsorozat?

\item Egy $F$ fa Prüfer-kódja csupa különböző számokból áll.
Hogyan jellemezhetjük $F$-et?

\item
\begin{enumerate}
\item Egy $n$ pontú fában legfeljebb hány két élből álló út
található? (Vizsga, 1999. máj.)

\item Mutass példát ilyen fára!
\end{enumerate}

\item Bizonyítsuk be, hogy egy $n$ pontú fában a másodfokú pontok
száma nem lehet pontosan $n-3\;$! (ZH, 2000. máj.)

\item Egy a koordinátarendszerben elhelyezett kocka éleit a
következőképpen súlyozzuk meg: az $x$ tengellyel párhuzamos élek
súlya 1, az $y$ tengellyel párhuzamosaké 2, a $z$ tengellyel
párhuzamo\-saké pedig 3. Hányféleképpen választhatunk ki egy
minimális súlyú feszítőfát ebből a súlyozott gráfból? (Pótzh,
1999. máj.)

\item Egy teljes gráf ponthalmaza
$\{x_1,x_2,...,x_s,y_1,y_2,...,y_t\}$. Az $\left(x_i,x_j\right)$
élek költsége (súlya) 1 Ft, az $\left(y_i,y_j\right)$ éleké 2 Ft,
az $\left(x_i,y_j\right)$ éleké pedig 3 Ft. Mennyibe kerül a
legolcsóbb feszítőfa? (ZH, 2000. márc.)

\item Hány olyan fa adható meg az $1,2,...,100$ csúcsokon, melynek
van olyan éle, amit elhagya a maradék gráf két komponensének
pontjai rendre az $1,2,...,50$ ill. az $51,52,...,100$ csúcsok?
\end{enumerate}
\end{document}
