Next: About this document ...
Bevezetés a számításelméletbe II.
6. gyakorlat 2002. március 21-22.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
PERT és Turán-tétele
- Állapítsuk meg, hogy mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT-diagram által leírt munkafolyamatnál? Adjuk meg a kritikus utakat is!
- Határozzuk meg az alábbi munka elvégzéséhez szükséges minimális időt, és a kritikus utakat a
paraméter függvényében. (ZH feladat)
- Adott egy
irányítatlan egyszerű gráf. Bizonyítsuk be, hogy a gráf éleinek tetszőleges kör mentes irányítása esetén az emeletek száma legalább
.
- Hány éle van a
Turán-gráfnak, ha
osztója
-nek?
- Minimálisan hány éle van egy olyan 2000 csúcsú gráfnak, melyre
? (ZH feladat)
- Igazoljuk, hogy ha az
csúcsú egyszerű
gráfnak
éle van, akkor
tartalmaz legalább két (nem feltétlenül diszjunkt)
részgráfot.
- HF Egy 90 fős társaságban bizonyos párok leveleznek egymással. Akárhogyan választunk ki 10 embert, ezek között biztosan lesz kettő, akik leveleznek egymással. Bizonyítsuk be, hogy a levelező párok száma legalább 405. (ZH feladat)
- HF Határozzuk meg az alábbi munka elvégzéséhez szükséges minimális időt, és a kritikus utakat a
paraméter függvényében. (ZH feladat)
- HF Bizonyítsuk be, hogy az 5 pontú teljes gráf élgráfja
nem perfekt.
- HF Egy legalább két csúcsú teljes gráf valamely
csúcsához illeszkedő élek közül néhányat elhagytunk. Bizonyítsuk be, hogy az így nyert gráf perfekt.
- HF Legyen az
-elemű halmaz összes részhalmaza egy irányított
gráf ponthalmaza, és az
,
részhalmazának megfelelő
pontok között pontosan akkor vezessen él, ha
és
. Mutassuk meg, hogy
-ben nincs irányított kör, majd adjuk meg egy maximális és egy minimális számú emeletekre bontását
-nek.
Next: About this document ...
Fogaras Daniel
2002-03-27