\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.2cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
3. feladatsor (2002. szept. 26.)}
\end{center}
\ \\\ \\
Az előző óráról maradt:
\begin{enumerate}
\item Egy teljes gráf ponthalmaza
$\{x_1,x_2,...,x_s,y_1,y_2,...,y_t\}$. Az $\left(x_i,x_j\right)$
élek költsége (súlya) 1 Ft, az $\left(y_i,y_j\right)$ éleké 2 Ft,
az $\left(x_i,y_j\right)$ éleké pedig 3 Ft. Mennyibe kerül a
legolcsóbb feszítőfa? (ZH, 2000. márc.)

\item Hány olyan fa adható meg az $1,2,...,100$ csúcsokon, melynek
van olyan éle, amit elhagya a maradék gráf két komponensének
pontjai rendre az $1,2,...,50$ ill. az $51,52,...,100$ csúcsok?

\end{enumerate}\ \\
Új feladatok:
\begin{enumerate}
\item Van-e az alábbi gráfnak Hamilton-köre ill. -útja? (Vizsga,
2001. jún.)

\[
\unitlength 1mm
\begin{picture}(40,20)(-20,-10)
\put(-20,-10){\circle*{2}} \put(-10,-10){\circle*{2}}
\put(0,-10){\circle*{2}} \put(10,-10){\circle*{2}}
\put(20,-10){\circle*{2}} \put(-20,0){\circle*{2}}
\put(-10,0){\circle*{2}} \put(10,0){\circle*{2}}
\put(20,0){\circle*{2}} \put(-20,10){\circle*{2}}
\put(-10,10){\circle*{2}} \put(0,10){\circle*{2}}
\put(10,10){\circle*{2}} \put(20,10){\circle*{2}}
\put(-20,-10){\line(1,0){40}} \put(-20,0){\line(1,0){10}}
\put(10,0){\line(1,0){10}} \put(-20,10){\line(1,0){40}}
\put(-20,-10){\line(0,1){20}} \put(-10,-10){\line(0,1){20}}
\put(10,-10){\line(0,1){20}} \put(20,-10){\line(0,1){20}}
\end{picture}
\]

\item Hány Hamilton-köre ill. -útja van a $K_{n,n}$ teljes páros
gráfnak? (Vizsga, 1999. máj.)

\item A $G$ 3-reguláris egyszerű gráfra teljesül, hogy
$|E(G)|=2\cdot |V(G)|-3$. Bizonyítsuk be, hogy $G$-ben van
Hamilton-kör! (ZH, 1999. márc.)

\item A $G$ egyszerű gráf pontjai az $1,2,...,100$ számok. Az $i$
és $j$ pontok pontosan akkor vannak éllel összekötve, ha
$|\,i-j|\leq2$. Van-e $G$-ben Euler-kör ill. Euler-út? (ZH, 2000.
márc.)

\item A $G$ gráf pontjai egy 10 elemű halmaz 2 elemű
részhalmazainak felelnek meg. Két pont akkor van összekötve éllel,
ha a pontoknak megfelelő két részhalmaz \emph{diszjunkt}. Van-e a
$G$ gráfban Euler- ill. Hamilton-kör? (Pótzh, 1999. máj.)

\item Egy 12 fős társaságban mindenki legalább 6 embert ismer (az
ismeretség kölcsönös). Bizonyítsuk be, hogy a társaság leültethető
egy kerek asztal köré úgy, hogy mindenki ismerje a szomszédait!
(Pótzh, 2001. dec.)

\item A $G$ összefüggő gráfban minden pont foka páros. Bizonyítsa
be, hogy ha $G$-nek páros sok éle van, akkor létezik $G$-nek olyan
$H$ részgráfja, hogy $V(G)=V(H)$, és minden pont $H$-beli foka
éppen fele a $G$-beli fokának. (ZH, 2000. máj.)

\item Legyen $n\geq3$ és legyen a $G$ gráf pontjainak halmaza az
$n$ hosszúságú $0-1$ sorozatok halmaza. A gráf két pontja között
akkor és csak akkor van él, ha a nekik megfelelő két sorozat
legalább 2 helyen eltér. Milyen $n$ esetén van $G$-ben
Euler-körséta? (Vizsga, 2000. jún.)
\end{enumerate}
\end{document}
