Bevezetés a számításelméletbe II.
3. gyakorlat 2002. február 28-március 1.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Négy görög betű

 
  1. Bizonyítsuk be, hogy ha egy páros gráfban nincsen teljes párosítás, akkor az $ A$ adjacencia (szomszédsági) mátrixra $ \det A=0$. (Segítség: Használjuk a determináns definícióját és mutassuk meg, hogy minden kifejtési tag 0.)
  2. Határozzuk meg az alábbi gráfokban az $ \alpha(G), \tau(G), \nu(G)$ és $ \rho(G)$ értékeket.
    \includegraphics[width=10cm]{antr.eps}
  3. Mennyi $ \tau(K_{n,m})$? (Azt a teljes páros gráfot jelöli $ K_{n,m}$, melynek két pontosztálya $ n$ illetve $ m$ pontból áll.)
  4. Legyen $ \Delta(G)$ egy gráfban a maximális fokszám. Bizonyítsuk be, hogy $ \Delta(G)\tau(G)\ge \vert E(G)\vert$.
  5. Igazoljuk, hogy egy hurokmentes $ G$ gráfban teljesül a $ \tau(G) \le 2\nu(G)$ egyenlőtlenség!
  6. Egy egyszerű $ G$ gráfnak 1000 pontja van és, bármely pontnak a foka legalább 6.
    1. Mutassuk meg, hogy $ \nu(G) \ge 6$!
    2. HF Tudsz mutatni példát olyan a feladat feltételeit kielégítő $ G$-re, ahol $ \nu(G) = 6$?
  7. Határozzuk meg $ \nu(G)$-t és $ \tau(G)$-t az alábbi gráfokban!
    \includegraphics[width=8cm]{hex.eps} \includegraphics[width=4cm]{abragyak3.eps}
  8. HF Legyen $ G$ egy $ 2n$ pontú gráf, mely egy $ 2n-1$ pontú $ L$ útból és egy $ c$ pontból áll, ami $ L$ minden pontjával össze van kötve. Mennyi $ \tau(G)$?
  9. HF Bizonyítsuk be, hogy egy fában legfeljebb egy teljes párosítás lehet!
  10. HF Egy $ n\times n$ méretű, nem negatív elemeket tartalmazó mátrix bármely sorában lévő elemek összege 1, hasonlóan bármely oszlopban előforduló elemek összege is 1. Bizonyítsuk be, hogy a mátrix determinánsában szereplő $ n!$ kifejtési tag nem lehet mind nulla.
  11. HF Legyen $ F$ egy maximális méretű független ponthalmaz az egyszerű $ G$ gráfban, és legyen $ F'$ egy független ponthalmaz $ V(G)-F$-ben. Bizonyítsuk be, hogy $ \nu(G) \ge \vert F'\vert$!
$ \alpha(G)$

Egy maximális független ponthalmaz mérete;
$ \tau(G)$

Egy minimális lefogó ponthalmaz mérete;
$ \nu(G)$

Egy maximális független élhalmaz mérete;
$ \rho(G)$

Egy minimális lefogó élhalmaz mérete;
$ \Delta(G)$

Maximális fokszám;
:)

Kitartás, még jön két görög betű!!!