Bevezetés a számításelméletbe II. - Vizsgafeladatok
2000. május 25.




1. Egy 2000 csúcsú $G$ gráfban a minimális fokszám 1500. Bizonyítsuk be, hogy $G$ tartalmaz legalább 251 páronként éldiszjunkt Hamilton-kört.


2. Jelölje $M_k$ a Mycielski-konstrukcióval kapott azon gráfot, melynek kromatikus száma $k$. ($M_2$ az egyetlen élet tartalmazó kétcsúcsú gráf, $M_3$ az 5 hosszú, húr nélküli kör.) Bizonyítsuk be, hogy $k>2$ esetén $\nu(M_k) = {{\vert V(M_k)\vert-1}\over 2}$.


3. Jelölje $k(m)$ azt a legnagyobb $k$ pozitív egész számot, amihez létezik $m$ élű $k$ kromatikus számú gráf. Határozzuk meg $k(m)$ értékét minden $m$-re.


4. Két légitársaság 10 város között üzemeltet járatokat. Minden járat két várost köt össze (oda-vissza) és bármely két város között legfeljebb az egyik társaságnak van járata. (Megengedett, hogy bizonyos városok között egyáltalán ne legyen közvetlen járat.) A két társaság megegyezett, hogy ha valamelyikük $A$ város és $B$ város valamint $A$ város és $C$ város között is üzemeltet járatot, akkor ugyanez a társaság nem repül közvetlenül $B$ és $C$ között. Bizonyítsuk be, hogy ilyen feltételek mellett a két légitársaság együttesen nem üzemeltethet 40-nél több járatot, 40-et viszont igen.


5. Adjunk meg az alábbi hálózatban egy maximális folyamot!

\includegraphics{v1.eps}


6. Milyen maradékot ad 60-nal osztva az az $x$ szám, melyre $104\, x \equiv 74 \pmod{60}$ ?


7. Bizonyítsuk be, hogy ha $d$ osztója $n$-nek, akkor $d- \varphi(d) \le n - \varphi(n)$.


8. Állapítsuk meg, hogy izomorf-e a $\bmod\ 4$ maradékosztályok additív csoportja a $\bmod\ 8$ redukált maradékosztályok multiplikatív csoportjával.



Bevezetés a számításelméletbe II. - Vizsgafeladatok
2000. június 6.




1. Legyen $G$ olyan véges egyszerű gráf melynek minden foka páros és valamely ${v\in V(G)}$ csúcsán az összes $G$-beli kör áthalad. Bizonyítsuk be, hogy minden olyan $G$-beli séta, amely csupa különböző élet használ fel és nem folytatható valamely már felhasznált él újbóli felhasználása nélkül, szükségképpen Euler-kör. ($G$-beli sétának olyan $v_1 e_1 v_2 e_2 v_3 \dots $ $v_i e_i v_{i+1} \dots v_{k-1} e_{k-1} v_k$ sorozatot nevezünk, ahol minden $i$-re $v_i \in V(G)$, $e_i\in E(G)$ és $e_i=\{v_i, v_{i+1}\}$.)


2. Egy $n$-szer $n$-es sakktábla bizonyos mezőit kijelölték, ezekre színes golyókat kell helyeznünk úgy, hogy azonos sorba, illetve, azonos oszlopba kerülő golyók nem lehetnek egyszínűek. Tudjuk, hogy semelyik sorban és semelyik oszlopban nincs $k$-nál több megjelölt mező. Igaz-e, hogy ekkor $k$-féle színű golyóval biztosan meg tudjuk oldani a feladatot (ha mindegyikből elég sokat használhatunk)?


3. Legyen $G_1$ és $G_2$ két véges egyszerű gráf, melyek kromatikus száma három. Definiáljuk általuk az alábbi $F$ gráfot. $F$ csúcsai az összes olyan rendezett $(u,v)$ párok, melyekre $u\in V(G_1)$ és $v\in V(G_2)$. Két ilyen csúcs, $(u_1,v_1)$ és $(u_2,v_2)$ akkor és csak akkor van összekötve $F$-ben, ha $\{u_1,u_2\}\in E(G_1)$ és $\{v_1,v_2\}\in E(G_2)$ is teljesül. Bizonyítsuk be, hogy $F$ kromatikus száma is három.


4. Minimálisan hány éle kell hogy legyen egy olyan $n$-csúcsú egyszerű gráfnak, amely háromszögmentes, de tetszőleges két még összekötetlen csúcsát összekötve keletkezik benne háromszög?


5. Állapítsuk meg a feladat elvégzéséhez minimálisan szükséges idő hosszát az alábbi PERT diagramon.

\includegraphics{v2.eps}


6. Bizonyítsuk be, hogy tetszőleges $n\ge 2$ pozitív egészre fennáll, hogy

\begin{displaymath}\sigma(n)\varphi(n) < n^2.\end{displaymath}


7. Tudjuk, hogy az $a$ egész számra teljesül, hogy ${a^{100} \equiv 5\!\!\!\!\pmod{31}}$ és ${a^{101} \equiv 19\!\!\!\!\pmod{31}}.$ Milyen maradékot ad 31-gyel való osztáskor az $a$ egész szám?


8. Legyenek $G$ és $H$ véges csoportok és $\phi$ homomorfizmus $G$-ből $H$-ba. Bizonyítsuk be, hogy tetszőleges $g\in G$ elemre a $g$ elem rendje osztható a $\phi(g)$ elem ($H$-beli) rendjével.



Bevezetés a számításelméletbe II. - Vizsgafeladatok
2000. június 20.




1. A $G$ gráf $k \ge 1$ darab pontdiszjunkt (húr nélküli) körből áll. Mi az a legkisebb $m$ szám, amelyre teljesül, hogy $G$-hez hozzá lehet venni $m$ élet úgy, hogy az új gráfban legyen teljes párosítás? Mikor létezik ilyen $m$ szám?


2. Bizonyítsuk be, hogy ha $n$ egynél nagyobb páratlan szám, akkor $L(K_n)$-nek, az $n$ pontú teljes gráf élgráfjának, van Hamilton-köre.


3. Legyen a $G$ gráf csúcshalmaza $V=\{1,2,\ldots,n\}$. A gráfban az olyan $a$ és $b$ csúcsok között van él, melyekre teljesül, hogy $a \ne b$ és vagy $a$ osztója $b$-nek, vagy $b$ osztója $a$-nak. Bizonyítsuk be, hogy $G$ perfekt.


4. Legkevesebb hány csúcsa lehet egy olyan $G$ egyszerű gráfnak, amely nem tartalmaz háromszöget és éleinek száma legalább kétszerese az $n$ csúcsú teljes gráf élei számának?


5. Adjunk meg az alábbi hálózatban egy maximális folyamot!

\includegraphics{v3.eps}


6. Milyen maradékot ad 21-gyel osztva az az $x$ szám, melyre $14\, x - 4 \equiv 80 \pmod{21}?$


7. Bizonyítsuk be, hogy ha $n > 2$ és $r_1, r_2, \ldots, r_{\varphi(n)}$ redukált maradékrendszer modulo $n$, akkor

\begin{displaymath}\sum_{i=1}^{\varphi(n)} r_i \equiv 0 \pmod{n}.\end{displaymath}


8. Bizonyítsuk be, hogy ha a $G$ csoport rendje 55, akkor minden $a \in G$ elemére teljesül, hogy az $a$ és az $a^8$ elemek rendje azonos.