\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}
12. gyakorlat, 2006. december 6.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Gráfok 2.}
\end{center}

\vspace*{2mm}

\begin{enumerate}
\setcounter{enumi}{135}

\item Rajzoljuk le a $K_4$ gráf duálisát!

\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 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.)

\item Hány különböző minimális súlyú feszítőfája van az alábbi gráfnak?
\vspace*{4cm}

\item Mely $k$ pozitív egészekre adható meg olyan, 2000 címkézett csúcsot és
2000 élet tartalmazó egyszerű összefüggő $G$ gráf, amelyre igaz a következő:
$G$-ben a 2000 él közül adható egynek 2 egységnyi, 1999-nek pedig 1
egységnyi súly úgy, hogy a $G$-ből kiválasztható különböző minimális súlyú
feszítőfák száma éppen $k$ legyen?

\item Legyen $G$ egy egyszerű irányítatlan gráf és $A$ a szomszédossági
mátrixa. Mutassuk meg, hogy az $A^3$ mátrix főátlóbeli elemeinek összege a
$G$-beli háromszögek számának hatszorosa.

\item Bizonyítsuk be, hogy egy irányítatlan egyszerű gráf szomszédossági
mátrixában akkor és csak akkor van két sor, melyek skaláris szorzata
legalább 2, ha a gráfban található pontosan 4 hosszúságú kör.

\item Legyen $B$ egy egyszerű irányítatlan $G$ gráf illeszkedési mátrixa,
$D$ pedig $G$ élgráfjának szomszédossági mátrixa. Mit mondhatunk a $B^TB-D$
mátrixról?

\end{enumerate}

\end{document}
