Bevezetés a számításelméletbe II.

2002. március 21.

1. Perfekt-e az alábbi gráf?

2. Á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!

3. (a) Hány éle van a $T_{n,k}$ Turán-gráfnak, ha $k$ osztója $n$-nek?
(b) Bizonyítsuk be, hogy a $T_{n,k}$ Turán-gráf minden $G$ részgráfjára $\chi(G)\leq k$.

4. ZH! Egy legalább két csúcsú teljes gráf néhány, egy csúcshoz illeszkedő élét elhagyjuk. Bizonyítsuk be, hogy az így kapott gráf perfekt.

5. ZH! Állapítsuk meg, hogy a $p$ paraméter függvényében mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT diagram által leírt munkafolyamatnál! Melyek a kritikus tevékenységek?

6. Mutass olyan $G$ gráfot, amire $\chi(G)=\omega(G)$, de $G$ mégse perfekt!

7. HF, ZH! Egy 90 fős társaságból bizonyos párok leveleznek egymással. Akárhogyan választunk ki közülük 10 embert, ezek között mindig van legalább kettő, akik leveleznek egymással. Bizonyítsuk be, hogy a levelező párok száma legalább 405.

8. HF Adott egy $G$ irányítatlan egyszerű gráf. Bizonyítsuk be, hogy $G$ éleinek egy tetszoleges irányított kör mentes irányításában az emeletek száma legalább $\chi(G)$.



9. Bizonyítsuk be, hogy az 5 pontú teljes gráf élgráfja, $L(K_5)$ nem perfekt!

10. ZH! Minimálisan hány éle kell, hogy legyen egy olyan 2000 csúcsú egyszerű $G$ gráfnak, melyre $\alpha(G)=5$?

11. ZH! Állapítsuk meg, hogy a $p$ paraméter függvényében mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT diagram által leírt munkafolyamatnál! Melyek a kritikus tevékenységek?

12. ZH! Bizonyítsuk be, hogy egy perfekt gráfból egy csúcs megduplázásával nyert gráf is perfekt! (A $v\in V(G)$ csúcs megduplázása azt jelenti, hogy a $G$ gráfhoz hozzáveszünk egy új $v'$ pontot, és azt a $v$ pont $G$-beli szomszédaival kötjük össze.)

13. Legyen egy $n$-elemu halmaz összes (azaz hány darab?) részhalmaza egy $G_n$ irányított gráf ponthalmaza, és az $X,Y$ részhalmazának megfelelo $x,y$ pontok között akkor és csak akkor vezessen él, ha $X\subset Y$ és $\vert X\vert+1=\vert Y\vert$. Mutassuk meg, hogy $G$-ben nincs irányított kör, majd adjuk meg mind maximális számú, mind minimális számú emeletekre való bontását.

14. Á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 tevékenységeket is!

15. Maximum hány éle lehet egy $n$ pontú, irányított kört nem tartalmazó egyszeru gráfnak?

16.* Legyen $G_1$ és $G_2$ két olyan perfekt gráf, melyek metszete teljes gráf. (A metszet pontjai a közos pontok, élei a közös élek.) Mutasd meg, hogy $G_1\cup G_2$ is perfekt! (Az únió pontjai a két ponthalmaz együtt, élei az élhalmazok úniója.)

17. * Igazoljuk, hogy ha az $n\geq 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.