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

1. Bizonyítsuk be, hogy ha egy véges, hurokélmentes $G$ gráfnak van Euler-köre, akkor $G$ élgráfjának is van Euler-köre. Igaz-e az elobbi állítás megfordítása?
2. Bizonyítsuk be, hogy egy $2$-reguláris páros gráfban (tehát amiben minden fokszám $2$) a különbözo teljes párosítások száma mindig $2$-nek valamilyen pozitív egész kitevos hatványával egyenlo.
3. Mutassuk meg, hogy ha egy véges, egyszeru $G$ gráfra$\chi(G)=\tau(G)+1$, akkor egyben $\chi(G)=\omega(G)$ is teljesül.
4. Mennyi az $\alpha(G)$ értéke egy olyan egyszeru $G$ gráfra, aminek $2002$ csúcsa van, és éleinek száma a leheto legnagyobb azon feltétel mellett, hogy nem tartalmaz $20$-nál nagyobb klikket.
5. Adjunk meg egy maximális folyamot és állapítsuk meg annak értékét az alábbi hálózatban! (Az élekre írt számok a kapacitásokat jelentik.)

6. Legyen $n$ olyan pozitív egész szám, ami sem $2$-vel, sem $5$-tel nem osztható. Bizonyítsuk be, hogy ekkor létezik olyan $k$ pozitív egész, amire $k\cdot n$ tízes számrendszerbeli alakja csupa $9$-es számjeggyel írható le.
7. Oldjuk meg az alábbi kongruenciát (vagyis állapítsuk meg az azt kielégíto $x$(-ek) 68-cal adott maradékát)!
$$24\, x \equiv 84 \pmod{68}$$
8. 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$ és $KH$ részhalmazai azonosak, vagyis $HK=KH$, akkor$HK$ is részcsoportja $G$-nek.

 

 

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.

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. június 4.

1. Legyen $G=(V,E)$ véges, összefüggo gráf. Mutassuk meg, hogy$G$-ben megadható olyan minden élen áthaladó séta, amely minden élen legfeljebb kétszer halad át.
2. Legyen $G$ olyan $2002$ csúcsú gráf, aminek van Hamilton-köre. Mutassuk meg, hogy ha $G$-bol elhagyunk $1000$ csúcsot (a hozzájuk csatlakozó élekkel együtt), akkor a megmaradó gráfnak még mindig van legalább két éle.
3. Legyenek egy $G$ gráf csúcsai azok a $10^{100}$-nál nem nagyobb pozitív egész számok, amelyeknek van $20$-nál kisebb prímosztója. $G$ két csúcsa pontosan akkor alkot élet, ha a megfelelo pozitív egészek relatív prímek. Állapítsuk meg $G$ kromatikus számának értékét!
4. Legyen $G$ olyan $n$ csúcsú véges egyszeru gráf, amelyik nem perfekt, de ha tetszoleges csúcsát elhagyjuk, az így kapott gráf már perfekt. Mutassuk meg, hogy $n-1$ nem lehet prímszám.
5. Á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! (Az élekre írt számok az adott élek ``hosszát'' jelentik.)

6. Mutassuk meg, hogy $2002!+1$ osztható $2003$-mal
7. Oldjuk meg az alábbi kongruenciát (vagyis állapítsuk meg az azt kielégíto $x$(-ek) 77-tel adott maradékát)!
$$121\, x \equiv 55 \pmod{77}$$
8. Legyen $G$ csoport, $H$ és $K$ pedig $G$-nek részcsoportjai. Mutassuk meg, hogy $H\cup K$ akkor és csak akkor részcsoportja $G$-nek, ha vagy$H\subseteq K$, vagy $K\subseteq H$.

 

 

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.

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.