Bevezetés a számításelméletbe 1. gyakorlat
10. feladatsor (2002. ápr. 26.)

1. Van-e olyan egyszerű gráf, melyben a pontok foka rendre
   $$\begin{array}{ll} \left(a\right)\;1,2,2,3,3,3\hspace{5cm}... ...4,5,6,6\\ \left(e\right)\;5,5,5,6,6,6,7,7,7& \end{array}$$

2. 1. A hét törpe minden este más sorrendben szerene sorban állni, amikor Hófehérke a vacsorát osztja. Hány egymás utáni napon tehetik ezt meg?
   2. Hány hatra végződő néggyel osztható ötjegyű szám van?
   3. Egy 12 fős társaságot egy szálloda két háromágyas és három kétágyas szobájában kell elszállásolni. Hány különböző szobabeosztás lehetséges, ha az azonos számú ágyat tartalmazó szobákat nem különböztetjük meg egymástól? (Vizsga, 1999. jan.)
   4. Hány olyan különböző lottószelvényt lehet kitölteni, hogy mindegyik pontosan három találatos legyen? (Vizsga, 2001. jan.)
3. Vannak-e izomorfak az alábbi gráfok között?
   $\left.a\right)$ $\left. b\right)$ $\left. c\right)$
4. Rajzold fel az összes 3, 4, illetve 5 pontú fát! (Az izomorfakat csak egyszer!)
5. Egy $G$ gráf pontjai legyenek egy kocka csúcsai. Két csúcs pontosan akkor legyen összekötve $G$-ben, ha a kockában él mentén szomszédosak. Az alábbiak köz ül melyek izomorfak $G$-vel?
   
6. 1. Egy gimnáziumban 16 osztály van, az osztálylétszám mindenhol 30. Mindegyik osztályt háromtagú küldöttség képviseli a diákbizottságban. Hányféle lehet a diákbizottság összetétele?
   2. Tíz gyerek hányféleképpen állítható úgy sorba, hogy Jancsi és Juliska egymás mellett álljanak? (ZH. 2000. dec.)
   3. Hányféleképpen ültethető le egy harminc fős társaság 5 darab, egyenként hatfős asztalhoz, ha két ültetést pontosan akkor tekintünk azonosnak, ha minden résztvevőnek ugyanaz a bal és a jobb oldali szomszédja? (Vizsga, 2000. jan.)
   4. Tizenöt vívóból hányféleképpen alkothatunk három négyfős csapatot, ha egy személy több csapatban is szerepelhet? (Vizsga, 1999. jan.)
7. Határozd meg az összes olyan - páronként nem izomorf - egyszerű gráfot, melyre
   $$\begin{array}{ll} \left(a\right)\;n=4,e=5\hspace{5cm}& \left(b\... ...hspace{5cm}\\ \left(c\right)\;n=5,e=7& \left(d\right)\;n=5,e=8 \end{array}$$
   $n$ a pontok számát, $e$ az élek számát jelöli.
8. Egy $n$ pontú egyszerű gráfban minden pont foka legalább $$\frac{n}2$$. Bizonyítsd be, hogy a gráf összefüggő!