\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.4cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
5. feladatsor (2002. okt. 10.)}
\end{center}
\ \\
\begin{enumerate}
\item Állapítsuk meg az alábbi gráf által szemléltetett
tevékenységekhez szükséges időt! Mely feladatok kritikusak?
\[
\unitlength1mm
\begin{picture}(30,14)(-5,-2)
\put(0,5){\circle*{2}} \put(5,0){\circle*{2}}
\put(5,10){\circle*{2}} \put(15,0){\circle*{2}}
\put(15,10){\circle*{2}} \put(20,5){\circle*{2}}
\put(0,5){\vector(1,-1){4.5}} \put(0,5){\vector(1,1){4.5}}
\put(5,10){\vector(0,-1){9.5}} \put(5,0){\vector(1,0){9.5}}
\put(5,0){\vector(1,1){9.5}} \put(5,10){\vector(1,0){9.5}}
\put(15,10){\vector(0,-1){9.5}} \put(15,0){\vector(1,1){4.5}}
\put(15,10){\vector(1,-1){4.5}}

\put(1.5,1){\makebox(0,0){5}} \put(1.5,9){\makebox(0,0){2}}
\put(3.5,5){\makebox(0,0){3}} \put(10,-2){\makebox(0,0){1}}
\put(8,6){\makebox(0,0){2}} \put(10,12){\makebox(0,0){4}}
\put(13.5,4){\makebox(0,0){3}} \put(18.5,1){\makebox(0,0){4}}
\put(18.5,9){\makebox(0,0){6}}
\end{picture}
\]

\item Határozzuk meg a mellékelt PERT-diagramokban a szükséges
időt és a kritikus tevékenységeket $S$ és $T$ között! (ZH, 2001.
máj. ill. dec.)

\[
\unitlength1mm
\begin{picture}(50,30)(-5,-5)
\put(0,10){\circle*{2}} \put(10,0){\circle*{2}}
\put(10,10){\circle*{2}} \put(10,20){\circle*{2}}
\put(30,0){\circle*{2}} \put(30,10){\circle*{2}}
\put(30,20){\circle*{2}} \put(40,10){\circle*{2}}
\put(0,10){\vector(1,-1){9.5}} \put(0,10){\vector(1,0){9.5}}
\put(0,10){\vector(1,1){9.5}} \put(10,0){\vector(0,1){9.5}}
\put(10,10){\vector(0,1){9.5}} \put(10,0){\vector(1,0){19.5}}
\put(10,0){\vector(2,1){19.5}} \put(30,10){\vector(-1,0){19.5}}
\put(30,10){\vector(-2,1){19.5}} \put(10,20){\vector(1,0){19.5}}
\put(30,0){\vector(0,1){9.5}} \put(30,10){\vector(0,1){9.5}}
\put(30,0){\vector(1,1){9.5}} \put(30,10){\vector(1,0){9.5}}
\put(30,20){\vector(1,-1){9.5}}

\put(-3,10){\makebox(0,0){S}} \put(4.5,3){\makebox(0,0){5}}
\put(6,12){\makebox(0,0){7}} \put(4.4,16.5){\makebox(0,0){9}}
\put(11.5,5){\makebox(0,0){4}} \put(11.5,15){\makebox(0,0){2}}
\put(19,-2){\makebox(0,0){1}} \put(22,4){\makebox(0,0){4}}
\put(19,12){\makebox(0,0){1}} \put(22,16){\makebox(0,0){4}}
\put(19,22){\makebox(0,0){1}} \put(28.5,5){\makebox(0,0){2}}
\put(28.5,15){\makebox(0,0){4}} \put(35.5,3){\makebox(0,0){9}}
\put(34,12){\makebox(0,0){7}} \put(35.5,17){\makebox(0,0){5}}
\put(43,10){\makebox(0,0){T}}
\end{picture}
\hspace{2cm}
\begin{picture}(30,30)(-5,-5)
\multiput(0,0)(10,0){3}{\circle*{2}}
\multiput(0,10)(10,0){3}{\circle*{2}}
\multiput(0,20)(10,0){3}{\circle*{2}}
\multiput(0,0)(0,10){3}{\vector(1,0){9.5}}
\multiput(10,0)(0,10){3}{\vector(1,0){9.5}}
\multiput(0,10)(10,0){3}{\vector(0,-1){9.5}}
\multiput(0,20)(20,0){2}{\vector(0,-1){9.5}}
\put(10,10){\vector(0,1){9.5}}
\multiput(0,0)(10,10){2}{\vector(1,1){9.5}}
\multiput(0,20)(10,-10){2}{\vector(1,-1){9.5}}

\put(-3,20){\makebox(0,0){S}} \put(5,22){\makebox(0,0){8}}
\put(15,22){\makebox(0,0){4}} \put(-1.5,15){\makebox(0,0){3}}
\put(6.5,16){\makebox(0,0){6}} \put(11.5,15){\makebox(0,0){1}}
\put(15,17){\makebox(0,0){6}} \put(21.5,15){\makebox(0,0){3}}
\put(5,12){\makebox(0,0){5}} \put(17,12){\makebox(0,0){10}}
\put(-1.5,5){\makebox(0,0){2}} \put(4,6){\makebox(0,0){3}}
\put(11.5,5){\makebox(0,0){5}} \put(17,6){\makebox(0,0){10}}
\put(21.5,5){\makebox(0,0){2}} \put(6,2){\makebox(0,0){8}}
\put(14,2){\makebox(0,0){4}} \put(23,0){\makebox(0,0){T}}
\end{picture}
\]

\item
\begin{enumerate}
\item Határozzuk meg ($a$ és $b$ függvényében) az ábrán látható
gráf által szemléltetett tevékenységhez szükséges időt.
($a,b\geq0$)

\[
\unitlength1mm
\begin{picture}(42,26)(-5,-5)
\put(0,8){\circle*{2}} \put(16,0){\circle*{2}}
\put(16,16){\circle*{2}} \put(32,8){\circle*{2}}
\put(0,8){\vector(2,-1){15.5}} \put(0,8){\vector(2,1){15.5}}
\put(16,0){\vector(2,1){15.5}} \put(16,16){\vector(2,-1){15.5}}
\put(16,0){\vector(0,1){15.5}}

\put(-3,8){\makebox(0,0){A}} \put(16,19){\makebox(0,0){B}}
\put(16,-3){\makebox(0,0){C}} \put(35,8){\makebox(0,0){D}}
\put(8,2){\makebox(0,0){2}} \put(8,14){\makebox(0,0){$a$}}
\put(18,8){\makebox(0,0){1}} \put(24,2){\makebox(0,0){$b$}}
\put(24,14){\makebox(0,0){1}}
\end{picture}
\]

\item Ismételjük meg az előző példát, ha $l(B,D)$ értékét 1-ről
3-ra változtatjuk.
\end{enumerate}

\item
\begin{enumerate}
\item Milyen a $K_n$ teljes gráf mélységi ill. szélességi
bejárása?

\item Mutassuk meg, hogy $K_4$ tetszőleges fája előáll egy
mélységi vagy szélességi bejárás fájaként! Igaz-e ugyanez
$K_5$-re?
\end{enumerate}

\item
\begin{enumerate}
\item Mutassuk meg, hogy páros gráf esetén szélességi kereséskor
nem találhatunk azonos szinten belüli éleket! (ZH, 1999. márc.)
\item Bizonyítsuk az állítás megfordítását: ha a $G$ összefüggő
gráf szélességi keresésekor nem kaptunk azonos szinten belüli
éleket, akkor $G$ páros gráf!
\end{enumerate}

\item Legfeljebb hány éle lehet egy $n$ pontú, egyszerű,
összefüggő gráfnak, ha egyik mélységi feszítőfájában van $n-1$
fokú pont? (ZH, 2001. jan.)

\item Legfeljebb hány éle lehet egy gráfnak, ha egyik mélységi
(DFS) keresőfája egy $n$ szintű, $2^n-1$ pontú teljes bináris fa?

\item Igaz-e, hogy ha egy páros gráfban van Hamilton-kör, akkor
van benne teljes párosítás is?
\end{enumerate}
\end{document}
