Számítástudomány elemei gyakorlat
7. feladatsor (2002. okt. 24.)

1. Adjunk meg az alábbi hálózatokban egy-egy maximális folyamot! (ZH, 2000. máj. és okt.)
   
   $$\raisebox{-30mm}{\resizebox{50mm}{!}{\includegraphics{abrak/... ...mm}{\resizebox{50mm}{!}{\includegraphics{abrak/halozat3.eps}}}$$
   
   

2. Legyenek egy gráf pontjai a 3 hosszúságú $0-1$ sorozatok. Vezessen egy irányított él $a$-ból $b$-be, ha $a$-ban kevesebb 1-es van, mint $b$-ben, és legyen egy ilyan él kapacitása az egyesek számának különbsége. Határozzuk meg a maximális folyam értékét $s=(0,0,0)$ és $t=(1,1,1)$ között! (Pótzh, 2001. máj.)

3. Határozzuk meg a maximális folyam értékét az alábbi hálózati folyamban $s$ és $t$ között az $x\geq0$ valós szám függvényében! (Vizsga, 2000. jún.)
   
   $$\raisebox{-15mm}{\resizebox{40mm}{!}{\includegraphics{abrak/halozat2.eps}}}$$
   
   

4. 1. Igaz-e, hogy ha egy hálózatban minden él kapacitása páros szám, akkor van olyan maximális folyam, aminek értéke minden élen páros szám?

   2. Igaz-e, hogy ha egy hálózatban minden él kapacitása páratlan szám, akkor van olyan maximális folyam, aminek értéke minden élen páratlan szám? (ZH, 2000. máj.)

5. Mutassuk meg, hogy egy háromszorosan összefüggő gráfban mindig létezik páros hosszúságú kör! (ZH, 2001. márc.)

6. Bizonyítsuk be, hogy egy 6-szorosan pontösszefüggő gráfot nem lehet síkba rajzolni! (ZH, 2001. jan.)

7. Legyen $G$ egy olyan egyszerű gráf, amelynek pontjai számozhatók úgy, hogy minden pont legfeljebb kettő nála nagyobb sorszámúval szomszédos. Igazoljuk, hogy $\chi(G)\leq3$, ahol $\chi(G)$ $G$ kromatikus számát jelenti. (Pótzh, 2001. máj.)

8. Bizonyítsuk be, hogy minden $G$ gráfban $\alpha(G)\chi(G)\geq \vert V(G)\vert$, ahol $\alpha(G)$ a független pontok maximális számát jelöli $G$-ben.