\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{-1.5cm}
\addtolength\textwidth{4.8cm}
\addtolength\hoffset{-0.5cm}
\addtolength\textheight{5.5cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}
\usepackage{graphicx}

\begin{document}

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

\vspace{10mm}
\textbf{\LARGE Gallai tételek – Színezések 1.}
\end{center}

\vspace*{9mm}

\begin{enumerate}
\setcounter{enumi}{44}

%\item Állapítsuk meg a 35. feladatban (múlt gyakorlat) szereplő páros
%gráf(ok)ban
%\begin{itemize}
%\item a minimális lefogó ponthalmazokat és ezek elemszámát,
%\item a maximális független ponthalmazokat és ezek elemszámát,
%\item a minimális lefogó élhalmazokat és ezek elemszámát,
%\item a maximális független élhalmazokat és ezek elemszámát.
%\end{itemize}

\item Határozzuk meg a független élek maximális számát az alábbi két
gráfban. Bizonyítsuk be, hogy nem lehet többet találni! \vspace*{3mm}

\includegraphics[scale=0.5]{gallai1.eps} \hspace*{1cm}
\includegraphics[scale=0.5]{gallai2.eps}

\item Az $a_1, a_2 \ldots a_{2004}$ csúcsokból álló $G$ gráf $a_i$ és
$a_j$ pontja akkor van összekötve, ha $i+j$ osztható 3-mal (és $i\neq
j$). Határozzuk meg $\tau(G)$, $\nu(G)$, $\rho(G)$, $\alpha(G)$,
$\omega(G)$ értékét.

\item Bizonyítsuk be, hogy $\Delta(G)\cdot\tau(G)\geqslant |E(G)|$.

%\item Bizonyítsuk be, hogy egy háromszögmentes $G$ gráfban
%$\alpha(G)\cdot\tau(G)\geqslant |E(G)|$.

\item Igazoljuk, hogy $\chi(G)\geqslant {|V(G)|\over \alpha(G)}$.
Keressünk olyan gráfokat, ahol ez a becslés pontos, illetve ahol
pontatlan. 

\item Bizonyítsuk be, hogy minden $n$ csúcsú gráfra
$\chi(G)\cdot\chi(\overline{G}) \geqslant n$.

%\item Bizonyítsuk be, hogy egy $G$ teljes páros gráfban (ahol tehát a két
%színosztály között minden él jelen van) mindig felláll, hogy
%$\nu(G)\cdot\rho(G)=|E(G)|$.

%\item Legyen $F$ egy maximális független ponthalmaz az egyszerű $G$ gráfban
%és legyen $F'$ egy független ponthalmaz $V(G)-F'$-ben. Bizonyítsuk be, hogy
%$\nu(G)\geqslant |F'|$.

\item Határozzuk meg véges egyszerű $G$ gráfokra a $\frac{\tau(G)}{\nu(G)}$ érték
lehető legkisebb és legnagyobb értékét.

%\item Minimálisan hány éle kell, hogy legyen egy 2000 csúcsú $G$ gráfnak, ha
%függetlenségi számára $\alpha(G)=5$ teljesül?


\item Hány szín szükséges az alábbi gráf pontjainak kiszínezéséhez?

\begin{figure}[h!]
\begin{center}
\scalebox{1}{\includegraphics{4szin.eps}}
\end{center}
\end{figure}
\vspace{-1.5 \baselineskip}

\item Legyen $V(G)=\{v_1,\dots,v_{100}\}$, ahol $v_i$ és $v_j$ között akkor és
csak akkor megy él, ha $7\geq |i-j|$. Mennyi $G$ kromatikus száma?

\item Minden páros $G$ gráfra $\chi(G) \leqslant 2$. Mikor nem
áll egyenlőség?

\item Bizonyítsuk be, hogy minden páros $G$ gráfra $\chi(G)=\omega(G)$.

\item Legyenek $G$ csúcsai az összes természetes számok és legyen 
az $n$ és $m$ csúcs éllel összekötve pontosan akkor, ha $n+m$
páratlan. Mennyi a gráf kromatikus száma?

\item A $V(G)={1, 2, \ldots 1023}$ ponthalmazon definiáljuk a $G$ gráfot
úgy, hogy benne $k$ és $m$ pontosan akkor van összekötve éllel, ha nem
egyenlőek és az egyik osztja a másikat. Határozzuk meg $\chi(G)$ értékét.
  
\end{enumerate}

\vspace*{1cm}

Puska: \vspace*{1mm}

$\tau$ (tau) – lefogó pontok minimális száma

$\alpha$ (alfa) – független pontok maximális száma

$\rho$ (ró) – lefogó élek minimális száma

$\nu$ (nű) – független élek maximális száma

\end{document}
