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

  1. Legyen $G$ a $V=\{p_1, p_2, \ldots, p_{2001} \}$ ponthalmazon egy olyan egyszerű gráf, amelyben $\{p_i,p_j\} \in E$ pontosan akkor teljesül, ha $\vert i - j\vert \le 2$.
    a) Van-e $G$-ben Euler-kör vagy Euler-út?
    b) Van-e $G$-ben Hamilton-kör vagy Hamilton-út?
  2. Legyen $V = \{ 1, 2, \ldots, 74\}$ a $H$ gráf ponthalmaza, az $i$ és $j$ pontok között akkor menjen él, ha $i+j$ és 74 relatív prímek. Határozzuk meg a $\chi(H)$, $\alpha(H)$, $\nu(H)$, $\rho(H)$, $\tau(H)$ értékeket!
  3. Á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?
    \includegraphics{pert1.eps}
  4. Adjunk meg az alábbi hálózatban egy maximális folyamot!
    \includegraphics{folyam1.eps}
  5. Bizonyítsuk be, hogy ha a $k$-szorosan pontösszefüggő $G$ gráf egy élét elhagyjuk, akkor a kapott $G'$ gráf $(k-1)$-szeresen pontösszefüggő lesz.
  6. Legyen $a$ páratlan $b$ pedig páros szám. Igazoljuk, hogy ha $a^2 + b^2$ négyzetszám, akkor $b$ osztható néggyel!
  7. Oldjuk meg a $2001 x \equiv 3 \!\!\!\pmod{12}$ kongruenciát!
  8. A 2001 rendű $G$ csoportnak $H$ egy 69 rendű részcsoportja. Bizonyítsuk be, hogy ha $H$ normálosztó $G$-ben, akkor a $G/H$ faktorcsoport kommutatív!

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

  1. Legyen $V = \{ 1, 2, \ldots, 74\}$ a $H$ gráf ponthalmaza, az $i$ és $j$ pontok között akkor menjen él, ha $i+j$ és 74 relatív prímek és $i \ne j$. Van-e $H$-ban Hamilton-kör?
  2. Legyen $G$ a $V=\{p_1, p_2, \ldots, p_{2001} \}$ ponthalmazon az a gráf, amelyben $\{p_i,p_j\} \in E$ pontosan akkor teljesül, ha $0 < \vert i - j\vert \le 2$. Határozzuk meg $\chi(G)$ értékét!
  3. Legyen $G$ egy olyan egyszerű gráf, amelynek 1000 csúcsa van és minden csúcs fokszáma legalább 6. Igazoljuk, hogy $\nu(G) \ge 6$.
  4. Á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! Melyek a kritikus tevékenységek?
    \includegraphics{pert2.eps}
  5. Az alábbi hálózatban az x paraméter értékétől függően adjunk meg egy maximális folyamot!
    \includegraphics{folyam2.eps}

  6. Legyen $a$ egy 2001-hez relatív prím egész szám. Bizonyítsuk be, hogy ekkor $(a^{28} -1) (a^{24}-a^{22}-a^2+1)$ osztható 2001-gyel! (2001 prímfelbontása:
    $2001 = 3 \cdot 23 \cdot 29$)
  7. Oldjuk meg az $56 x \equiv 28 \!\!\!\pmod{36}$ kongruenciát!
  8. Legyen a $G$ csoport elemeinek halmaza $\{1,2,3,4,5,6 \}$, a művelet a $\pmod{7}$ szorzás. Igazoljuk, hogy a $G$ csoport ciklikus!

Bevezetés a számításelméletbe II.
Vizsgazárthelyi feladatok
2001. június 13.

  1. Legyen $G$ a $V=\{p_1, p_2, \ldots, p_{2001} \}$ ponthalmazon az a gráf, amelyben $\{p_i,p_j\} \in E$ pontosan akkor teljesül, ha $0 < \vert i - j\vert \le 2$. Határozzuk meg $G$ élkromatikus számát, azaz $\chi_e(G)$ értékét!
  2. Legyen $G_0$ egy irányított gráf. A $G_1$ gráfot úgy kaptuk $G_0$-ból, hogy néhány él irányítását megfordítottuk. Jelölje $B_0$, illetve $B_1$ a két gráf illeszkedési mátrixát (a csúcsokat és az éleket ugyanolyan sorrendben vettük mindkét esetben). Bizonyítsuk be, hogy $B_0 B_0^T = B_1 B_1^T$.
  3. Á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?
    \includegraphics{pert3.eps}
  4. Az alábbi hálózatban adjunk meg egy maximális folyamot!
    \includegraphics{folyam3.eps}

  5. Az $n$ pontú egyszerű $G$ gráfban minden olyan $a \ne b$ csúcsra melyek nincsenek éllel összekötve teljesül, hogy $d(a) + d(b) \ge n+1$. Igazoljuk, hogy $G$ minden $e$ éléhez van $e$-n átmenő Hamilton-kör! ($d(a)$ az $a$ pont fokszámát jelöli.)
  6. Bizonyítsuk be, hogy ha $a$ egy páratlan pozitív egész szám, akkor $a^4 - 26 a^2 + 25$ osztható 64-gyel!
  7. Oldjuk meg a $168 x \equiv 84 \!\!\!\pmod{48}$ kongruenciát!
  8. Legyen $G$ egy 2001 rendű csoport és $g \in G$ egy 23-rendű eleme. Határozzuk meg $g^2$ rendjét! (2001 prímfelbontása: $2001 = 3 \cdot 23 \cdot 29$)

Bevezetés a számításelméletbe II.
Vizsgazárthelyi feladatok
2001. június 27.

  1. Legyen $G$ a $V=\{p_1, p_2, \ldots, p_{2001} \}$ ponthalmazon az a gráf, amelyben $\{p_i,p_j\} \in E$ pontosan akkor teljesül, ha $0 < \vert i - j\vert \le 2$. Határozzuk meg az $\alpha(G)$, $\nu(G)$, $\rho(G)$, $\tau(G)$ értékeket!
  2. Legyen $V = \{ 1, 2, \ldots, 74\}$ a $H$ gráf ponthalmaza, az $i$ és $j$ pontok között akkor menjen él, ha $i+j$ és 74 relatív prímek és $i \ne j$. Határozzuk meg $\chi_e(H)$ értékét!
  3. A $G$ egyszerű gráfnak legyen $A$ a szomszédossági mátrixa. Határozzuk meg az összes olyan $G$ gráfot, amelyre az $A^2 + A -E $ mátrixban mindenhol 1 áll. ($E$ az egységmátrixot jelöli.)
  4. Á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! Melyek a kritikus tevékenységek?
    \includegraphics{pert4.eps}
  5. Az alábbi hálózatban az x paraméter értékétől függően adjunk meg egy maximális folyamot!
    \includegraphics{folyam4.eps}

  6. Bizonyítsuk be, hogy három szomszédos egész szám köbének összege osztható 9-cel!
  7. Oldjuk meg a $40 x \equiv 24 \!\!\!\pmod{16}$ kongruenciát!
  8. Legyen a $G$ csoport elemeinek halmaza $\{1,5,7,11 \}$, a művelet a $\pmod{12}$ szorzás. Ciklikus-e a $G$ csoport?