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

1. Melyik fa Prüfer-kódja a $4477418$ számsorozat?

2. 1. Egy fa Prüfer-kódja 100 tagú és csupa ugyanolyan számból áll. Rajzold fel a fát!

   2. Egy $F$ fa Prüfer-kódja csupa különböző számokból áll. Hogyan jellemezhetjük $F$-et?

3. Hány olyan fa adható meg az $1,2,...,100$ csúcsokon, melynek van olyan éle, amit elhagya a maradék gráf két komponensének pontjai rendre az $1,2,...,50$ ill. az $51,52,...,100$ csúcsok? (Vizsga, 1999. jan.)

4. Van-e olyan 9 pontú $G$ gráf, hogy sem $G$, sem a komplementere, $\overline{G}$ nem síkbarajzolható? (Vizsga, 2001. jan.)

5. Egy $n$ csúcsú fa fokszámai $n-1$ félék. Mekkora lehet $n$ értéke? (Vizsga, 1999. febr.)