Bevezetés a számításelméletbe II.
2. gyakorlat 2003. február 21.
 
 
Színezések, páros gráfok

 

1. Melyik igaz az alábbi állítások közül?
   1. Ha egy páros gráfnak létezik Hamilton-köre, akkor páros sok pontja van.
   2. Ha egy páros grában van Euler-kör, akkor a két pontosztály mérete megegyezik.
   3. HF Ha egy páros gráfban van Euler-kör, akkor páros sok éle van.
2. Mekkora lehet $\omega(G)$ értéke, ha $G$ egy páros gráf?
3. Határozzuk meg az alábbi gráfokban a maximális klikkméret és a kromatikus szám értékét!
   
   
   
   
   
   
   
   
   
   
4. A $G_n$ gráf csúcsai az $n$ hosszú 0-1 bitsorozatoknak felelnek meg. Két csúcs pontosan akkor szomszédos, ha a megfelelö bitsorozatok pontosan egy bitben térnek el egymástól. Határozzuk meg a maximális klikkméretet! És mennyi a kromatikus szám ?
5. Egy $G$ gráf csúcsai az $\{1,2,\ldots,100\}$ számoknak felelnek meg. Két csúcs között pontosan akkor fut él, ha a megfelelö $i$ és $j$ számokra $\vert i-j\vert \le 10$ teljesül. Mennyi $\chi(G)$ értéke?
6. Mutassuk meg, hogy bármely $G$ gráf csúcsai sorbarendezhetők úgy, hogy a csúcsokat ebben a sorrendben mohó módon színezve $\chi(G)$ színt használó színezéshez jutunk.
7. A $G$ gráf fokszámainak sorozata $d_1 \ge d_2 \ge \dots \ge d_n$. Bizonyítsuk be, hogy
   
   $$\chi(G) \le \max_{i=1,\dots,n}\{\ \min\{d_i+1,i\} \ \}.$$
   
   

8. HF Egy $n=2k$ pontú teljes gráfból elhagytuk egy Hamilton-kör éleit. Mennyi az így kapott gráf kormatikus száma?
9. HF A $V(G)=\{1,2,\dots,1023\}$ 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 $\chi(G)$ értékét!
10. HF Mutassuk meg, hogy egy jo szinezesben legfeljebb $\omega(\overline{G})$ szin lehet egyforma. Ennek segitsegevel mutassunk also korlatot a kromatikus szamra $\omega(\overline{G})$ es a pontok szamanak felhasznalasaval! ($\overline{G}$ a graf komplementeret jeloli.)
11. 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 $G$ gráf pontjainak, és a gráf élei legyenek az egyes egyeneseken szomszédosan elhelyezkedő csúcspárok. Igazoljuk, hogy $\chi(G)\le 3$. (Segítség: valamilyen mohó színezést érdemes mutatni, csak arra kell rájönni, hogy milyen sorrendben érdemes a pontokat kiválasztani.)