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

2002. március 28.

1. Adjunk meg egy maximális folyamot az alábbi hálózatban:

2. Határozzuk meg, hogy melyik az a legnagyobb $k$ érték, amire $k$-szorosan pont-, illetve élösszefüggők az alábbi gráfok:
(a) $n\geq 1$ hosszú út (b) $n\geq 3$ hosszú kör (c) $K_n$ ($n\geq 4$)



3. (a) Igaz-e, hogy ha minden él kapacitása páros szám, akkor van olyan maximális folyam, aminek minden élén a folyam értéke páros szám?
(b) Igaz-e ugyanez páratlan számokkal?

4. ZH! Melyik az a legnagyobb $k$ szám, amelyre $K_{n,n}$ teljes páros gráf $k$-szorosan pontösszefüggő?

5. HF, ZH! Bizonyítsuk be, hogy ha egy $k$-szorosan pontösszefüggő $G$ gráfból elhagyunk egy élet, akkor a kapott gráf $(k-1)$-szeresen pontösszefüggő lesz.

6. ( 16 jön ki ) Adjunk meg az alábbi ábrán látható hálózatban egy maximális folyamot!

7. HF Bizonyítsuk be, hogy ha egy gráf $k$-szorosan pontösszefüggő akkor $k$-szorosan élösszefüggő is.



8. ZH! Egy hálózat gráfja a kocka élhálózata az ábrán látható irányítással. (A forrás és a nyelő a kocka két átellenes pontja, lásd az ábrán.)

Az éleket vagy 1 vagy 2 kapacitásúnak választhatjuk meg a következő feltételek mellett:
(a) az elérhető maximális folyam értéke a lehető legnagyobb legyen,
(b) az (a) feltétel teljesülése mellett minél kevesebb 2 kapacitású él legyen.
Hány 2 kapacitású élre van szükség és melyek lesznek ezek?

9. ZH! A $G$ összefüggő, legalább 3 pontot tartalmazó gráfban minden $v$ pontra és $e$ élre teljesül az, hogy van $v$-n és $e$-n is átmenő kör. Mutassuk meg, hogy $G$ kétszeresen pontösszefüggő.

10. Határozzuk meg, hogy melyik az a legnagyobb $k$ érték, amire $k$-szorosan pont-, illetve élösszefüggők az alábbi gráfok:

11. Adjunk meg az alábbi ábrán látható hálózatban egy maximális folyamot!

12. ZH Mutassuk meg, hogy egy $k$-szorosan összefüggo $n$-pontú gráfnak legalább $kn/2$ éle van.

13. (a) Mutassuk meg, hogy egy 2-reguláris gráf pont és élösszefüggőségi szám megegyezik.
(b) Ugyanez 3-reguláris gráfokra.

14. ZH!, * Bizonyítsuk be, hogy ha $G$ egy egyszerű síkgráf, akkor $G$ nem lehet hatszorosan pontösszefüggő!