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

1. Bizonyítsuk be, hogy egy egyszeru, összefüggo és reguláris gráf élgráfjában mindig van Euler-kör. (Emlékezteto: Egy gráfot akkor mondunk regulárisnak, ha minden fokszáma egyenlo.)
2. Legyenek $m\ge 2$ és $n\ge 3$ egész számok, melyekre $n\ge m$. Bizonyítsuk be, hogy az $n$ csúcsú és $m$ osztályú Turán gráf akkor és csak akkor nem tartalmaz Hamilton-kört, ha $m=2$ és $n$ páratlan.
3. Egy $G$ gráf csúcsai legyenek az $\{1,2,\dots,n\}$ számok összes permutációi. Két csúcs akkor legyen összekötve $G$-ben, ha a megfelelo két permutáció egyetlen (nem feltétlenül szomszédos elemekbol álló) elempár felcserélésével egymásba viheto. Mutassuk meg, hogy az így megadott $G$ gráf tartalmaz teljes párosítást.
4. Legyen $G$ a $3$ osztályú $12$ pontú Turán-gráf. Állapítsuk meg $\tau(G)$ értékét!
5. Igazoljuk, hogy tetszoleges $n$ csúcsú $G$ egyszeru gráfra fennáll, hogy
$$\tau(G)-\nu(G)<{n\over 2}.$$
6. Legyen $G$ a következoképpen megadott gráf:$V(G)=\{1,2,\dots, 10\}$ és $E(G)=E_1\cup E_2\cup E_3,$ ahol$E_1=\{\{i,j\}: 1\leq i<j\leq 5\}, E_2=\{\{i,j\}: 6\leq i<j\leq 10\},E_3=\{\{i,j\}: j=i+5\}.$ (Szavakkal megadva: $G$ két pontdiszjunkt $K_5$-bol áll, amiket egy teljes párosítás köt össze.) Állapítsuk meg $G$ élkromatikus számának értékét!
7. Adott a síkon néhány körvonal, ezekhez rendeljük a következo $G$ gráfot. $G$ csúcsai feleljenek meg egy-egy megadott körvonalnak, és ketto akkor legyen összekötve, ha a két megfelelo körvonal egyike teljesen a másik belsejében halad. Bizonyítsuk be, hogy az így megadott $G$ gráf perfekt.
8. Állapítsuk meg a feladat elvégzéséhez szükséges ido hosszát és határozzuk meg a kritikus utakat az alábbi PERT diagramon!

 

 


 

A feladatok sorrendje nem jelent nehézségi sorrendet. Minden feladat 10 pontot ér. Az elégséges eléréséhez szükséges minimális pontszám 32. A további osztályzatok ponthatárai egyenletesen (12 pontonként) helyezkednek el, de a vizsgára nem osztályzat, hanem az elért pontszám ``megy tovább''.

Puszta (indoklás nélküli) eredményközlésért nem jár pont.

A dolgozatra kérjük jól olvashatóan felírni a következo adatokat: név, neptun-kód, tankör száma, gyakorlatvezeto neve.

 
 
 
 

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

1. Adjunk meg egy maximális folyamot és állapítsuk meg annak értékét az alábbi hálózatban!

 

 


 
2. Legyen $G$ az ábrán látható nyolc csúcsú gráf. Bizonyítsuk be, hogy $G$ háromszorosan összefüggo, de négyszeresen már nem.

 

 


 
3. Oldjuk meg az alábbi kongruenciát (vagyis állapítsuk meg az azt kielégíto $x$(-ek) 90-nel adott maradékát)!
$$1000\, x \equiv 80 \pmod{90}$$
4. Bizonyítsuk be, hogy tetszoleges $h_1,\dots,h_k$ pozitív egészekre és $p$ prímszámra fennáll, hogy
$$(h_1+h_2+\dots+h_k)^p\equiv h_1^p+h_2^p+\dots +h_k^p \pmod{p}.$$
5. Mutassuk meg, hogy $61!+1$ osztható 71-gyel. (Emlékezteto: Számológép a zárthelyi feladatok megoldásához nem használható; jelen feladatnak is csak számelméleti érvelést tartalmazó, ``fejben ellenorizheto'' megoldását fogadjuk el.)
6. Hány különbözo részcsoportja van a $C_{2002}$ ciklikus csoportnak?
7. Legyenek $H$ és $K$ egy $G$ csoport olyan részcsoportjai, melyekre$(\vert H\vert,\vert K\vert)=1$ (vagyis a $H$ és $K$ részcsoport rendjének legnagyobb közös osztója $1$). Mutassuk meg, hogy ekkor $H\cap K=\{e\}$, ahol $e$ a$G$ csoport egységeleme.
8. Legyen $H$ a $G$ csoport tetszoleges, $N$ pedig a $G$ csoport normális részcsoportja. Bizonyítsuk be, hogy ekkor $H\cap N$ normális részcsoportja $H$-nak.

 

 

A feladatok sorrendje nem jelent nehézségi sorrendet. Minden feladat 10 pontot ér. Az elégséges eléréséhez szükséges minimális pontszám 32. A további osztályzatok ponthatárai egyenletesen (12 pontonként) helyezkednek el, de a vizsgára nem osztályzat, hanem az elért pontszám ``megy tovább''.

Puszta (indoklás nélküli) eredményközlésért nem jár pont.

A dolgozatra kérjük jól olvashatóan felírni a következo adatokat: név, neptun-kód, tankör száma, gyakorlatvezeto neve.

 
 
 
 

Bevezetés a számításelméletbe II.      Pótzárthelyi feladatok (I.)      2002. május 10.

1. Igaz-e, hogy ha egy $G=(A,B,E)$ páros gráfnak van Euler-köre, akkor szükségképpen teljesül, hogy $\vert A\vert=\vert B\vert$?
2. Legyen $G$ az a gráf, amit úgy kapunk, hogy a $K_{n,n}$ teljes páros gráfból elhagyunk egy teljes párosítást. Mutassuk meg, hogy ha$n>2$, akkor $G$ tartalmaz Hamilton-kört.
3. Tekintsük az összes létezo olyan légijáratot, amely közvetlen összeköttetést biztosít egy amerikai és egy európai város között. Tegyük fel, hogy $k$ a legnagyobb olyan pozitív egész, amire létezik $k$ különbözo európai város, $E_1,\dots,E_k$, és $k$ különbözo amerikai város, $A_1,\dots,A_k$, úgy, hogy minden $1\leq i\leq k$-ra $E_i$ és $A_i$ között van közvetlen repülojárat. Bizonyítsuk be, hogy ekkor biztosan van az elobbi $2k$ város között $k$ olyan, amelyekre igaz, hogy az összes létezo Európa és Amerika közötti közvetlen légijáratnak az egyik végpontja közöttük van.
4. Mutassuk meg, hogy tetszoleges $n$ csúcsú véges egyszeru $G$ gráfra fennáll, hogy
$$\alpha(G)\ge n-2\nu(G).$$
5. Legyen $G$ $3$-reguláris véges egyszeru gráf, melynek $\chi_e(G)$ élkromatikus száma $4$. Mutassuk meg, hogy $G$ nem tartalmaz Hamilton-kört.
6. Legyen $G_n$ az az $n$ csúcsú gráf, melynek csúcsai az $1,2,\dots,n$ természetes számok, és ketto pontosan akkor van összekötve, ha egyik sem osztója a másiknak. Mutassuk meg, hogy $G_n$ (tetszoleges$n$ természetes szám esetén) perfekt gráf.
7. Legyen $T$ egy leheto legtöbb élet tartalmazó $n$ csúcsú egyszeru gráf, amely nem tartalmaz $r+1$ csúcsú teljes részgráfot. Mutassuk meg, hogy ha $T$-ben van Euler-kör, akkor $r$ osztója $n$-nek.
8. Állapítsuk meg a feladat elvégzéséhez szükséges ido hosszát és határozzuk meg a kritikus utakat az alábbi PERT diagramon!

 

 


 


A feladatok sorrendje nem jelent nehézségi sorrendet. Minden feladat 10 pontot ér. Az elégséges eléréséhez szükséges minimális pontszám 32. A további osztályzatok ponthatárai egyenletesen (12 pontonként) helyezkednek el, de a vizsgára nem osztályzat, hanem az elért pontszám ``megy tovább''.

Puszta (indoklás nélküli) eredményközlésért nem jár pont.

A dolgozatra kérjük jól olvashatóan felírni a következo adatokat: név, neptun-kód, tankör száma, gyakorlatvezeto neve.
 
 

 
 
 
 

Bevezetés a számításelméletbe II.      Pótzárthelyi feladatok      2002. május 16.

1. Adjunk meg egy maximális folyamot és állapítsuk meg annak értékét az alábbi hálózatban!

 

 


 
2. Legyen $G$ reguláris páros gráf, melyrol tudjuk, hogy összefüggo és legalább három csúcsa van. Mutassuk meg, hogy ekkor $G$ $2$-szeresen is összefüggo.
3. Oldjuk meg az alábbi kongruenciát (vagyis állapítsuk meg az azt kielégíto $x$(-ek) $49$-cel adott maradékát)!
$$77\, x \equiv 21 \pmod{49}$$
4. Mutassuk meg, hogy $2002^{2002}+1$ osztható $17$-tel.
5. Legyen $k\ge 2$ és jelölje $(a_1,a_2,\dots,a_k)$ azt a legnagyobb pozitív egészt, amely az $a_i\, (1\leq i\leq k)$ számok mindegyikét osztja, $[a_1,a_2,\dots,a_k]$ pedig azt a legkisebb pozitív egészt, amely az $a_i\, (1\leq i\leq k)$ számok mindegyikével osztható. Mutassuk meg, hogy
$$(a_1,a_2,\dots,a_k)\cdot [a_1,a_2,\dots,a_k]=a_1\cdota_2\cdot\dots\cdot a_k$$


akkor és csak akkor áll fönn minden$a_1,a_2,\dots,a_k$ pozitív egészekbol álló szám $k$-asra, ha$k=2$.

6. Legyenek $H$ és $K$ egy $G$ csoport részcsoportjai. Bizonyítsuk be, hogy ha $G$-nek a részhalmazszorzással (komplexusszorzással) létrejövo $HK$ részhalmaza is részcsoportja$G$-nek, akkor $HK=KH$.
7. Legyen $G$ egy csoport és $a$ ennek tetszoleges eleme. Bizonyítsuk be, hogy pontosan egy olyan $\phi$ homomorfizmus létezik, amely az egész számok additív csoportját képezi le $G$-be úgy, hogy$\phi(1)=a$. Mi lesz $Ker\phi$ erre a leképezésre?
8. Bizonyítsuk be, hogy ha egy legalább két elemet tartalmazó $G$ csoportnak nincsen valódi részcsoportja (tehát olyan részcsoportja, mely egynél több, de $\vert G\vert$-nél kevesebb elemet tartalmaz), akkor $G$ prímrendu ciklikus csoport.

 

 

A feladatok sorrendje nem jelent nehézségi sorrendet. Minden feladat 10 pontot ér. Az elégséges eléréséhez szükséges minimális pontszám 32. A további osztályzatok ponthatárai egyenletesen (12 pontonként) helyezkednek el, de a vizsgára nem osztályzat, hanem az elért pontszám ``megy tovább''.

Puszta (indoklás nélküli) eredményközlésért nem jár pont.

A dolgozatra kérjük jól olvashatóan felírni a következo adatokat: név, neptun-kód, tankör száma, gyakorlatvezeto neve.