Számítástudomány elemei gyakorlat
2. feladatsor (2002. szept. 19.)

1. Vannak-e izomorfak az alábbi gráfok között?
   $\left(\textup{a}\right)$ $\left(\textup{b}\right)$ $\left(\textup{c}\right)$

2. Legyen a $G$ egyszerű gráfban minden pont foka legalább $k$. Mutassuk meg, hogy $G$-ben van egy legalább $k$ hosszúságú út!

3. Rajzold fel az összes 3, 4, illetve 5 pontú fát! (Az izomorfakat csak egyszer.)

4. Melyik fa Prüfer-kódja a 447741 számsorozat?

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

6. 1. Egy $n$ pontú fában legfeljebb hány két élből álló út található? (Vizsga, 1999. máj.)

   2. Mutass példát ilyen fára!

7. Bizonyítsuk be, hogy egy $n$ pontú fában a másodfokú pontok száma nem lehet pontosan $n-3\;$! (ZH, 2000. máj.)

8. Egy a koordinátarendszerben elhelyezett kocka éleit a következőképpen súlyozzuk meg: az $x$ tengellyel párhuzamos élek súlya 1, az $y$ tengellyel párhuzamosaké 2, a $z$ tengellyel párhuzamosaké pedig 3. Hányféleképpen választhatunk ki egy minimális súlyú feszítőfát ebből a súlyozott gráfból? (Pótzh, 1999. máj.)

9. Egy teljes gráf ponthalmaza $\{x_1,x_2,...,x_s,y_1,y_2,...,y_t\}$. Az $\left(x_i,x_j\right)$ élek költsége (súlya) 1 Ft, az $\left(y_i,y_j\right)$ éleké 2 Ft, az $\left(x_i,y_j\right)$ éleké pedig 3 Ft. Mennyibe kerül a legolcsóbb feszítőfa? (ZH, 2000. márc.)

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