\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\\
6. feladatsor (2002. okt. 17.)}
\end{center}
\ \\
\begin{enumerate}
\item Keressünk maximális párosítást az alábbi gráfban! (Vizsga,
2001. jún.)
\vspace{2mm}
\[
\unitlength 1.2cm
\begin{picture}(4,1)
\multiput(0,0)(1,0){5}{\circle*{.2}}
\multiput(0,1)(1,0){5}{\circle*{.2}}
\multiput(0,0)(1,0){4}{\line(1,1){1}}
\multiput(0,1)(1,0){4}{\line(1,-1){1}}
\multiput(1,0)(2,0){2}{\line(0,1){1}}
\multiput(0,0)(1,0){2}{\line(3,1){3}}
\multiput(0,1)(1,0){2}{\line(3,-1){3}}
\end{picture}
\vspace{1mm}
\]

\item Egy osztályban az iskolai asztalitenisz-bajnokságra
fiúpárosokat szeretnének összeállítani. A tíz pingpongozni tudó
fiúból Andris és Balázs csak Marcival akar egy párban lenni, Csaba
és Dani Norbihoz, Ede és Karcsi pedig Oszihoz ragaszkodik. Laci
szívesen lenne Marcival, Norbival vagy akár Oszival is. Az utóbbi
három bárki oldalán kiállna, aki őket választja. Hány pár
állítható így össze?

\item Mekkora a maximális párosítás mérete a következő gráfban?
(ZH, 2001. márc.)
\[
\unitlength .5cm
\begin{picture}(14,8)
\put(4,0){\circle*{.4}} \put(10,0){\circle*{.4}}
\put(4,2){\circle*{.4}} \put(10,2){\circle*{.4}}
\put(14,2){\circle*{.4}} \put(2,3){\circle*{.4}}
\put(6,3){\circle*{.4}} \put(8,3){\circle*{.4}}
\put(12,3){\circle*{.4}} \put(2,5){\circle*{.4}}
\put(6,5){\circle*{.4}} \put(8,5){\circle*{.4}}
\put(12,5){\circle*{.4}} \put(0,6){\circle*{.4}}
\put(4,6){\circle*{.4}} \put(10,6){\circle*{.4}}
\put(4,8){\circle*{.4}} \put(10,8){\circle*{.4}}
\put(4,0){\line(0,1){2}} \put(10,0){\line(0,1){2}}
\put(2,3){\line(2,-1){2}} \put(4,2){\line(2,1){2}}
\put(6,3){\line(1,0){2}} \put(8,3){\line(2,-1){2}}
\put(10,2){\line(2,1){2}} \put(12,3){\line(2,-1){2}}
\put(2,3){\line(0,1){2}} \put(6,3){\line(0,1){2}}
\put(8,3){\line(0,1){2}} \put(12,3){\line(0,1){2}}
\put(0,6){\line(2,-1){2}} \put(2,5){\line(2,1){2}}
\put(4,6){\line(2,-1){2}} \put(6,5){\line(1,0){2}}
\put(8,5){\line(2,1){2}} \put(10,6){\line(2,-1){2}}
\put(4,6){\line(0,1){2}} \put(10,6){\line(0,1){2}}
\end{picture}
\]

\item Adott egy $G=(A,B)$ egyszerű páros gráf, ahol az osztályok
$|A|=3,\;|B|=n\geq3$ méretűek, és az élek száma $|E(G)|=2n+1$.
Bizonyítsuk be, hogy van $G$-nek olyan párosítása, mely lefedi az
$A$ osztályt! (ZH, 2000. márc.)

\item A $G=(A,B,E)$ páros gráfra $|A|=|B|$, és az $A$ minden
valódi $X$ részhalmazára $(X\ne\emptyset,\;X\ne A)$ teljesül, hogy
$|X|<|N(X)|$, ahol $N(X)$ az $X$ szomszédainak halmazát jelöli.
Igazoljuk, hogy ekkor $G$ egy tetszőleges éle kiegészíthető teljes
párosítássá! (Vizsga, 1999. máj.)

\item Mutassa meg, hogy egy fának nem lehet két különböző teljes
párosítása! (Vizsga, 2001. jún.)

\item Bizonyítsuk be, hogy ha egy $n$ pontú páros gráfban létezik
teljes párosítás, akkor $\alpha=\frac{n}2$, ahol $\alpha$ a
független pontok maximális számát jelöli. (Pótzh, 2001. dec.)
\end{enumerate}
\end{document}
