\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\usepackage{graphics}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.4cm}
\addtolength{\textheight}{1cm} \addtolength{\topmargin}{-.5cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
4. feladatsor (2002. okt. 3.)}
\end{center}
\ \\
\begin{enumerate}
\item Síkba rajzolhatók-e a következő gráfok? Ha igen, rajzold le
élkereszteződés nélkül; ha nem, mutass bennük egy
Kuratowski-gráffal topologikusan izomorf részgráfot!

\[
\unitlength 1.3mm
\raisebox{1cm}{\hbox{$\left(\textup{a}\right)$\ \ }}
\raisebox{5mm}{
\begin{picture}(20,10)
\multiput(0,0)(10,0){3}{\circle*{1.5}}
\multiput(0,10)(10,0){3}{\circle*{1.5}} \put(5,5){\circle*{1.5}}
\multiput(0,0)(10,0){3}{\line(0,1){10}}
\multiput(0,0)(10,0){2}{\line(1,1){10}}
\multiput(0,10)(10,0){2}{\line(1,-1){10}}
\put(0,0){\line(2,1){20}} \put(0,10){\line(2,-1){20}}
\end{picture}}
\hspace{10mm} \raisebox{1cm}{\hbox{$\left(\textup{b}\right)$\ }}
\resizebox*{!}{25mm}{\includegraphics{abrak/sikbarajz_k5_felosztva.eps}}
\hspace{10mm} \raisebox{1cm}{\hbox{$\left(\textup{c}\right)$\ }}
\resizebox*{!}{25mm}{\includegraphics{abrak/sikbarajz_k5_pluszpont.eps}}
\]
\[
\ \unitlength 10mm
\raisebox{1.5cm}{\hbox{$\left(\textup{d}\right)$\ \ }}
\begin{picture}(3,3)
\multiput(1,0)(1,0){2}{\circle*{.2}}
\multiput(1,3)(1,0){2}{\circle*{.2}}
\multiput(0,1)(0,1){2}{\circle*{.2}}
\multiput(3,1)(0,1){2}{\circle*{.2}}
\multiput(1,0)(0,3){2}{\line(1,0){1}}
\multiput(0,1)(3,0){2}{\line(0,1){1}}
\multiput(0,1)(2,2){2}{\line(1,-1){1}}
\multiput(2,0)(-2,2){2}{\line(1,1){1}} \put(1,0){\line(1,3){1}}
\put(0,1){\line(3,1){3}} \put(0,2){\line(3,-1){3}}
\put(1,3){\line(1,-3){1}}
\end{picture}
\hspace{1cm} \raisebox{1.5cm}{\hbox{$\left(\textup{e}\right)$\ \
}}
\begin{picture}(3,3)
\multiput(1,0)(1,0){2}{\circle*{.2}}
\multiput(1,3)(1,0){2}{\circle*{.2}}
\multiput(0,1)(0,1){2}{\circle*{.2}}
\multiput(3,1)(0,1){2}{\circle*{.2}}
\multiput(1,0)(0,3){2}{\line(1,0){1}}
\multiput(0,1)(3,0){2}{\line(0,1){1}}
\multiput(0,1)(2,2){2}{\line(1,-1){1}}
\multiput(2,0)(-2,2){2}{\line(1,1){1}}
\multiput(0,1)(0,1){2}{\line(1,0){3}}
\multiput(0,2)(1,-2){2}{\line(2,1){2}}
\multiput(0,1)(1,2){2}{\line(2,-1){2}}
\end{picture}
\hspace{1cm} \raisebox{1.5cm}{\hbox{$\left(\textup{f}\right)$\ \
}}
\begin{picture}(3,3)
\multiput(1,0)(1,0){2}{\circle*{.2}}
\multiput(1,3)(1,0){2}{\circle*{.2}}
\multiput(0,1)(0,1){2}{\circle*{.2}}
\multiput(3,1)(0,1){2}{\circle*{.2}}
\multiput(1,0)(0,3){2}{\line(1,0){1}}
\multiput(0,1)(3,0){2}{\line(0,1){1}}
\multiput(0,1)(2,2){2}{\line(1,-1){1}}
\multiput(2,0)(-2,2){2}{\line(1,1){1}}
\multiput(1,1)(1,0){2}{\circle*{.2}}
\multiput(1,2)(1,0){2}{\circle*{.2}}
\multiput(0,1)(0,1){2}{\line(1,0){3}}
\multiput(1,0)(0,2){2}{\line(1,1){1}}
\multiput(1,1)(0,2){2}{\line(1,-1){1}}
\end{picture}
\]
\rule{0mm}{0mm}

\item Legyenek a $G_n$ gráf csúcsai az $\{1,2,...,n\}$ számok, és
két csúcs pontosan akkor legyen összekötve, ha a nekik megfelelő
számok egyike osztója a másiknak. Bizonyítsuk be, hogy $n\geq16$
esetén $G_n$ nem síkba rajzolható! (Pótzh, 2001. máj.)

\item Egy hatelemű halmaz kételemű részhalmazai legyenek egy gráf
pontjai. Két pont akkor legyen összekötve éllel, ha a nekik
megfelelő részhalmazok diszjunktak (metszetük üres). Síkba
$\textup{rajzolható-e}$ ez a gráf?

\item Hány csúcsa van annak a $G$ összefüggő 4-reguláris
síkgráfnak, amelynek a síkba rajzolásakor 10 tartomány keletkezik?
(Vizsga, 2001. dec.)

\item Egy 20 csúcsú konvex poliéder lapjainak száma 12. Hány
oldala van az egyes lapoknak, ha tudjuk, hogy ez a szám minden
lapra azonos? Melyik ez a poliéder?

\item Keress gyengén izomorfakat az alábbi gráfok között!
\[
\raisebox{.6cm}{\hbox{$\left(\textup{a}\right)$\ }}
\resizebox*{!}{1.4cm}{\includegraphics{abrak/gyenge_izomorfia_1.eps}}
\hspace{4mm} \raisebox{.6cm}{\hbox{$\ \left(\textup{b}\right)$\ }}
\resizebox*{!}{1.4cm}{\includegraphics{abrak/gyenge_izomorfia_2.eps}}
\hspace{4mm} \raisebox{.6cm}{\hbox{$\ \left(\textup{c}\right)$\ }}
\resizebox*{!}{1.4cm}{\includegraphics{abrak/gyenge_izomorfia_3.eps}}
\hspace{4mm} \raisebox{.6cm}{\hbox{$\ \left(\textup{d}\right)$\ }}
\resizebox*{!}{1.7cm}{\includegraphics{abrak/gyenge_izomorfia_4.eps}}
\hspace{4mm} \raisebox{.6cm}{\hbox{$\ \left(\textup{e}\right)$\ }}
\resizebox*{!}{1.7cm}{\includegraphics{abrak/gyenge_izomorfia_5.eps}}
\]

\item
\begin{enumerate}
\item Rajzoltam egy nyolc csúcsú fát. Mi lehet a duálisa?

\item Bizonyítsd be, hogy tetszőleges két $n$ csúcsú fa gyengén
izomorf egymással!
\end{enumerate}

\item Legyen $G$ egy 20 pontú, összefüggő, 3-reguláris síkgráf.
Hány pontja van $G$ duálisának, $G^*$-nak? (ZH, 2001. máj.)

\item Egy nemzetközi konferencián egy asztalnál öt különböző
ország egy-egy képviselője ül. Bizonyítsuk be, hogy van közöttük
kettő, akiknek az országa nem szomszédos!
\end{enumerate}
\end{document}
