Bevezetés a számításelméletbe II.
6. gyakorlat 2003 március 21.
Menger tételei
- Az a) ábrán látható gráf egy térképet mutat, ahol
egy kirabolt bankot,
pedig Ausztriát jelöli. Minimálisan hány kereszteződésbe kell rendőrt állítani, hogy a bankot éppen elhagyó rablót még az országon belül biztosan elkapják? (Természetesen
-ba és
-be nem állíthatunk rendőrt.)
- A b) ábrán
,
,
,
jelöli a bankrabló lehetséges tartózkodási helyeit, továbbá
,
,
és
a szomszédos országok határátkelőit. Hány utat kell minimálisan lezárni, hogy a rabló ne szökhessen külföldre?
- 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
?
- Mutassunk olyan gráfot, amely 6-szorosan élösszefüggő, de csak egyszeresen pontösszefüggő.
- Mutassuk meg, hogy egy gráf akkor és csak akkor kétszeresen (pont)összefüggő, ha bármely két pontjához található olyan kör, amelyik mindkettőn keresztülhalad!
- Mutassuk meg, hogy egy
-szorosan összefüggő gráfnak legalább
éle van.
- Határozzuk meg, hogy melyik az a legnagyobb
szám, amire még
-szorosan élösszefüggő az alábbi gráf! Legalább hány új élet kell hozzávenni, hogy ez eggyel nőjön?
- (korábbi feladatsorból) Egy társaságban van tíz olyan lány, akik közül bármely kettő különböző számú, de legalább egy fiút kedvel a társaságból. Mutassuk meg, hogy a tíz lány egyszerre tud keringőzni úgy, hogy mindegyikük kedvére való fiúval táncoljon!
- (korábbi feladatsorból) Egy egyszerű
gráfnak 1000 pontja van és,
bármely pontnak a foka legalább 6.
- Mutassuk meg, hogy
!
- Mutassunk példát olyan a feladat feltételeit kielégítő
-re, ahol
?
Fogaras Daniel
2003-03-21