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
- Perfektek-e az alábbi gráfok? Határozzuk meg az alábbi gráfok élkromatikus számát (vagy kromatikus indexét)!
- Az alább felsorolt gráftulajdonságok közül melyek öröklődnek minden feszített részgráfra?
- síkbarajzolhatóság;
- síkba nem rajzolhatóság;
- összefüggőség;
- körmentesség;
- élgráfnak lenni;
- Igazoljuk, hogy a legalább öt hosszú páratlan körök illetve azok komplementere minimális imperfekt gráf!
- Mutassuk meg, hogy az intervallumgráfok perfektek Lovász tételének felhasználása nélkül is.
- A
gráf
egy
Hamilton-körből, valamint a
darab további
élből kapjuk.
- Határozzuk meg
élkromatikus számát.
- HF Határozzuk meg
kromatikus számát is tetszőleges
-ra.
- Legyen
100-reguláris egyszerű gráf 2001 ponton. Határozzuk meg
értékét.
- HF Mutassuk meg, hogy
- HF Legyen
a
irányítatlan gráf adjacencia (szomszédsági) mátrixa, és jelölje
az
méretű egység mátrixot. Mutassuk meg, hogy
ahol
-mel az
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.)
- HF Előbb páratlan, majd páros
esetére is határozzuk meg az
pontú teljes gráf élkromatikus számát!
- HF Legyen
egy 3-reguláris gráf, amire
és a színek permutációjától eltekintve az élek csak egyféleképpen színezhetők 3 színnel.
Igazoljuk, hogy
-nek van Hamilton-köre!
![$ \alpha(G)$](img18.png)
-
Függetlenségi szám. Egy maximális
független ponthalmaz mérete;
![$ \tau(G)$](img19.png)
-
Egy minimális lefogó ponthalmaz mérete;
![$ \nu(G)$](img20.png)
-
Egy maximális független élhalmaz mérete;
![$ \rho(G)$](img21.png)
-
Egy minimális lefogó élhalmaz mérete;
![$ \Delta(G)$](img22.png)
-
Maximális fokszám;
![$ \omega(G)$](img23.png)
-
Klikkszám. Egy maximális méretű klikk pontjainak száma;
![$ \chi(G)$](img24.png)
-
Kromatikus szám. Egy minimális számú színt használó színezésben felhasznált színek száma;
![$ \chi'(G)$](img8.png)
-
É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: About this document ...
Fogaras Daniel
2002-03-20