\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\usepackage{graphics}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.4cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
7. feladatsor (2002. okt. 24.)}
\end{center}
\ \\
\begin{enumerate}
\item 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/halozat1.eps}}}
\hspace{15mm}
\raisebox{-30mm}{\resizebox{50mm}{!}{\includegraphics{abrak/halozat3.eps}}}
\]

\item 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.)

\item 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}}}
\]

\item \begin{enumerate} \item 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?

\item 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.)
\end{enumerate}

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

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

\item 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.)

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