\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.7cm}
\addtolength\textwidth{3.0cm}
\addtolength\hoffset{0.2cm}
\addtolength\textheight{7.0cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}
\usepackage{graphicx}

\begin{document}

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

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

\vspace{0.9cm}

\begin{enumerate}
\addtocounter{enumi}{39}

\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.
%Mit állíthatunk ezen gráfok élkromatikus számáról?
\item Határozzuk meg az $r$-reguláris páros gráfok élkromatikus számát.

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

\item Határozzuk meg a független élek maximális számát az alábbi két
gráfban. Bizonyítsuk be, hogy nem lehet többet találni! \vspace*{3mm}

\includegraphics[scale=0.5]{gallai1.eps} \hspace*{1cm}
\includegraphics[scale=0.5]{gallai2.eps}

\item Az $a_1, a_2 \ldots a_{2007}$ csúcsokból álló $G$ gráf $a_i$ és
$a_j$ pontja akkor van összekötve, ha $i+j$ osztható 3-mal (és $i\neq
j$). Határozzuk meg $\tau(G)$, $\nu(G)$, $\rho(G)$, $\alpha(G)$,
$\omega(G)$ értékét.

\item Bizonyítsuk be, hogy $\Delta(G)\cdot\tau(G)\geqslant |E(G)|$.

\item Igazoljuk, hogy $\alpha(G)\geqslant n-2\nu(G)$.

\item Bizonyítsuk be, hogy egy háromszögmentes $G$ gráfban
$\alpha(G)\cdot\tau(G)\geqslant |E(G)|$.

\item Mutassuk meg, hogy $\chi_e(G)+\nu(G)\leqslant e+1$.

%\item Bizonyítsuk be, hogy egy $G$ teljes páros gráfban (ahol tehát a két
%színosztály között minden él jelen van) mindig felláll, hogy
%$\nu(G)\cdot\rho(G)=|E(G)|$.

%\item Legyen $F$ egy maximális független ponthalmaz az egyszerű $G$ gráfban
%és legyen $F'$ egy független ponthalmaz $V(G)-F'$-ben. Bizonyítsuk be, hogy
%$\nu(G)\geqslant |F'|$.

\item Határozzuk meg véges egyszerű $G$ gráfokra a $\frac{\tau(G)}{\nu(G)}$ érték
lehető legkisebb és legnagyobb értékét.

%\item Minimálisan hány éle kell, hogy legyen egy 2000 csúcsú $G$ gráfnak, ha
%függetlenségi számára $\alpha(G)=5$ teljesül?

\end{enumerate}

\end{document}
