Számítástudomány elemei gyakorlat
8. feladatsor (2002. okt. 31.)

1. 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.)

2. 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?

3. 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.)

4. 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.)

5. 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
   1. az indexek közül a nagyobbikat a kisebbikkel elosztva kettőhatványt kapunk;
   2. a kisebb index osztója a nagyobb indexnek.
   Határozzuk meg $G$ kromatikus számát!

6. 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.)

7. 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
   1. melyik a hamis?
   2. melyik a hamis, és könnyebb vagy nehezebb, mint a valódi?

8. 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.)

9. 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 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{array}%% \right)$$
   
   

10. 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!)