Bevezetés a számításelméletbe II.
Zárthelyi feladatok
2001. március 29.

  1. Legyenek a $G_n$ gráf pontjai az $n$ hosszú (0,1) sorozatok, két pont akkor legyen szomszédos, ha pontosan egy helyen térnek el egymástól (pl. az $n=4$ esetben (0,0,0,1) és (0,1,0,1) szomszédosak). Van-e a $G_n$ gráfnak Euler-köre?
  2. Legyen a $G_n$ gráf ugyanaz, mint az előző feladatban. Van-e $G_n$-nek Hamilton-köre?
  3. A $G$ egyszerű gráfnak $2k+1$ csúcsa van és minden csúcsának legalább $k$ a foka. Bizonyítsuk be, hogy $G$-ben van Hamilton-út!
  4. Mutassuk meg, hogy minden egyszerű síkba rajzolható $n$ pontú $G$ gráfra $\alpha(G) \ge n/4$ (ahol $\alpha(G)$ a $G$ gráf független pontjainak maximális száma).
  5. Legyen a $H$ gráf csúcshalmaza $V = \{1,2, \ldots, 2001\}$, és az $i, j \in V$ csúcsok között pontosan akkor menjen él, ha az $i+j$ szám 3-mal osztva 1 maradékot ad. Határozzuk meg a következő értékeket: $\chi(H)$, $\nu(H)$, $\rho(H)$, $\tau(H)$, $\alpha(H)$
  6. Adjunk meg az alábbi hálózatban egy maximális folyamot!
    \includegraphics{folyam.eps}

  7. A $G(V,E)$ összefüggő gráfban minden $v \in V$ ponthoz és $e \in E$ élhez van olyan kör, amely $v$-n is és $e$-n is átmegy. Mutassuk meg, hogy a $G$ gráf kétszeresen összefüggő!
  8. Állapítsuk meg, hogy mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT diagram által leírt munkafolyamatnál!
    \includegraphics{pert.eps}



Bevezetés a számításelméletbe II.
Zárthelyi feladatok
2001. május 3.


  1. Legyen $G$ egy egyszerű páros gráf és jelölje $A$ a $G$ szomszédsági mátrixát. Mutassuk meg, hogy ha $G$-ben nincs teljes párosítás, akkor $\det A = 0$ !
  2. Oldjuk meg a $6x \equiv 9\!\!\!\!\pmod{15}$ kongruenciát!
  3. Mi az utolsó két számjegye (a tízes számrendszerben) az alábbi számnak:

    \begin{displaymath}1997^{\textstyle 2001^{\textstyle 2005}} \end{displaymath}

  4. Határozzuk meg az összes olyan $m$ természetes számot és $p$ prímszámot, melyekre $\varphi(m) = \varphi(pm)$ teljesül!
  5. Bizonyítsuk be, hogy tetszőleges $p > 5$ prímszám az 1, 11, 111, 1111, $\ldots$ számok közül végtelen soknak osztója!
  6. Legyen a valós számok halmazán $a * b = a b + a + b$. Vizsgáljuk meg, hogy ez a művelet asszociatív-e, kommutatív-e, van-e neutrális eleme (más néven egységeleme) és hogy invertálható-e.
  7. Legyen $n \ge 4$. Az $n$ hosszú 0-1 sorozatok $H_1$ halmazán jelölje $+$ a modulo 2 összeadást, azaz legyen $a_1 a_2 \ldots a_n + b_1 b_2 \ldots b_n = c_1 c_2 \ldots c_n$ ha $c_i \equiv a_i + b_i\!\!\!\!\pmod{2}$ teljesül minden $1 \le i \le n$ esetén. Álljon $H_2$ azokból a 0-1 sorozatokból, amelyekben az egyesek száma kettővel osztható, $H_3$ pedig azokból, amelyekben az egyesek száma hárommal osztható. Az előbb definiált művelettel csoport-e $H_2$ ? Csoport-e $H_3$ ?
  8. Igazoljuk, hogy egy csoport nem állhat elő mint két valódi részcsoportjának uniója!