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)!
   

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
   $$\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
   $$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;