Next: About this document ...
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
- 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!
- Legyenek egy gráf pontjai az
hosszúságú
sorozatok. Vezessen irányított él
-ból
-be, ha
-ban kevesebb
-es van mint
-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
egy minimális vágás értékét ebben a gráfban.
- Határozzuk meg
értékét.
- HF
Mennyi általában
?
- 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ú
- élidegen utat találni;
- pontidegen utat találni.
- 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)
- 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?
- Egy összefüggő gráf legalább 3 pontot tartalmaz és bármely
éléhez és
pontjához található olyan kör, mely tartalmazza őket. Mutassuk meg, hogy a gráf kétszeresen összefüggő.
- Bizonyítsuk be, hogy egy
gráf akkor és csak akkor
-szorosan élösszefüggő, ha a csúcsoknak minden nem üres valódi
részhalmazára az
-ből kilépő élek száma legalább
.
- HF Határozzuk meg a maximális folyam értékét az alábbi gráfban, ahol pont- és élkapacitások is előfordulnak.
- HF Határozzuk meg a nemnegatív valós
függvényében az alábbi ábrákon látható hálózatokban a maximális folyam értékét.
- HF Mutassunk olyan gráfot, amely 6-szorosan élösszefüggő, de csak egyszeresen pontösszefüggő.
- HF Mutassuk meg, hogy egy
-szorosan összefüggő gráfnak legalább
éle van.
- HF
A háborúban a Ford gyár kifejlesztette az
szuperszámítógépet, mellyel folyamproblémákat hatékonyan lehet megoldani (maximális folyamot keresni). Az
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
gép teljes párosítás keresésére páros gráfban?
Next: About this document ...
Fogaras Daniel
2002-04-05