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

5. gyakorlat, 2007. március 14.

                               Koblinger Egmont <egmont@cs.bme.hu>

Folyamok

55. Adjuk meg az alábbi hálózatokban a maximális folyamot!

56. Osszunk szét három 1-es, három 2-es és három 3-as kapacitást az alábbi gráf élein úgy, hogy a maximális folyam a lehető

(a) legnagyobb

(b) legkisebb

legyen.

57. (a) Igaz-e, hogy ha egy irányított gráfban minden él kapacitása páros, akkor létezik olyan maximális

folyam, amelynek értéke minden élen páros?

(b) Ugyanez páros helyett mindenütt páratlannal.

58. Egy kisváros úthálózata csupa egyirányú utcából áll. A polgármester minden hétköznap reggel autóval megy otthonról a városházára. A fejébe veszi, hogy úgy szeretné ezt megtenni, hogy minden utcán egy hét alatt legfeljebb egyszer menjen végig (a hazafelé utak nem számítanak).

(a) Adjunk meg olyan algoritmust, amely a kisváros térképe alapján eldönti, hogy ez megtehető-e!

(b) Mi a helyzet, ha vannak kétirányú utcák is?

59. Legyenek egy irányított gráf pontjai az n ∈ ℤ^{+} hosszú 0–1 vektorok. Az a csúcsból akkor mutasson a b csúcsba él, ha a-ban kevesebb 1-es van, mint b-ben. Egy ilyen élre kapacitásként írjuk rá a-ban lévő egyesek száma és a b-ben lévő egyesek száma közti különbséget. Legyesn s = (0, 0, …, 0) és t = (1, 1, …, 1). Jelölje F_{n} a maximális folyam nagyságát. Számoljuk ki:

(a) F_{3} értékét!

(b) F_{n} értékét tetszőleges n ∈ ℤ^{+}-ra!

60. Adott egy város, ahol fiúk és lányok élnek, néhányan közülük barátságban vannak, ezek köthetnek házasságot. Továbbá a városban vannak közvetítő irodák is, és a fiúk (esetleg több) közvetítőhöz is beadták papírjaikat. Házasságot csak házasságközvetítő szervezhet, de egy közvetítő legfeljebb m-et. Mutassunk algoritmust, melynek segítségével meghatározható a városban köthető legtöbb házasság.