Bevezetés a számításelméletbe II.
4. gyakorlat 2003 március 7.
 
 
Görög betűk

 

1. Határozzuk meg az alábbi gráfokban az $\alpha(G), \tau(G), \nu(G)$ és $\rho(G)$ értékeket.
   
2. 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.)
3. Melyik igaz az alábbi állítások közül?
   1. Ha egy páros gráfnak van Hamilton-köre, akkor van benne teljes párosítás.
   2. Ha egy gráfban van két éldiszjunkt (közös élt nem tartalmazó) teljes párosítás, akkor van benne Hamilton-kör.
4. Keressünk maximális párosítást és minimális lefogóponthalmazt az alábbi gráfokban!
   
5. Legyen $\Delta(G)$ egy gráfban a maximális fokszám. Bizonyítsuk be, hogy $\Delta(G)\tau(G)\ge \vert E(G)\vert$.
6. Bizonyítsuk be, hogy tetszőleges $r$-reguláris egyszerű páros gráf tartalmaz teljes párosítást!
7. Bizonyítsuk be, hogy tetszőleges $G(V,E)$ egyszerű gráfban $\chi_e(G) \ge \frac{\vert E\vert}{\nu(G)}$ .
8. Határozzuk meg egy tetszőleges $r$-reguláris egyszerű páros gráf élkromatikus számát!
9. HF Igazoljuk, hogy egy hurokmentes $G$ gráfban teljesül a $\tau(G) \le 2\nu(G)$ egyenlőtlenség!
10. 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)$?
11. HF Egy társaságban van tíz olyan lány, akik közül bármely kettő különböző számú, de legalább egy fiút kedvel a társaságból. Mutassuk meg, hogy a tíz lány egyszerre tud keringőzni úgy, hogy mindegyikük kedvére való fiúval táncoljon!
12. HF Bizonyítsuk be, hogy egy fában legfeljebb egy teljes párosítás lehet!
13. HF 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. Mutassunk példát olyan a feladat feltételeit kielégítő $G$-re, ahol $\nu(G) = 6$?

$\alpha(G)$

Egy maximális független ponthalmaz mérete;

$\omega(G)$

Egy maximális klikk 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;

$\chi(G)$

Kromatikus szám;

$\chi_e(G)$

Élkromatikus szám ($\chi'(G)$ jelölés is előfordul);