\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{3.8cm}
\addtolength\hoffset{0cm}
\addtolength\textheight{5.0cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}
\usepackage{epic}
\usepackage{eepic}

\def\itemm{\vspace{-0.5mm}\item}

\newcounter{bak}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
1. gyakorlat, 2006. február 15.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Euler- és Hamilton-bejárások}
\end{center}

\vspace{0.6cm}

{\Large Euler-bejárások}\\

\begin{enumerate}

%  \itemm Van-e Euler-kör illetve Euler-út az alábbi gráfokban?
%
%\vspace{5mm}\hspace{3cm} \unitlength 0.2mm
%\begin{picture}(120,60)(0,-40)
%\put(0,0){\circle*{5}} \put(60,60){\circle*{5}}
%\put(0,60){\circle*{5}} \put(60,0){\circle*{5}}
%\put(30,90){\circle*{5}} \put(30,120){\circle*{5}}
%\drawline(0,0)(60,0)(0,60)(0,0)(60,60)(60,0)(0,60)(30,90)(60,60)(60,0)
%\drawline(30,90)(30,120) \drawline(0,60)(60,60)
%\end{picture}\hspace{0.7cm}
%\begin{picture}(90,90)(0,-40)
%\put(0,0){\circle*{5}} \put(0,30){\circle*{5}}
%\put(0,60){\circle*{5}} \put(0,90){\circle*{5}}
%\put(30,0){\circle*{5}} \put(30,30){\circle*{5}}
%\put(30,60){\circle*{5}} \put(30,90){\circle*{5}}
%\put(60,0){\circle*{5}} \put(60,30){\circle*{5}}
%\put(60,60){\circle*{5}} \put(60,90){\circle*{5}}
%\put(90,0){\circle*{5}} \put(90,30){\circle*{5}}
%\put(90,60){\circle*{5}} \put(90,90){\circle*{5}}
%\drawline(0,0)(0,90) \drawline(30,0)(30,90) \drawline(60,0)(60,90)
%\drawline(90,0)(90,90) \drawline(0,0)(90,0) \drawline(0,30)(90,30)
%\drawline(0,60)(90,60) \drawline(0,90)(90,90)
%\drawline(0,30)(30,0) \drawline(60,0)(90,30)
%\drawline(0,60)(30,90) \drawline(60,90)(90,60)
%\end{picture}\hspace{2cm}
%\begin{picture}(120,150)(0,-10)
%\put(0,30){\circle*{5}} \put(0,120){\circle*{5}}
%\put(30,60){\circle*{5}} \put(30,90){\circle*{5}}
%\put(60,0){\circle*{5}} \put(60,30){\circle*{5}}
%\put(60,60){\circle*{5}} \put(60,90){\circle*{5}}
%\put(60,120){\circle*{5}} \put(60,150){\circle*{5}}
%\put(90,60){\circle*{5}} \put(90,90){\circle*{5}}
%\put(120,30){\circle*{5}} \put(120,120){\circle*{5}}
%\drawline(0,30)(120,30)(120,120)(0,120)(0,30)
%\drawline(30,60)(90,60)(90,90)(30,90)(30,60)
%\drawline(60,0)(60,150)
%%\drawline(0,60)(60,60)
%\end{picture}

%  \itemm Minimálisan hányszor kell felemelni a ceruzát az alábbi ábrán
%  látható gráf lerajzolásakor, ha minden élet csak egyszer rajzolhatunk meg
%  (további vonalakat nem húzhatunk)?
%
%\hspace{6.5cm} \unitlength 0.1mm
%\begin{picture}(300,300)
%\put(0,150){\circle*{10}} \put(90,90){\circle*{10}}
%\put(90,210){\circle*{10}} \put(150,0){\circle*{10}}
%\put(150,300){\circle*{10}} \put(300,150){\circle*{10}}
%\put(210,90){\circle*{10}} \put(210,210){\circle*{10}}
%
%\drawline(0,150)(90,90)(150,0)(210,90)(300,150)(210,210)(150,300)(90,210)(0,150)
%\drawline(90,90)(210,90)(210,210)(90,210)(90,90)
%\drawline(90,90)(210,210)
%\drawline(90,210)(210,90)
%%\drawline(90,90)(210,90)
%%\drawline(90,90)(210,90)
%\end{picture}

  \itemm Milyen $n$ esetén tartalmaz a teljes $n$ pontú gráf Euler-kört
  illetve -utat?

  \itemm Van-e olyan egyszerű gráf, melynek van zárt Euler-vonala, továbbá
  páros számú pontja és páratlan számú éle van?

  \itemm Bizonyítsuk be, hogy tetszőleges összefüggő gráf élei bejárhatók
  úgy, hogy minden élen pontosan kétszer megyünk át.

%  \itemm Mutassuk meg, hogy egy összefüggő gráf élei bejárhatók úgy, hogy
%  mindegyiken kétszer megyünk végig, éspedig mindkét irányban
%  egyszer-egyszer.

  \itemm Igazoljuk, hogy ha egy gráf minden pontjának a foka 4, akkor élei
  színezhetők piros és kék színekkel úgy, hogy minden él teljes hosszában
  egyszínű legyen, és minden ponthoz két piros és két kék él illeszkedjék!

  \itemm Bizonyítsuk be, hogy ha egy összefüggő gráfban a páratlan fokszámú
  pontok száma $2k$, akkor a gráf élei bejárhatóak $k$ darab sétával.

  \itemm Egy gráf csúcsai a négy hosszúságú 0–1 sorozatok. Két pont akkor
  van összekötve, ha a nekik megfelelő sorozatok pontosan egy helyen térnek
  el. Található Euler-kör ebben a gráfban?

  \itemm A gráf csúcsai legyenek ugyanazok, mint az előző példában, de most
  akkor kössük össze őket, ha pontosan két helyen térnek el a sorozatok. A
  kérdés ugyanaz.

%  \itemm Képzeljünk el egy képzőművészeti kiállítást. A látogatók
%  szeretik a saját lelkiviláguk szerint élvezni a tárlat anyagát, azaz
%  annyira elmerülnek az esztétikai élmények kavalkádjában, hogy
%  útjelző táblák figyelemmel követésére már nem képesek. Annyi azért
%  persze még tőlük is elvárható, hogy mindig olyan folyosón haladnak
%  tovább, amerre addig még nem jártak és ha egy adott pillanatban
%  látnak ilyen folyosót, akkor azok egyikén tovább is haladnak.
%
%  Feladat: határozzuk meg, milyen lehet egy ilyen kiállítócsarnok, ha
%  azt szeretnénk, hogy az összes látogató a saját korlátoltsága
%  ellenére végignézhesse a kiállítást (gráfnyelven: melyek azok a
%  gráfok, amelyeknek egy adott pontjából (bejárat) induló tetszőleges
%  elakadó séta szükségképpen Euler-kör).

  \setcounter{bak}{\value{enumi}}
\end{enumerate}

\vspace{0.4cm}

{\Large Hamilton-bejárások}\\    
\begin{enumerate}
  \setcounter{enumi}{\value{bak}}
  
  \itemm Van-e Hamilton-kör az alábbi gráfokban?

\vspace{3mm}\hspace{2cm} \unitlength 0.1mm
\begin{picture}(300,300)(0,0)
\put(0,0){\circle*{10}} \put(0,360){\circle*{10}}
\put(60,60){\circle*{10}} \put(60,180){\circle*{10}}
\put(60,300){\circle*{10}} \put(120,120){\circle*{10}}
\put(120,240){\circle*{10}} \put(180,60){\circle*{10}}
\put(180,300){\circle*{10}} \put(240,120){\circle*{10}}
\put(240,240){\circle*{10}} \put(300,60){\circle*{10}}
\put(300,300){\circle*{10}} \put(300,180){\circle*{10}}
\put(360,0){\circle*{10}} \put(360,360){\circle*{10}}

\drawline(0,0)(0,360)(360,360)(360,0)(0,0)
\drawline(60,60)(60,300)(300,300)(300,60)(60,60)
\drawline(120,120)(120,240)(240,240)(240,120)(120,120)
\drawline(0,0)(120,120)
\drawline(0,360)(120,240)
\drawline(360,360)(240,240)
\drawline(360,0)(240,120)

\end{picture}
\hspace{3cm} \unitlength 0.05mm
\begin{picture}(900,700)(0,0)

\put(300,0){\circle*{20}} \put(700,0){\circle*{20}}
\put(400,200){\circle*{20}} \put(600,200){\circle*{20}}
\put(300,400){\circle*{20}} \put(700,400){\circle*{20}}
\put(900,400){\circle*{20}} \put(100,400){\circle*{20}}
\put(500,500){\circle*{20}} \put(500,700){\circle*{20}}
\put(500,350){\circle*{20}}

\drawline(300,0)(700,0)(900,400)(500,700)(100,400)(300,0)

\drawline(300,0)(300,400)(500,700)(700,400)(700,0)(400,200)(100,400)(500,500)(900,400)(600,200)(300,0)
\drawline(500,350)(400,200)
\drawline(500,350)(300,400)
\drawline(500,350)(500,500)
\drawline(500,350)(700,400)
\drawline(500,350)(600,200)
\end{picture}

  \itemm Milyen $m$ és $n$ értékekre tartalmaz Hamilton-kört illetve
  -utat az $m\times n$ méretű négyzetháló-gráf (amelynek összesen
  $(m+1)\times(n+1)$ pontja van)?
  
%  \itemm Ha egy páros gráfban van Hamilton-kör, akkor a gráf két
%  pontosztálya azonos elemszámú.
  
%  \itemm Ha egy $G$ gráfban van Hamilton-kör, akkor bármely $v$
%  csúcsára és bármely $e$ élére a $G-v$ és a $G-e$ gráf is
%  összefüggő.

%  \itemm Legalább hány éle van egy olyan $n$ pontú egyszerű gráfnak,
%  melynek van két különböző Hamilton-köre?

%  \itemm \emph{Hamilton-kör létezésének \emph{szükséges} feltétele:}
%  ha egy $G$ gráf valamely $S$ ponthalmazára a $G-S$ gráf összefüggő
%  komponenseinek száma több, mint $S$ pontjainak a száma, akkor
%  $G$-ben nem lehet Hamilton-kör. Lehet-e ilyenkor Hamilton-út
%  $G$-ben?

  \itemm Legyen $G$ olyan, a $V=\{p_1, p_2, ..., p_{2005}\}$
  ponthalmazon értelmezett egyszerű gráf, amelyben $\{p_i,p_j\}\in
  E$ pontosan akkor teljesül, ha $|i-j|\leqslant 2$. Van-e $G$-ben
  Hamilton-kör vagy Hamilton-út?

  \itemm Be lehet-e járni huszárral egy $4\times 4$-es sakktáblát?

  \itemm Mutassuk meg, hogy tetszőleges $n\geq 5$ értékre igaz az alábbi
  két állítás:
\begin{enumerate}
\item Létezik olyan $n$ csúcsú $G$ gráf, hogy $G$ is és $\overline G$ is
tartalmaz Hamilton-kört.
\item Létezik olyan $n$ csúcsú gráf, hogy sem $G$, sem $\overline G$ nem
tartalmaz Hamilton-kört.
\end{enumerate}

  \itemm Bizonyítsuk be, hogy ha egy $2n+1$ pontú egyszerű gráf minden
  csúcsának fokszáma legalább $n$, akkor a gráfban van Hamilton-út.

  \itemm Bizonyítsuk be, hogy a Petersen gráfban nincsen
  Hamilton-kör.

\itemm Egy szállodába egy 100 fős társaság érkezik, akik közül kezdetben
  bármely két ember jóban van egymással. Esténként egyetlen nagy kerek
  asztal körül ül le mindenki. Sajnos egy vacsora alkalmával az egymás
  mellé került emberek örökre összevesznek egymással. A társaság minden
  vacsora előtt úgy ül le, hogy mindenki a szomszédjaival jóban legyen. Ha
  ez lehetetlen, akkor az összes résztvevő még aznap este haza
  megy. Bizonyítsuk be, hogy legalább 25 éjszakát a szállodában tölt a
  társaság!


%  \itemm Mutassuk meg, hogy Pósa tételéből következik Ore tétele.

\end{enumerate}

\end{document}
