Számítástudomány elemei gyakorlat
5. feladatsor (2002. okt. 10.)

1. Állapítsuk meg az alábbi gráf által szemléltetett tevékenységekhez szükséges időt! Mely feladatok kritikusak?
   
   $$\unitlength 1mm \begin{picture}(30,14)(-5,-2) \put(0,5){\cir... ...{\makebox(0,0){4}} \put(18.5,9){\makebox(0,0){6}} \end{picture}$$
   
   

2. Határozzuk meg a mellékelt PERT-diagramokban a szükséges időt és a kritikus tevékenységeket $S$ és $T$ között! (ZH, 2001. máj. ill. dec.)

   
   

   $$\unitlength1mm \begin{picture}(50,30)(-5,-5) \put(0,10){\cir... ...2){\makebox(0,0){4}} \put(23,0){\makebox(0,0){T}} \end{picture}$$
   
   

3. 1. Határozzuk meg ($a$ és $b$ függvényében) az ábrán látható gráf által szemléltetett tevékenységhez szükséges időt. ($a,b\geq0$)

      
      

      $$\unitlength1mm \begin{picture}(42,26)(-5,-5) \put(0,8){\circ... ...\makebox(0,0){$b$}} \put(24,14){\makebox(0,0){1}} \end{picture}$$
      
      

   2. Ismételjük meg az előző példát, ha $l(B,D)$ értékét 1-ről 3-ra változtatjuk.

4. 1. Milyen a $K_n$ teljes gráf mélységi ill. szélességi bejárása?

   2. Mutassuk meg, hogy $K_4$ tetszőleges fája előáll egy mélységi vagy szélességi bejárás fájaként! Igaz-e ugyanez $K_5$-re?

5. 1. Mutassuk meg, hogy páros gráf esetén szélességi kereséskor nem találhatunk azonos szinten belüli éleket! (ZH, 1999. márc.)
   2. Bizonyítsuk az állítás megfordítását: ha a $G$ összefüggő gráf szélességi keresésekor nem kaptunk azonos szinten belüli éleket, akkor $G$ páros gráf!

6. Legfeljebb hány éle lehet egy $n$ pontú, egyszerű, összefüggő gráfnak, ha egyik mélységi feszítőfájában van $n-1$ fokú pont? (ZH, 2001. jan.)

7. Legfeljebb hány éle lehet egy gráfnak, ha egyik mélységi (DFS) keresőfája egy $n$ szintű, $2^n-1$ pontú teljes bináris fa?

8. Igaz-e, hogy ha egy páros gráfban van Hamilton-kör, akkor van benne teljes párosítás is?