\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-2cm}
\addtolength\textwidth{3.8cm}
\addtolength\hoffset{0cm}
\addtolength\textheight{5.5cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe I.}
\\\vspace*{1mm}
11. gyakorlat, 2005. november 28.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Gráfok – Bevezetés}
\end{center}

\vspace*{2mm}

\begin{enumerate}
\setcounter{enumi}{119}

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

\item Van-e olyan egyszerű gráf, amelyben a pontok foka rendre
\begin{enumerate}
\item 1, 2, 2, 3, 3, 3;
\item 1, 1, 2, 2, 3, 4, 4;
\item 5, 5, 5, 6, 6, 6, 7, 7, 7;
\item 1, 2, 2, 3, 4, 4, 5, 6, 6;
\item 1, 1, 3, 3, 3, 3, 5, 6, 8, 9;
\item 2, 3, 3, 4, 5, 6, 7\,?
\end{enumerate}

\item Igazoljuk, hogy tetszőleges gráfban a páratlan fokú pontok száma páros.

\item Hány olyan egyszerű gráf van, melynek fokszámai: 2,3,3,4,6,6,6?

\item Milyen komponensekből állhat egy gráf, ha minden pontjának a foka
legfeljebb 2?

\item Bizonyítsuk be, hogy minden fában van olyan pont, amit az összes
leghosszabb út tartalmaz.

%%%\item Jellemezzük azon gráfokat, melyekben minden kör páratlan hosszúságú.

\item Hány 3 hosszú kör található abban a gráfban, amelyet az $n$ szögpontú
$K_n$ teljes gráfból kapunk, ha egy élét elhagyjuk?

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

\item Hány olyan, páronként nem izomorf 5 pontú és 8 élű egyszerű gráf
létezik, melyben pontosan két darab harmadfokú pont van?

\item Hány páronként nem izomorf 4 pontú és 3 élű egyszerű irányított gráf
létezik?

\item Hány olyan páronként nem izomorf 6 pontú összefüggő egyszer gráf
létezik, melyben két másodfokú és négy harmadfokú pont van?

\item Egy gráf izomorf a komplementerével. Mutassuk meg, hogy összefüggő.

\item Rajzoljunk a komplementerével izomorf 5, ill. 6 pontú gráfot.

\item Egy négyreguláris (minden csúcs fokszáma 4) összefüggő gráfból
töröljük egy fa éleit. Bizonyítsuk be, hogy a maradék legalább két kört
tartalmaz.

\item Rajzoljuk le azt a gráfot, melynek pontjai a 4 hosszú nullákból és
egyesekbl álló sorozatok, és két csúcs akkor van éllel összekötve, ha egyik a
másikból egy ``forgatással'' megkapható, azaz ha az egyik a $(b_1, b_2, b_3,
b_4)$, akkor a másik a $(b_2, b_3, b_4, b_1)$ sorozathoz tartozó pont.

\item Az előre megszámozott (címkézett) $n$ darab pont közé hányféleképp
húzhatunk be éleket úgy, hogy egyszerű gráfhoz jussunk?

\item Hány különböző olyan körmentes gráf létezik $n$ címkézett ponton,
amelyben az élek száma vala\-milyen $n-1$-nél kisebb fix $k$ szám, és amiben
pontosan $n-k-1$ izolált pont van?

\item Hány különböző fa adható meg $n$ ponton?

\item Rajzoljuk le a 447741 Prüfer-kódú fát.

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

\item Válasszuk meg az $x$ értékét úgy, hogy az alábbi sorozat egy olyan fa
Prüfer-kódja legyen, amelyben minden pont fokszáma páratlan szám. Adjuk is
meg ezt a fát! A sorozat: $1,1,5,x,6,6,8$. (Egy $n$ csúcsú fa Prüfer-kódjába
most beleértjük annak $(n-1)$-edik, $n$-nel egyenlő elemét is.)

\end{enumerate}

\end{document}
