„A számítástudomány alapjai - Régi ZH feladatok vegyesen” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
Kory (vitalap | szerkesztései) (Új oldal, tartalma: „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…”) |
Kory (vitalap | szerkesztései) |
||
| 16. sor: | 16. sor: | ||
[[:Media:szamtud_ZH_gyak_graf3.png|Gráf2]] | [[:Media:szamtud_ZH_gyak_graf3.png|Gráf2]] | ||
[[:Media:szamtud_ZH_gyak_graf4.png|Gráf3]] | [[:Media:szamtud_ZH_gyak_graf4.png|Gráf3]] | ||
| + | *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 <math>k\ge\frac{e}{3n-6}</math> | ||
| + | *Síkba rajzolható-e az alábbi gráf? | ||
| + | [[Media:Szamtud ZH gyak graf5.png|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? | ||
A lap 2013. június 10., 21:23-kori változata
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 [math]k\ge\frac{e}{3n-6}[/math]
- 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?
