\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage{graphics}
\usepackage{epic}
\usepackage{eepic}
\usepackage{color}
\usepackage{amssymb}

\setlength{\hoffset}{-2 cm}
\setlength{\voffset}{-1 cm}
\addtolength{\textwidth}{5 cm}
\addtolength{\textheight}{8 cm}

\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
8. Gyakorlat
}
\end{center}

\large

\begin{enumerate}

\item Igaz-e, hogy ha egy gráf $\chi (G)$ kromatikus számára és $\omega (G)$ 
klikkszámára teljesül, hogy $\chi (G) > \omega (G)$, akkor behúzhatók a $G$-be 
új élek, úgy hogy a keletkező $G^{'}$ gráfra 
$\chi (G) = \omega (G^{'}) = \chi (G^{'})$ teljesüljön?

\item Bizonyítsuk be, hogy minden $n$ pontú gráfra 
$\chi (G) \le 1+n-\alpha (G)$ és $\chi (G) \alpha (G) \ge n$.
Próbáljunk $e$ és $\nu (G)$ segítségével a fenti másodikhoz hasonló 
alsó becslést mondani $\chi_e (G)$-re!

\item Hagyjuk el egy teljes gráfból egy Hamilton kör éleit. 
Mennyi az így keletkezett gráf kromatikus száma? Próbálkozzunk külön 
páros és páratlan pontszám esetén!

\item Bizonyítsuk be, hogy minden $n$ pontú gráfra 
$\chi (G) \chi (\overline G) \ge n$.

\item Tegyük fel, hogy $G$ minden éle legfeljebb egy körben van benne.
Bizonyítsuk be, hogy ekkor $\chi (G) \le 3$ !

\item Legyen $V(G)=\{v_1, v_2, \dots, v_{106}\}$. $v_i$ és $v_j$ között 
pontosan akkor van él, ha $|i-j| \le 7$ Mennyi a $G$ kromatikus száma?

\item Bizonyítsuk be, hogy ha $G$ reguláris, de nem kétszeresen összefüggő, 
akkor $\chi_e (G) > \Delta(G)$!

\item Igazoljuk, hogy egy síkgráf tartományai pontosan akkor színezhetőek két 
színnel, ha minden pont foka páros!

\item Legyen $A$ egy egyszerű irányítatlan gráf szomszédossági mátrixa.
Bizonyítsuk be hogy az alábbi két kijelentés ekvivalens!
\begin{enumerate}
\item A gráf nem tartalmaz 4 hosszúságú kört.
\item Az $A$ bármely két sorának skalárszorzata legfeljebb egy.
\end{enumerate} 

\item Lássuk be, hogy egy egyszerű irányítatlan gráf akkor és csak akkor 
páros, ha szomszédossági mátrixának minden páratlan kitevőjű hatványában 
minden diagonális elem 0.

\end{enumerate}

\end{document}










