\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}
\usepackage{amsmath}
\usepackage{graphics}
\addtolength{\textwidth}{4.5cm}
\addtolength{\oddsidemargin}{-2.5cm}
\addtolength{\topmargin}{-2.5cm}
\addtolength{\textheight}{4.5cm}
\pagestyle{empty}
\begin{document}
\begin{center}
\large{Bevezetés a számításelméletbe 1. gyakorlat\\
10. feladatsor (2002. ápr. 26.)}
\end{center}
\vspace{.5cm}
\begin{enumerate}
\item Van-e olyan egyszerű gráf, melyben a pontok foka rendre
\[
\begin{array}{ll}
    \left(a\right)\;1,2,2,3,3,3\hspace{5cm}&
    \left(b\right)\;1,1,2,2,3,4,4\hspace{5cm}\\
    \left(c\right)\;2,3,3,4,5,6,7&
    \left(d\right)\;1,3,3,4,5,6,6\\
    \left(e\right)\;5,5,5,6,6,6,7,7,7&
\end{array}
\]

\item
\begin{enumerate}
\item
A hét törpe minden este más sorrendben szerene sorban állni, amikor
Hófehérke a vacsorát osztja. Hány egymás utáni napon tehetik ezt meg?
\item
Hány hatra végződő néggyel osztható ötjegyű szám van?
\item
Egy 12 fős társaságot egy szálloda két háromágyas és három kétágyas
szobájában kell elszállásolni. Hány különböző szobabeosztás lehetséges,
ha az azonos számú ágyat tartalmazó szobákat nem különböztetjük meg
egymástól? (Vizsga, 1999. jan.)
\item
Hány olyan különböző lottószelvényt lehet kitölteni, hogy mindegyik
pontosan három találatos legyen? (Vizsga, 2001. jan.)
\end{enumerate}

\item Vannak-e izomorfak az alábbi gráfok között? \rule[-3mm]{0mm}{10mm}\\
\raisebox{1.3cm}{\hbox{$\left.a\right)$\ }}
\resizebox*{!}{3cm}{\includegraphics{abrak/hetszog_negyregularis_1.eps}}
\hspace{1.5cm} \raisebox{1.3cm}{\hbox{$\left. b\right)$\ }}
\resizebox*{!}{3cm}{\includegraphics{abrak/hetszog_negyregularis_2.eps}}
\hspace{1.5cm} \raisebox{1.3cm}{\hbox{$\left. c\right)$\ }}
\resizebox*{!}{3cm}{\includegraphics{abrak/hetszog_negyregularis_3.eps}}

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

\item Egy $G$ gráf pontjai legyenek egy kocka csúcsai. Két csúcs pontosan
akkor
legyen összekötve $G$-ben, ha a kockában él mentén szomszédosak. Az alábbiak
köz
ül
melyek izomorfak $G$-vel?\rule[-3mm]{0mm}{5mm}\\ \rule{.5cm}{0cm}
\raisebox{.8cm}{\resizebox*{!}{1.4cm}{\includegraphics{abrak/kockaizomorfia_1.eps}}}
\hspace{2cm}
\resizebox*{!}{3cm}{\includegraphics{abrak/kockaizomorfia_2.eps}}\hspace{2cm}
\resizebox*{!}{3cm}{\includegraphics{abrak/kockaizomorfia_3.eps}}

\item
\begin{enumerate}
\item
Egy gimnáziumban 16 osztály van, az osztálylétszám mindenhol 30.
Mindegyik osztályt háromtagú küldöttség képviseli a diákbizottságban.
Hányféle lehet a diákbizottság összetétele?
\item
Tíz gyerek hányféleképpen állítható úgy sorba, hogy Jancsi és Juliska
egymás mellett álljanak? (ZH. 2000. dec.)
\item
Hányféleképpen ültethető le egy harminc fős társaság 5 darab, egyenként
hatfős asztalhoz, ha két ültetést pontosan akkor tekintünk azonosnak, ha
minden résztvevőnek ugyanaz a bal és a jobb oldali szomszédja? (Vizsga,
2000. jan.)
\item
Tizenöt vívóból hányféleképpen alkothatunk három négyfős csapatot, ha
egy személy több csapatban is szerepelhet? (Vizsga, 1999. jan.)
\end{enumerate}

\item Határozd meg az összes olyan - páronként nem izomorf - egyszerű gráfot,
melyre
\[ \begin{array}{ll}
    \left(a\right)\;n=4,e=5\hspace{5cm}&
    \left(b\right)\;n=5,e=3\hspace{5cm}\\
    \left(c\right)\;n=5,e=7&
    \left(d\right)\;n=5,e=8
\end{array}\]
\noindent $n$ a pontok számát, $e$ az élek számát jelöli.

\item Egy $n$ pontú egyszerű gráfban minden pont foka legalább
$\displaystyle\frac{n}2$. Bizonyítsd be, hogy a gráf összefüggő!

\end{enumerate}
\end{document}
