Bevezetés a számításelméletbe II.
6. gyakorlat 2003 március 21.
 
 
Menger tételei

 

1. 1. Az a) ábrán látható gráf egy térképet mutat, ahol $B$ egy kirabolt bankot, $A$ 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 $A$-ba és $B$-be nem állíthatunk rendőrt.)
   2. A b) ábrán $B_1$, $B_2$, $B_3$, $B_4$ jelöli a bankrabló lehetséges tartózkodási helyeit, továbbá $A$, $H$, $S$ és $R$ 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?
   
   
   
   
   
   
   
   
   
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. Mutassunk olyan gráfot, amely 6-szorosan élösszefüggő, de csak egyszeresen pontösszefüggő.
4. 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!
5. Mutassuk meg, hogy egy $k$-szorosan összefüggő gráfnak legalább $kn/2$ éle van.
6. Határozzuk meg, hogy melyik az a legnagyobb $k$ szám, amire még $k$-szorosan élösszefüggő az alábbi gráf! Legalább hány új élet kell hozzávenni, hogy ez eggyel nőjön?
   
   
   
   
   
   
   
   
7. (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!
8. (korábbi feladatsorból) Egy egyszerű $G$ gráfnak 1000 pontja van és, bármely pontnak a foka legalább 6.
   1. Mutassuk meg, hogy $\nu(G) \ge 6$!
   2. Mutassunk példát olyan a feladat feltételeit kielégítő $G$-re, ahol $\nu(G) = 6$?