Bevezetés a számításelméletbe II. Zárthelyi feladatok 2000. április 6.


  1. Minimálisan hányszor kell ``felemelni'' a ceruzát az alábbi ábrán látható gráf lerajzolásakor, ha minden élet csak egyszer rajzolhatunk meg? (Egyéb vonalakat nem rajzolhatunk.)

  2. Igaz-e, hogy ha egy páros gráfban van Hamilton-kör, akkor teljes párosítást is tartalmaz?


  3. Egy társaságban bármely két embernek legalább két közös ismerőse van. Tudjuk továbbá, hogy bármely két ember vagy ismeri egymást, vagy ha nem, akkor a társaság bármely harmadik tagját legalább az egyikük ismeri. Bizonyítsuk be, hogy a társaság tagjai leültethetők egy (megfelelő méretű) kerek asztal köré úgy, hogy mindenki két ismerőse között üljön.


  4. Állapítsuk meg, hogy mennyi az alábbi ábrán látható $G$ gráf összes élét lefogó pontok $\tau(G)$ minimális száma.

    \includegraphics{gr.eps}


  5. Adjuk meg az összes olyan véges egyszerű gráfot, amire $\chi(G) = 3$ és tetszőleges $e \in E(G)$ élre $\chi(G - e) < 3$.

  6. Mennyi az ábrán látható gráf kromatikus száma?

    \includegraphics{grmod.eps}


  7. Állapítsuk meg, hogy mennyi a feladat elvégzéséhez minimálisan szükséges idő az alábbi PERT diagram által leírt munkafolyamatnál!

    \includegraphics{foly1.eps}


  8. Legyen $A$ a $G$ véges egyszerű irányítatlan gráf szomszédossági mátrixa, $E$ pedig az $A$-val azonos méretű egységmátrix. Bizonyítsuk be, hogy a $G$ gráfban található legnagyobb független ponthalmaz $\alpha(G)$ mérete és az $(A + E)$ mátrix $rk(A+E)$ rangja között fönnáll az
    \begin{displaymath} \alpha(G) \le rk(A+E) \end{displaymath}

    összefüggés.



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


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

    \includegraphics{foly2.eps}


  2. Bizonyítsuk be, hogy ha a $G$ véges egyszeru gráf síkgráf, akkor $G$ nem lehet hatszorosan (csúcs)összefüggo.


  3. Egy $90$ fos társaságból bizonyos párok leveleznek egymással. Akárhogyan választunk ki közülük tíz embert, ezek között mindig van legalább ketto, akik leveleznek egymással. Bizonyítsuk be, hogy a levelezo párok száma legalább $405$.


  4. Bizonyítsuk be, hogy $70$ ember között mindig van vagy $5$ olyan, akik páronként tegezodnek egymással, vagy $5$ olyan, akik páronként magázódnak. (Feltesszük, hogy a tegezodés és a magázódás is kölcsönös, és azt is, hogy bármely két ember vagy tegezodik, vagy magázódik.)


  5. Bizonyítsuk be, hogy négy egymást követo 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.


  6. Legyenek $k$ és $n$ olyan pozitív egészek, amelyekre $k<n$. Mi a legnagyobb közös osztója az $n!+k$ és az $(n+1)!+k$ számoknak?


  7. Legyenek $m$ és $n$ olyan pozitív egészek, amelyekre $m$ osztója $n$-nek. Bizonyítsuk be, hogy $\varphi(m)$ osztója $\varphi(n)$-nek.
  8. Milyen maradékot adhat 45-tel osztva az $x$ szám, ha $12x \equiv 42 \pmod{45}$