next up previous
Next: About this document ...

Bevezetés a számításelméletbe II.
5. gyakorlat 2002. március 14.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Perfekt gráfok, élszínezés

 

  1. Perfektek-e az alábbi gráfok? Határozzuk meg az alábbi gráfok élkromatikus számát (vagy kromatikus indexét)!
    \includegraphics[width=10cm]{antr.eps}

  2. Az alább felsorolt gráftulajdonságok közül melyek öröklődnek minden feszített részgráfra?
    1. síkbarajzolhatóság;
    2. síkba nem rajzolhatóság;
    3. összefüggőség;
    4. körmentesség;
    5. élgráfnak lenni;

  3. Igazoljuk, hogy a legalább öt hosszú páratlan körök illetve azok komplementere minimális imperfekt gráf!

  4. Mutassuk meg, hogy az intervallumgráfok perfektek Lovász tételének felhasználása nélkül is.

  5. A $ G_k$ gráf $ (k \ge 2)$ egy $ (v_1,v_2,\dots,v_{2k})$ Hamilton-körből, valamint a $ k$ darab további $ \{v_1,v_{k+1}\}, \{v_2,v_{k+2}\}, \dots ,\\ \{v_k, v_{2k} \}$ élből kapjuk.
    1. Határozzuk meg $ G_k$ élkromatikus számát.
    2. HF Határozzuk meg $ G_k$ kromatikus számát is tetszőleges $ k$-ra.

  6. Legyen $ G$ 100-reguláris egyszerű gráf 2001 ponton. Határozzuk meg $ \chi'(G)$ értékét.

  7. HF Mutassuk meg, hogy

    $\displaystyle \alpha(G) + \omega(G) \le \vert V\vert+1.$

  8. HF Legyen $ A$ a $ G$ irányítatlan gráf adjacencia (szomszédsági) mátrixa, és jelölje $ E$ az $ \vert V(G)\vert \times \vert V(G)\vert$ méretű egység mátrixot. Mutassuk meg, hogy

    $\displaystyle r(A+E) \ge \alpha(G),$

    ahol $ r(M)$-mel az $ M$ mátrix rangját jelöljük. (Segítség: Ez a példa egyáltalán nem olyan nehéz, mint amilyennek tűnik.)

  9. HF Előbb páratlan, majd páros $ n$ esetére is határozzuk meg az $ n$ pontú teljes gráf élkromatikus számát!

  10. HF Legyen $ G$ egy 3-reguláris gráf, amire $ \chi'(G)=3$ és a színek permutációjától eltekintve az élek csak egyféleképpen színezhetők 3 színnel. Igazoljuk, hogy $ G$-nek van Hamilton-köre!

$ \alpha(G)$

Függetlenségi szám. 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;
$ \omega(G)$

Klikkszám. Egy maximális méretű klikk pontjainak száma;
$ \chi(G)$

Kromatikus szám. Egy minimális számú színt használó színezésben felhasznált színek száma;
$ \chi'(G)$

Élkromatikus szám vagy kromatikus index. Az élek egy minimális számú színt használó színezésben felhasznált színek száma;


next up previous
Next: About this document ...
Fogaras Daniel 2002-03-20