\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage[latin2]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage[mathscr]{eucal}
\usepackage{graphics}


\newcommand{\Conj}[1]{\overline{#1}}
\newcommand{\Halm}[1]{\mathbbm{#1}}

\newcommand{\V}{\underline}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\Lek}[1]{{\cal #1}}
\newcommand{\im}{\mathop{\mathrm{Im}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}}

\newcommand{\mo}{{\bf Megoldás:}\\}

\addtolength{\textwidth}{5cm}
\addtolength{\textheight}{6cm}
\setlength{\hoffset}{-2.5cm}
\setlength{\voffset}{-3cm}


\frenchspacing

\begin{document}
\begin{center}
{\LARGE \bf Bevezetés a számításelméletbe (kieg.)}\\
{\bf Vizsgazárthelyi, 2002. 02. 01.}
\end{center}
\Large


\begin{enumerate}

\item Oldjuk meg a lineáris egyenletrendszert!
\[ x+4y=0 \]
\[ 3x+5y+8z=0 \]
\[ -y+z=1 \]

\mo
Vonjuk ki az első egyenlet háromszorosát a második egyenletből, 
így kiesik abból $x$. Vonjuk ki ezután az előbb kapott sorból 
az utolsó $8$-szorosát. Ekkor ,,tilos sor'' keletkezett, hiszen 
a második egyenletből minden változó kiesett, míg jobb oldalán 
nem $0$ áll.

\item Igazoljuk, hogy a három dimenziós vektortérben bázist alkot 
a következő három vektor: 
\[
\left(\begin{array}{c}
1\\2\\5
\end{array}\right)\hbox{, }
\left(\begin{array}{c}
6\\20\\7
\end{array}\right)\hbox{, }
\left(\begin{array}{c}
4\\15\\1
\end{array}\right)\hbox{.}
\]

\mo
Elegendő ellenőriznünk, hogy lineárisan függetlenek a fenti vektorok.
Ez pedig azzal ekvivalens, hogy a belőlük, mint oszlopokból képzett mátrix
determinánsa nem 0 (pl a mátrix rangjára vonatkozó tétel miatt).
A fenti determináns értéke 9, tehát valóban bázis a három vektor.

\item Hozzuk trigonometrikus alakra az $z = (1+\sqrt{3}i)^2$ komplex számot.

\mo
Érdemes a négyzetre emelés előtt elvégezni a trigonometrikus alakra 
alakítást. Abszolútértéke $\sqrt{1^2+\sqrt{3}^2} = 2$. 
Tehát $z = \left(2\left(\frac12+\frac{\sqrt3}{2}i\right)\right)^2$.
Vegyük észre, hogy $\frac12=\cos\frac{\pi}{3}$, és ezért 
$z = 4\left(\cos\frac{\pi}{3}+i\sin\frac{\pi}{3}\right)^2$. 
A trigonometrikus alak hatványozását most már könnyű elvégezni:
$z = 4\left(\cos\frac{2\pi}{3}+i\sin\frac{2\pi}{3}\right)^2$. 

\item Legalább hány élet kell hozzávenni a Petersen-gráfhoz, hogy a 
keletkező gráfban legyen Euler (!) kör?

\mo
A Petersen gráfnak 10 darab páratlan fokú csúcsa van. Élek behúzásával 
ezeket kell páros fokúvá tenni. Egy él legfeljebb két páratlan fokú
csúcsot ,,javíthat meg''. Tehát 5 élre biztosan szükségünk van. De 
ha mindig két olyan csúcsot kötünk össze, amely páratlan fokú, akkor 
5 éllel minden csúcsot páros fokúvá tehetünk, így a tétel szerint 
lesz benne Euler kör.

\item Mennyi a maximális $s \rightarrow t$ folyam az alábbi gráfban:
\begin{center}
\includegraphics{vizsgazh3foly.eps}
\end{center}

\mo
22

\item Adjunk felső becslést egy síkbarajzolható gráf éleinek számára, ha
minden körének hossza legalább $k$ ($k \geq 3$ rögzített természetes szám).

\mo
Vezessük be a következő jelöléseket: legyen gráfunk élszáma $e$, 
csúcsszáma $n$, tartományainak száma $l$, az egyes tartományokat 
határoló élek száma valamilyen sorrendben $t_1$, $t_2$,\dots, $t_l$.
Mivel egy tartomány határa kört alkot, ezért $\forall i$ $t_i\ge k$.
Így teljesül, hogy $2e=\sum_{i=1}^lt_i\ge\sum_{i=1}^lk=kl$, 
tehát $\frac{2e}{k}\ge l$. Az Euler képletbe $l$ helyére írjuk be ezt, 
akkor: $e=l+n-2\le\frac{2e}{k}+n-2$, átrendezve $e\le \frac{n-2}{k-2}k$.

\end{enumerate}

Minden feladat 10 pontot ér. Részeredményekért is jár pont, 
bizonyítás nélküli eredményközlésért azonban nem. Ponthatárok: 
0--23: 1; 24--32: 2; 33--42: 3; 43--51: 4; 52--60: 5.
\end{document}
