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, ..., p_{2001}\}$ ponthalmazon egy olyan egyszerű gráf, amelyben $\{p_i,p_j\}\in E$ pontosan akkor teljesül, ha $\vert i-j\vert\leqslant 2$.

    1. Van-e $G$-ben Euler-kör vagy Euler-út?
    2. Van-e $G$-ben Hamilton-kör vagy Hamilton-út?

    Megoldás:

    1. A $G$ gráf összefüggő, így Euler-kör illetve -út létezésének eldöntéséhez $G$ fokszámait kell megvizsgálnunk. A feltételek szerint $p_1$ és $p_{2001}$ fokszáma 2, $p_2$ és $p_{2000}$ fokszáma 3, végezetül $3 \leqslant i \leqslant 1999$ esetén $p_i$ fokszáma 4.

      Összességében tehát megállapítható, hogy $G$-nek pontosan két páratlan fokszámú csúcsa van, ezért Euler-utat tartalmaz, de Euler-kört nem.

    2. A legegyszerűbb Hamilton-út a csúcsok növekvő index szerinti bejárásával kapható, hiszen $p_i$ és $p_{i+1}$ minden $1\leqslant i \leqslant 2000$ esetén szomszédosak. Sajnos ez a Hamilton-út nem terjeszthető ki egyetlen él behúzásával Hamiton-körré.

      Könnyű ellenőrizni azonban, hogy a csúcsok következő sorrendben való bejárása Hamilton-kört ad: $p_1, p_3, p_5, ..., p_{1999}, p_{2001}, p_{2000}, p_{1998}, p_{1996}, ..., p_4, p_2, p_1$. Természetesen ennek egy élét elhagyva szintén Hamilton-utat kapunk.

  2. Legyen $V={1,2,...,74}$ a H gráf ponthalmaza, az $i$ és $j$ különböző 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!

    Megoldás:

    Azonos paritású számok között biztosan nem megy él, hiszen az ilyen számpárok összege páros, ami nem lehet relatív prím 74-hez. Bizonyos számpárok összege lehet továbbá 37, 74 vagy 111, mely esetekben az adott számpár szintén nincs összekötve. Minden egyéb számpár össze van kötve.

    Ennek alapján $H$ egy jó színezését kapjuk, ha a páros számokat pirosra, a páratlanokat pedig kékre festjük. $H$ tartalmaz élet, így egyetlen színnel biztosan nem színezhető. Ezek alapján $\chi(H)=2$.

    Vizsgáljuk a lefogó élek minimális számát ($\rho(H)$). Egyfelől ez a szám nyilván legalább 37, hisz egy él legfeljebb két pontot foghat le. Másfelől megadható 37 él, melyek $H$ összes pontját lefogják, éspedig az $\{i,75-i\} (1 \leqslant i \leqslant 37)$ élek. Ezen élek csúcsaihoz tartozó számok összege ugyanis minden esetben 75, ami relatív prím 74-hez, tehát ezek valóban $H$ élei. Ezért $\rho(H)=37$.

    A $H$ gráf hurokmentes, ezért alkalmazható Gallai tétele, amely szerint $\rho(H)+\nu(H)=\vert V(H)\vert$, ennek alapján $\nu(H)=37$.

    A $H$ gráf páros és nem tartalmaz izolált pontot, így König tételének mindkét állítása alkalmazható, amely szerint $\tau(H)=\nu(H)$ és $\alpha(H)=\rho(H)$. Tehát a lefogó pontok minimális száma $\tau(H)=37$, a független pontok maximális száma pedig $\alpha(H)=37$.

  3. Állapítsuk meg, hogy a $p$ paraméter függvényében mennyi a feladat elvégzéséhez szükséges minimális idő az alábbi PERT diagram által leírt munkafolyamatnál! Melyek a kritikus tevékenységek? (ábra és megoldás nemsokára)

  4. Adjunk meg az alábbi hálózatban egy maximális folyamot! (ábra és megoldás nemsokára)

  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.

    Megoldás:

    Legyen a $G$-ből elhagyott él $e$. Indirekt módon tegyük fel, hogy az állítás nem igaz. Ekkor a $G'$ gráfból elhagyható legfeljebb $k-2$ pont úgy, hogy ne maradjon összefüggő. Tekintsük ugyanezen legfeljebb $k-2$ pontot $G$-ben. Ha $e$ egyik végpontja sincs köztük, akkor vegyük hozzájuk a kettő közül pontosan az egyiket. Így legfeljebb $k-1$ pontot kaptunk, melyeket $G$-ből elhagyva az nem marad összefüggő. Ez azonban ellentmond annak, hogy $G$ eredetileg $k$-szorosan pontösszefüggő volt.

  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!

    Megoldás:

    Könnyű ellenőrizni, hogy bármely páratlan szám négyzete 1-et ad 8-cal osztva maradékul ( $(8k \pm 1)^2 \equiv (8k \pm 3)^2 \equiv 1 \pmod{8}$).

    Indirekt módon tegyük fel, hogy $b$ nem osztható néggyel, ekkor alkalmas $k$ egész szám választása esetén $b=4k+2$. Ekkor $b^2\equiv 4 \pmod{8}$. Ekkor azonban $a^2+b^2 \equiv 5 \pmod{8}$ ellentmond a fenti megállapításunknak, ez az ellentmondás bizonyítja a feladat állítását.

  7. Oldjuk meg a $2001x \equiv 3 \pmod {12}$ kongruenciát!

    Megoldás:

    $(2001,12)=3$, ezért a kongruenciának pontosan három megoldása lesz modulo 12, vagy másképpen mondva pontosan egy megoldása lesz modulo 4. A 3-mal való osztás elvégzése után $667x \equiv 1 \pmod {4}$, azaz $3x \equiv 1 \pmod {4}$ adódik. Mindkét oldalt 3-mal szorozva (figyelem! itt változatlan marad a modulus) kapjuk a megoldást: $9x \equiv x \equiv 3 \pmod{4}$.

  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!

    Megoldás:

    A faktorcsoport elemszáma: $\vert G/H\vert=\vert G\vert/\vert H\vert=2001/69=29$, ami prímszám. Ismeretes, hogy minden prímrendű csoport ciklikus. A $G/H$ faktorcsoport tehát ciklikus, ezért kommutatív.

Vissza