\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage[magyar]{babel}
%\usepackage[mathscr]{eucal}
\usepackage{stmaryrd}

\setlength{\hoffset}{-2 cm}
\setlength{\voffset}{-1 cm}
\addtolength{\textwidth}{5 cm}
\addtolength{\textheight}{8 cm}

\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
6. Gyakorlat
}
\end{center}

\large

\begin{enumerate}

\item Egy vállalatnál hét pályázó jelentkzett hat üres munkahelyre,
számozzuk ezeket 1-től 6-ig. Egy ember több munkahelyre is: Aladár 1;
Béla 1, 6; Csaba 2, 3, 4; Dani 2, 5; Erzsi 3, 4, 5; Feri 1, 6; Géza
6. Döntsük el, hogy betölthető-e mind a hat munkahely (egy ember csak
egy helyre kerülhet). Ha nem, legfeljebb hány munkahely tölthető be?
Javít-e valamit, ha Feri meggondolja magát, és a második munkahelyet
is hajlandó elfogani?

\item Igaz-e hogy ha egy összefüggő páros gráfban van
Hamilton-kör, akkor van teljes párosítás is? Igaz-e az állítás megfordítva?

\item Bizonyítsuk be, hogy reguláris páros gráfban van teljes párosítás.

\item Igazoljuk, hogy egy fának nem lehet két különböző teljes
párosítása.

\item Legyen $G=(A,B)$ egyszerű összefüggő páros gráf, $|A|=|B|$, és
minden $A$-beli pont foka különböző. Mutassuk meg, hogy van teljes
párosítás.

\item Egy $G=(A,B)$ páros gráfban létezik olyan $X\subseteq A$
ponthalmaz, amelyre $|N(X)| \leq |X|-2$. Bizonyítsuk be, hogy a
gráfban nincs Hamilton-út.

\item Hagyjunk el $K_{2n}$-ből egy teljes párosítást! Hány háromszög
van a megmaradt gráfban?

\item Mennyi $\nu, \rho, \tau, \alpha$ a háromszög-, négyzet-,
$\boxslash$, $K_{n,m}$, Petersen-gráfokon? 

\item Igazoljuk, hogy bármely $G$ gráfra $\Delta\cdot\tau\geq e$

\item Igaz-e, hogy hurokmentes gráfban $\alpha\tau\geq e$.

\item Legyen $F_1$ és $F_2$ fét független élhalmaz egy $G$
gráfban. Mutassuk meg, hogy az $(F_1 \cup F_2)\setminus(F_1
\cap F_2)$ élhalmaz által meghatározott részgráf összefüggő
komponensei utak és körök.

\item (nehéz) Igaz-e, hogy 3-reguláris összefüggő páros gráfban van Hamilton-kör?

\end{enumerate}

\end{document}










