Next: About this document ...
Bevezetés a számításelméletbe II.
4. gyakorlat 2002. március 7-8.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
Gráfok színezése
- Határozzuk meg az alábbi gráfok kromatikus számát és maximális klikkméretét!
- Mennyi
, ha
egy páros gráf legalább egy éllel?
- Milyen összefüggés írható fel az
és az
függvények között?
- A
gráfra
, továbbá a
és
pontok között pontosan akkor van él, ha
valamely
egésszel. Mennyi
?
- Bizonyítsuk be a
egyenlőtlenséget!
- Igazoljuk, hogy
!
- Mutassuk meg, hogy bármely
gráf csúcsai sorbarendezhetők úgy, hogy a csúcsokat ebben a sorrendben mohó módon színezve
színű színezéshez jutunk.
- A
gráf fokszámainak sorozata
. Bizonyítsuk be, hogy
- HF A
ponthalmazon definiáljunk egy gráfot úgy, hogy két pont között akkor és csak akkor legyen él, ha a két szám közül az egyik osztja a másikat. Határozzuk meg
értékét!
- HF Bizonyítsuk be, hogy
- HF Egy
pontú teljes gráfból elhagytuk egy Hamilton-kör éleit. Mennyi az így kapott gráf kormatikus száma? Mi a helyzet, ha
pontú teljes gráfból hagyjuk el az éleket?
- HF Tetszőleges
egészekre mutassunk példát olyan gráfra, ahol
,
és
.
- HF Adott a síkon néhány egyenes, melyek közül semelyik három nem metszi egymást egy közös pontban. Tekintsük az egyenesek metszéspontjait egy
gráf pontjainak, és a gráf élei legyenek az egyes egyeneseken szomszédosan elhelyezkedő csúcspárok. Igazoljuk, hogy
. (Segítség: valamilyen mohó színezést érdemes mutatni, csak arra kell rájönni, hogy milyen sorrendben érdemes a pontokat kiválasztani.)
![$ \alpha(G)$](img25.png)
-
Egy maximális
független ponthalmaz mérete;
![$ \tau(G)$](img26.png)
-
Egy minimális lefogó ponthalmaz mérete;
![$ \nu(G)$](img27.png)
-
Egy maximális független élhalmaz mérete;
![$ \rho(G)$](img28.png)
-
Egy minimális lefogó élhalmaz mérete;
![$ \Delta(G)$](img29.png)
-
Maximális fokszám;
![$ \omega(G)$](img2.png)
-
Egy maximális méretű klikk pontjainak száma;
![$ \chi(G)$](img11.png)
-
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-12