\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-1.2cm}
\addtolength\textwidth{3.0cm}
\addtolength\hoffset{0.2cm}
\addtolength\textheight{7.0cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
4. gyakorlat, 2006. március 8.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{10mm}
\textbf{\LARGE Párosítások}
\end{center}

\vspace{0.9cm}

\begin{enumerate}
\addtocounter{enumi}{34}

\item Egy vállalatnál hét pályázó jelentkezett hat üres munkahelyre, egy
ember esetleg több helyre is. Aladár az 1-es, Béla az 1-es és 6-os, Csaba
a 2-es, 3-as és 4-es, Dénes a 2-es és 5-ös, Elemér a 3-as, 4-es és 5-ös,
Ferenc az 1-es és 6-os végül Géza a 6-os munkahelyre. 
\begin{itemize}
\item Ábrázoljuk a helyzetet páros gráffal.
\item Döntsük el, hogy betölthető-e mind a hat munkahely. Ha nem mind,
akkor legfeljebb hány tölthető be?
\item Javít-e valamit, ha Ferencnek több pénzt ígérünk, és így elérjük,
hogy elfogadja a 2-es munkahelyet? 
\end{itemize}  

%\item Állapítsuk meg az előző feladatban szereplő páros gráf(ok)ban
%\begin{itemize}
%\item a minimális lefedő ponthalmazokat és ezek elemszámát.
%\item a maximális független ponthalmazokat és ezek elemszámát.
%\item a minimális lefogó élhalmazokat és ezek elemszámát.
%\item a maximális független élhalmazokat és ezek elemszámát.
%\end{itemize}

\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 ennek megfordítása?

\item Igazoljuk, hogy ha egy páros gráf $r$-reguláris (vagyis minden
csúcsának fokszáma $r$), akkor a gráfban van teljes párosítás.
%%%%% %%%%% Idén még nem volt kromatikus szám:
%Mit állíthatunk ezen gráfok élkromatikus számáról?

\item Egy páros gráf egyik pontosztályában van olyan $X$ részhalmaz,
melyre $|N(X)|\leqslant |X|-2$. Bizonyítsuk be, hogy a gráfban nincsen
Hamilton-út.

\item Mutassuk meg, hogy egy fának legfeljebb egy teljes párosítása van.

\item Igazoljuk, hogy ha egy gráfban van két teljes párosítás, akkor létezik
benne páros hosszúságú kör is.

\item Bizonyítsuk be, hogy ha egy páros gráf minden csúcsának fokszáma 4,
akkor van benne olyan kör, melynek hossza legalább 8.

\item Egy $2n$ csúcsú teljes gráfból elhagyjuk egy teljes párosítás éleit.
Hány különböző 3 hosszú kör található a maradék gráfban?

%\item Egy társaságban $\omega$ darab fiú és $\omega$ darab lány van úgy,
%hogy bármely $k$ darab fiú összesen legalább $k$ darab lányt ismer (ahol
%$\omega$ jelöli a megszámlálható számosságot). Igaz-e általánosan, hogy a
%fiúk összeházasíthatók különböző lányokkal (vigyázat: a végtelen rendesen
%belekavar a dologba)? 

%\item Legyenek $A_i (i=1,\ldots,n)$ illetve $B_i (i=1,\ldots,n)$ olyan
%$m$-elemű halmazok, amelyek ugyanazt a $T$ halmazt partícionálják ($T$
%nyilván $mn$ elemű). Igazoljuk, hogy van olyan $\sigma\in S_n$ permutáció,
%amelyre $A_i\cap B_{\sigma(i)}$ semmilyen $i$-re $(i=1,\ldots,n)$ nem
%üreshalmaz.

\item Legyen a nemnegatív elemű, négyzetes $A$ mátrix olyan tulajdonságú,
hogy minden sorában és minden oszlopában a számok összege 1 (amúgy
az ilyen mátrixot hívjuk duplán sztochasztikusnak). Mutassuk meg, hogy a
determinánsa tartalmaz nemnulla kifejtési tagot. 

\item Képzeljünk el egy szigetet, amely fel van parcellázva $n$ darab
azonos méretű vadászterületre, valamint $n$ azonos méretű mezőgazdasági
területre is (a két parcellázás nem feltétlenül esik egybe). Mutassuk meg,
hogy beköltöztethető $n$ lakó úgy, hogy mindenki egy vadászterület és egy
mezőgazdasági parcella fölött rendelkezzék, és mindenkhez található legyen
olyan szigetdarabka, melyet mindkét tevékenység szempontjából
birtokol.

\end{enumerate}

\end{document}
