\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{-2.5cm}
\addtolength\textwidth{4.0cm}
\addtolength\hoffset{-0.3cm}
\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}
3. gyakorlat, 2007. február 28.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Perfekt gráfok – Színezések 2. – Pert módszer}
\end{center}

\vspace{5mm}

\begin{enumerate}

\addtocounter{enumi}{26}

\item Bizonyítsuk be, hogy az összehasonlítási gráfok perfektek.

\item Bizonyítsuk be, hogy egy intervallumgráf komplementere
összehasonlítási gráf.

\item Mutassunk olyan nem perfekt gráfot, amelyre $\chi (G)=\omega (G)$.

\item Legyenek egy gráf csúcsai a számok $1$-től $n$-ig, és két (különböző)
csúcs akkor legyen összekötve, ha ez egyik osztója a másiknak. Bizonyítsuk
be, hogy az így kapott gráf minden $n$-re perfekt!

\item Adott a síkon néhány körvonal, ezekhez
rendeljük a következő $G$ gráfot. $G$ csúcsai feleljenek meg
egy-egy adott körvonalnak, és kettő akkor legyen összekötve, ha a
két megfelelő körvonal egyike teljesen a másik belsejében halad.
Bizonyítsuk be, hogy az így megadott $G$ gráf perfekt.

\vspace*{5mm}

\item Mennyi a Petersen-gráf élkromatikus száma?

\item Legyen $G$ egy 100-reguláris egyszerű gráf 2007 ponton. Határozzuk meg
$\chi_e(G)$ értékét.

\item Határozzuk meg $K_n$ élkromatikus számát. Mutassunk is egy jó
élszínezést.

\item $n$ csapat körmérkőzést szeretne játszani (mindegyik csapat
mindegyikkel egy meccset). Legalább hány forduló szükséges ennek
lebonyolításához? (Egy fordulóban több pályán is folyhat párhuzamosan
mérkőzés.)

%%%\item Mennyi az élkromatikus száma egy $r$-reguláris páros gráfnak?
%%% Ehhez kell a teljes párosítás, ami idén még nem volt.

\item Legyen $G$ egy olyan 3-reguláris, egyszerű gráf, melyben van elvágó
él. Mutassuk meg, hogy $\chi_e(G)=4$.

\vspace*{5mm}

\item Állapítsuk meg a feladat elvégzéséhez minimálisan szükséges
idő hosszát az alábbi PERT diagramon:
\begin{center}
\includegraphics{pert1.eps}
\end{center}

\item Állapítsuk meg, hogy a $p$ paraméter függvényében mennyi
a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT diagram által
leírt munkafolyamatnál! Melyek a kritikus tevékenységek?
\begin{center}
\includegraphics{pert2.eps}
\end{center}

\item A $G$ irányított gráf csúcsai legyenek egy $n$ elemű halmaz összes
részhalmazai. Az $A$ részhalmazból akkor vezessen egy irányított él a $B$
részhalmazba, ha $A \subset B$, de $A \neq B$. Az $A$-ból $B$-be vezető
élhez rendeljük hozzá az $|A|+|B|$ értéket. Határozzuk meg az így kapott
PERT feladatban a szükséges időt és a kritikus tevékenységeket!

\end{enumerate}

\end{document}
