\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{-2.5cm}
\addtolength\textwidth{5.8cm}
\addtolength\hoffset{-1.2cm}
\addtolength\textheight{5.5cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{graphicx}
%\usepackage{epic}

\begin{document}

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

\vspace{8mm}
\textbf{\LARGE Gráfok – Síkbarajzolhatóság}
\end{center}

\vspace*{9mm}

\begin{enumerate}
\setcounter{enumi}{120}

\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 \vspace*{2mm} \\
\begin{tabular}{lll}
 \begin{tabular}{rl}
  \vspace{1mm} (a) & 1, 2, 2, 3, 3, 3; \\
  \vspace{1mm} (b) & 1, 1, 2, 2, 3, 4, 4; \\
  \vspace{1mm} (c) & 5, 5, 5, 6, 6, 6, 7, 7, 7;
 \end{tabular} &
 ~~~~~~~~~~~~ &
 \begin{tabular}{rl}
  \vspace{1mm} (d) & 1, 2, 2, 3, 4, 4, 5, 6, 6; \\
  \vspace{1mm} (e) & 1, 1, 3, 3, 3, 3, 5, 6, 8, 9; \\
  \vspace{1mm} (e) & 2, 3, 3, 4, 5, 6, 7\,?
 \end{tabular}
\end{tabular}

\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 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 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 Öt falu szeretne aszfaltutat építeni egymás között, hogy
%bármelyik faluból el tudjanak jutni bármelyik másik faluba, akkor
%is, ha nagy eső van. Mi a legolcsóbb megoldás, ha az útépítés
%költségeit az egyes falvak közt az adott élre írt számok jelzik?
%
%\vspace{5mm}\hspace{5cm} \unitlength 0.07mm
%\begin{picture}(700,500)
%\put(0,0){\circle*{10}} \put(700,0){\circle*{10}}
%\put(0,500){\circle*{10}} \put(700,500){\circle*{10}}
%
%\put(200,250){\circle*{10}} \put(500,250){\circle*{10}}
%\drawline(0,0)(200,250) \drawline(0,500)(200,250)
%\drawline(500,250)(700,0) \drawline(500,250)(700,500)
%\drawline(0,0)(700,0) \drawline(0,500)(700,500)
%\drawline(0,0)(0,500) \drawline(700,0)(700,500)
%\drawline(200,250)(500,250)
%
%\put(-20,250){\makebox(0,0){$2$}}
%\put(680,250){\makebox(0,0){$2$}}
%\put(350,30){\makebox(0,0){$1$}}
%\put(350,530){\makebox(0,0){$1$}}
%\put(350,280){\makebox(0,0){$1$}}
%\put(140,130){\makebox(0,0){$1$}}
%\put(140,370){\makebox(0,0){$1$}}
%\put(560,130){\makebox(0,0){$1$}}
%\put(560,370){\makebox(0,0){$1$}}
%\end{picture}

%\item Hányféleképpen választhatunk ki minimális súlyú feszítőfát
%az alábbi gráfokból?
%
%\vspace{5mm}\hspace{3cm} \unitlength 0.07mm
%\begin{picture}(600,700)(0,-50)
%\put(200,0){\circle*{10}} \put(0,400){\circle*{10}}
%\put(400,400){\circle*{10}} \put(200,700){\circle*{10}}
%\put(600,700){\circle*{10}}
%
%\drawline(200,0)(0,400) \drawline(200,0)(400,400)
%\drawline(0,400)(400,400) \drawline(0,400)(200,700)
%\drawline(400,400)(200,700) \drawline(400,400)(600,700)
%\drawline(200,700)(600,700)
%
%\put(75,200){\makebox(0,0){8}} \put(325,200){\makebox(0,0){$7$}}
%\put(200,430){\makebox(0,0){$4$}}
%\put(50,550){\makebox(0,0){$2.5$}}
%\put(335,550){\makebox(0,0){$3$}}
%\put(535,550){\makebox(0,0){$5$}}
%\put(400,730){\makebox(0,0){$6$}}
%\end{picture}
%$\qquad \qquad$
%\begin{picture}(1000,800)(0,-50)
%\put(300,0){\circle*{10}} \put(700,0){\circle*{10}}
%\put(400,200){\circle*{10}} \put(600,200){\circle*{10}}
%\put(300,400){\circle*{10}} \put(700,400){\circle*{10}}
%\put(900,400){\circle*{10}} \put(100,400){\circle*{10}}
%\put(500,500){\circle*{10}} \put(500,700){\circle*{10}}
%
%\drawline(300,0)(700,0) \drawline(100,400)(900,400)
%\drawline(700,0)(900,400)(500,700)(100,400)(300,0)
%\drawline(400,200)(700,400)
%\drawline(500,500)(500,700)
%\drawline(300,400)(600,200)(500,500)(400,200)
%\drawline(300,0)(400,200) \drawline(700,0)(600,200)
%%\drawline(200,250)(500,250)
%
%\put(175,175){\makebox(0,0){$1$}}
%\put(825,175){\makebox(0,0){$1$}}
%\put(275,575){\makebox(0,0){$1$}}
%\put(725,575){\makebox(0,0){$1$}}
%\put(500,-20){\makebox(0,0){$1$}}
%\put(520,600){\makebox(0,0){$3$}}
%\put(220,425){\makebox(0,0){$3$}}
%\put(760,425){\makebox(0,0){$3$}}
%\put(400,425){\makebox(0,0){$2$}}
%\put(400,275){\makebox(0,0){$2$}}
%\put(600,275){\makebox(0,0){$2$}}
%\put(350,335){\makebox(0,0){$2$}}
%\put(650,335){\makebox(0,0){$2$}}
%\put(380,120){\makebox(0,0){$3$}}
%\put(620,120){\makebox(0,0){$3$}}
%%\put(500,-20){\makebox(0,0){$1$}}
%
%\end{picture}

\item Síkbarajzolhatóak-e az ábrán látható gráfok?
\vspace*{-0.4cm}
\begin{figure}[h]
  \begin{center}
\input{muab14.pstex_t}
%\input{muab4.pstex_t}
\end{center}
\end{figure}
\vspace*{-0.5cm}

\item Négy szomszéd mindegyike úgy épített utat a másik három házához,
hogy azok nem keresztezik egymást. Egy ötödik ember újabb házat épít.
\begin{itemize}
\item Bizbe, hogy nem tud úgy utakat építeni házától a másik
négy házához, hogy az úthálózatban ne legyenek kereszteződések.
\item Bizbe, hogy valamely három házhoz viszont tud kereszteződés
nélkül utat építeni.
\end{itemize}

\item Bizonyítsuk be, hogy egy egyszerű síkbarajzolható gráfban nem lehet
minden pont foka legalább 6.

\item Keressünk olyan 8 pontú gráfot, hogy se ő, se a komplementere ne
legyen síkbarajzolható.

\item Keressük meg az összes 6 csúcsú nem síkgráfot.

\item Hány metszéspontja van maximálisan egy konvex 9-szög átlóinak?

\item Mutassuk meg, hogy egy nyolc csúcsú teljes gráfot a síkra
lerajzolva legalább 10 élkeresztezés jön létre.

\item Egy 20 csúcsú konvex poliéder lapjainak száma 12. Hány oldala van
az egyes lapoknak, ha tudjuk, hogy ez a szám minden lapra azonos? 

\item Egy hatelemű halmaz részhalmazai legyenek egy gráf pontjai.
Két pont akkor legyen összekötve éllel, ha a nekik megfelelő
részhalmazok diszjunktak (metszetük üres). Síkbarajzolható-e ez a
gráf?

\item Tudjuk, hogy síkbarajzolható gráfok esetén $n+t=e+2$. Hogyan módosul
ez a képlet nem síkbarajzolható gráfok esetén?

\end{enumerate}

\end{document}
