Bevezetés a számításelméletbe II.
7. gyakorlat 2003 március 28.
 
 
Gráfok mátrixai, számelmélet

 

1. Legyen $A$ egy egyszerű irányítatlan gráf szomszédsági mátrixa. Mutassuk meg, hogy ha $A^2$ mátrix minden eleme 0 vagy 1, akkor $G$ nem tartalmaz négy hosszú kört!
2. Tegyük fel, hogy egy páros gráf nem tartalmaz teljes párosítást. Igazoljuk, hogy adjacencia mátrixa szinguláris, azaz determinánsa nulla! (Segítség: lássuk be, hogy a determinánsban szereplo kifejtési tagok mindegyike 0.)
3. Legyen $\mathbf{A}$ és $\mathbf{B}$ egy hurokél-mentes gráf szomszédsági, ill. illeszkedési mátrixa. Mi mondható a $\mathbf{BB^T - A}$ mátrixról?
4. Igazoljuk, hogy öt egymást követő egész szám szorzata osztható 30-al!
5. Lehet-e négy egymást követo prímszám összege is prím?
6. Mutassuk meg, hogy
   1. $24 \vert a (a^2 -1 )$, ahol $a$ páratlan egész;
   2. $360 \vert a^2(a^2-1)(a^2-4)$, ha $a$ tetszőleges egész;
   3. $24 \vert a ^2 + 23$, ahol $a$ 2-vel és 3-mal nem osztható szám.
7. Bizonyítsuk be, hogy ha $2^n-1$ prím, akkor $n$ is prím!
8. Bizonyítsuk be, hogy négy egymást követő pozitív egész szám között mindig van olyan, amelyik a másik három mindegyikéhez (külön-külön) relatív prím.
9. Péter a XX. század második felében született, éppen nagyapja 53. születésnapján. Kettejük születési évszámai nem relatív prímek. Hány éves Péter?