A számítástudomány alapjai - Régi ZH feladatok vegyesen
A VIK Wikiből
Ez az oldal A számítástudomány alapjai ZH kérdéseit tartalmazza, vegyesen. A többsége emlékezetből lett leírva. Érdemes először a főoldali ZH sorokat megnézni, és utána ezeket, ha van bent még újdonság.
_TOC_
Dualitás és Pert módszer
- Döntsük el, hogy az alábbi gráf síkba rajzolható-e! Ha igen, rajzoljuk le egyenes szakaszokkal, élkereszteződés nélkül, és adjuk meg a duálisát is! Ha nem, bizonyítsuk!
- Határozzuk meg az összes olyan egyszerű, összefüggő 3-reguláris gráfot, mely izomorf a duálisával!
- Egy irányított, (az irányítástól eltekintve) összefüggő, n pontú gráf körmátrixának két sora van. Hány éle van?
- Hány csúcsa lehet annak a fának, amelyben csak kétféle fokszám szerepel, ezek közül az egyik a 4, és a pontoknak pontosan a negyedrésze negyedfokú?
- Legyen G a következő 2n pontú gráf: {v1,…,vn} és {vn+1,…v2n} is egy-egy n hosszú kört alkot. Ezen kívül pedig minden i-re {vi,vi+n} E(G). Igaz-e, hogy G bármely élét elhagyva a maradék gráfban van Hamilton-kör?
- Az alábbi PERT feladatokban határozzuk meg a feladatok elvégzéséhez szükséges összes időt! Mik a kritikus tevékenységek? (x és p paraméterek!)
- Tegyük fel, hogy egy egyszerű G gráf előáll k db egyszerű, síkba rajzolható gráf éldiszjunkt uniójaként. (Azaz az éleit k csoportra lehet osztani úgy, hogy az egy csoportban lévő élek síkba rajzolható gráfot alkossanak.)Bizonyítsd be, hogy ha n a pontok száma, e az élek száma, akkor
- Síkba rajzolható-e az alábbi gráf?
- Egy egyszerű, hat pontból álló, összefüggő gráfban van 1, 2, 3, 4 és 5 fokú pont is. Mennyi lehet a hatodik pont foka?
