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

 

1. Á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!
2. Határozzuk meg az alábbi munka elvégzéséhez szükséges minimális időt, és a kritikus utakat a $p$ paraméter függvényében. (ZH feladat)
3. Adott egy $G$ 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 $\chi(G)$.
4. Hány éle van a $T_{n,k}$ Turán-gráfnak, ha $k$ osztója $n$-nek?
5. Minimálisan hány éle van egy olyan 2000 csúcsú gráfnak, melyre $\alpha(G)=5$ ? (ZH feladat)
6. Igazoljuk, hogy ha az $n \ge 4$ csúcsú egyszerű $G$ gráfnak $\frac{n^2}{4} +1$ éle van, akkor $G$ tartalmaz legalább két (nem feltétlenül diszjunkt) $K_3$ részgráfot.
7. 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)
8. HF Határozzuk meg az alábbi munka elvégzéséhez szükséges minimális időt, és a kritikus utakat a $p$ paraméter függvényében. (ZH feladat)
9. HF Bizonyítsuk be, hogy az 5 pontú teljes gráf élgráfja $L(K_5)$ nem perfekt.
10. HF Egy legalább két csúcsú teljes gráf valamely $v$ csúcsához illeszkedő élek közül néhányat elhagytunk. Bizonyítsuk be, hogy az így nyert gráf perfekt.
11. HF Legyen az $n$-elemű halmaz összes részhalmaza egy irányított $G_n$ gráf ponthalmaza, és az $X$, $Y$ részhalmazának megfelelő $x,y$ pontok között pontosan akkor vezessen él, ha $\X \subset Y$ és $\vert X\vert+1=\vert Y\vert$. Mutassuk meg, hogy $G_n$-ben nincs irányított kör, majd adjuk meg egy maximális és egy minimális számú emeletekre bontását $G_n$-nek.