\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.4cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
8. feladatsor (2002. okt. 31.)}
\end{center}
\ \\
\begin{enumerate}
\item Legyenek egy $G$ gráf pontjai az $1,2,...,8$ számok, és az
$i$ és a $j$ csúcs pontosan akkor legyen összekötve, ha
$i-j\equiv\pm1\;\textup{vagy}\pm2\;(\textup{mod}\;8)$. Határozzuk
meg $G$ kromatikus számát, $\chi(G)$-t! (ZH, 2002. máj.)

\item Igaz-e, hogy ha egy $G$ 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 $G$-be új élek úgy, hogy a keletkező $G'$ gráfra
$\chi(G)=\chi(G')=\omega(G')$ teljesüljön?

\item  Egy négyzetrácsban legyen egy lépés, hogy egy négyzetből
átmehetünk egy vele közös éllel rendelkező négyzetbe. A $100\times
100$-as rácsban mi az a legkevesebb szín, amivel a négyzetek
kiszínezhetők úgy, hogy az egymásból pontosan két lépéssel
elérhető négyzetek színe különböző? (ZH, 1999. máj.)

\item Legyen $G$ véges egyszerű gráf, kromatikus száma $n$.
Tekintsük $G$-nek egy $n$ színnel való jó színezését, melyben a
használt színek egyike piros. Bizonyítsuk be, hogy a megadott
színezésben van olyan piros színű pont, amelynek a szomszédai
között az összes felhasznált pirostól különböző szín előfordul!
(Vizsga, 2000. aug.)

\item Legyen a $G$ gráf ponthalmaza
$V(G)=\{v_1,v_2,...,v_{128}\}$. A $v_i$ és a $v_j$ pontok között
akkor és csak akkor van él, ha
\begin{enumerate}
\item az indexek közül a nagyobbikat a kisebbikkel elosztva
kettőhatványt kapunk; \item a kisebb index osztója a nagyobb
indexnek.
\end{enumerate}
Határozzuk meg $G$ kromatikus számát!

\item A $G$ egyszerű $k$-reguláris gráf élkromatikus száma
$\chi_e(G)=k$. Bizonyítsuk be, hogy ekkor $G$-ben létezik teljes
párosítás! (ZH, 2001. okt.)

\item Bergengóciában 1, 2, 3 és 5 petákos érméket használnak.
Mindegyik annyi gramm tömegű, ahány petákot ér. Van $1-1$ érménk
mindegyikből, de az egyik hamis: tömege eltér a valódiétól.
Kétkarú mérleggel hány méréssel állapíthatjuk meg, hogy
\begin{enumerate}
\item melyik a hamis? \item melyik a hamis, és könnyebb vagy
nehezebb, mint a valódi?
\end{enumerate}

\item Legyen $G$ egy $n$ pontú irányítatlan egyszerű összefüggő
gráf, és jelölje $A$ a $G$ szomszédsági mátrixát. Bizonyítsuk be,
hogy minden $1\leq i,j\leq n$ számpárhoz létezik olyan $1\leq
k\leq n$, hogy az $A^k$ mátrix $i$-edik sorának $j$-edik eleme nem
nulla. (Pótzh, 2001. máj.)

\item Az alábbi mátrixok közül melyek állnak elő gráfok
körmátrixaként?
\[
\left(%
\begin{array}{cccc}
  1 & 1 & 1 & 0 \\
  1 & 1 & 0 & 1 \\
  1 & 0 & 1 & 1 \\
\end{array}%
\right) \hspace{1.5cm}
\left(%
\begin{array}{ccc}
  1 & 1 & 0 \\
  1 & 0 & 1 \\
  0 & 1 & 1 \\
\end{array}%
\right)
\]

\item Egy labdarúgó bajnokságban 10 csapat játszik körmérkőzést.
Minden fordulóban minden csapat pályára lép. Igazoljuk, hogy a
4.~forduló után van három olyan csapat, amelyik egyike sem
játszott még a másikkal! (A feladatra nov.~14-ig beadott helyes
megoldás csokit ér!)
\end{enumerate}
\end{document}
