Bevezetés a számításelméletbe II.
7. gyakorlat 2002. március 28-29.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Hálózati folyamok és Menger tételei

 

1. Határozzuk meg a lenti ábrákon látható hálózatokban a maximális folyam értékét, és a folyam értékének maximalitását indokoljuk is!

2. Legyenek egy gráf pontjai az $n$ hosszúságú $0-1$ sorozatok. Vezessen irányított él $a$-ból $b$-be, ha $a$-ban kevesebb $1$-es van mint $b$-ben, és az él kapacitása legyen az egyesek számának különbsége. A forrás legyen a csupa 0-t és a nyelő a csupa 1-t tartalmazó sorozat.Továbbá jelölje $c_n$ egy minimális vágás értékét ebben a gráfban.
   1. Határozzuk meg $c_3$ értékét.
   2. HF $(*)$ Mennyi általában $c_n$ ?

3. Adjunk algoritmust arra, hogy hogyan lehet egy irányított gráf két rögzített pontja között maximális számú
   1. élidegen utat találni;
   2. pontidegen utat találni.

4. Egy hálózati folyam 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, ld. ábra.)Az éleket 1 vagy 2 kapacitásúnak választhatjuk meg a következo feltételek mellett: egyrészt az elérheto maximális folyam értéke legyen a lehető legnagyobb; másrészt a lehető legkevesebb 2 kapacitású élt használjuk fel. Hány 2 kapacitású élre van szükség és hogyan helyezzük el azokat? (ZH feladat)

5. Határozzuk meg az ábrán látható gráf élösszefüggőségi számát! Legalább hány új élet kell hozzávenni, hogy ez eggyel nőjön?

6. Egy összefüggő gráf legalább 3 pontot tartalmaz és bármely $e$ éléhez és $v$ pontjához található olyan kör, mely tartalmazza őket. Mutassuk meg, hogy a gráf kétszeresen összefüggő.

7. Bizonyítsuk be, hogy egy $G$ gráf akkor és csak akkor $k$-szorosan élösszefüggő, ha a csúcsoknak minden nem üres valódi $X$ részhalmazára az $X$-ből kilépő élek száma legalább $k$.

8. HF Határozzuk meg a maximális folyam értékét az alábbi gráfban, ahol pont- és élkapacitások is előfordulnak.

9. HF Határozzuk meg a nemnegatív valós $x$ függvényében az alábbi ábrákon látható hálózatokban a maximális folyam értékét.

10. HF Mutassunk olyan gráfot, amely 6-szorosan élösszefüggő, de csak egyszeresen pontösszefüggő.

11. HF Mutassuk meg, hogy egy $k$-szorosan összefüggő gráfnak legalább $kn/2$ éle van.

12. HF $(*)$ A háborúban a Ford gyár kifejlesztette az $FF$ szuperszámítógépet, mellyel folyamproblémákat hatékonyan lehet megoldani (maximális folyamot keresni). Az $FF$ gépet most békés célokra kívánják használni, ezért egy házasságközvetítőnek adták. Hogyan használható az $FF$ gép teljes párosítás keresésére páros gráfban?