Next: About this document ...
Számítástudomány elemei gyakorlat
5. feladatsor (2002. okt. 10.)
- Állapítsuk meg az alábbi gráf által szemléltetett
tevékenységekhez szükséges időt! Mely feladatok kritikusak?
- Határozzuk meg a mellékelt PERT-diagramokban a szükséges
időt és a kritikus tevékenységeket
és
között! (ZH, 2001.
máj. ill. dec.)
- Határozzuk meg (
és
függvényében) az ábrán látható
gráf által szemléltetett tevékenységhez szükséges időt.
(
)
- Ismételjük meg az előző példát, ha
értékét 1-ről
3-ra változtatjuk.
- Milyen a
teljes gráf mélységi ill. szélességi
bejárása?
- Mutassuk meg, hogy
tetszőleges fája előáll egy
mélységi vagy szélességi bejárás fájaként! Igaz-e ugyanez
-re?
- 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.)
- Bizonyítsuk az állítás megfordítását: ha a
összefüggő
gráf szélességi keresésekor nem kaptunk azonos szinten belüli
éleket, akkor
páros gráf!
- Legfeljebb hány éle lehet egy
pontú, egyszerű,
összefüggő gráfnak, ha egyik mélységi feszítőfájában van
fokú pont? (ZH, 2001. jan.)
- Legfeljebb hány éle lehet egy gráfnak, ha egyik mélységi
(DFS) keresőfája egy
szintű,
pontú teljes bináris fa?
- Igaz-e, hogy ha egy páros gráfban van Hamilton-kör, akkor
van benne teljes párosítás is?
Next: About this document ...
Veto Balint
2002-10-10