Bevezetés a számításelméletbe II.

2002. március 14.

1. ZH! Mennyi az ábrán látható gráf élkromatikus száma?

2. HF, Nem volt Perfekt-e az alábbi gráf?

3. Legyenek $G$ csúcsai a sakktábla mezoi, és két csúcs pontosan akkor legyen összekötve, ha a megfelelo mezok bástyával egy lépésben elérhetok egymásból. Mennyi az így keletkezett gráf kromatikus száma?

4. ZH! Jelentse $G_k$ a Mycielski konstrukcióval kapott azon gráfot, melynek kromatikus száma $k$. Adjuk meg az összes olyan $k$ értéket, melyre $G_k$ tartalmaz Euler-kört!
* És Euler-út mikor van?

5. Bizonyítsuk be, hogy ha $G$ egy $n$ csúcsú egyszeru reguláris gráf, akkor $\chi(G) + \chi(\overline{G}) \le n+1$. ($\overline{G}$ a $G$ gráf komplementerét jelöli.)

6. Nem volt Mutass olyan $G$ gráfot, amire $\chi(G)=\omega(G)$, de $G$ mégse perfekt!

7. ZH! Mutasd meg, hogy minden egyszerű, síkba rajzolható $n$ pontú gráfra teljesül, hogy $\alpha(G)\geq \frac{n}{4}$.

8. HF, ZH! Legyen $G$ egy $10$-reguláris egyszeru gráf, melynek $1999$ csúcsa van. Mennyi a ${\chi}_e(G)$ élkromatikus szám értéke?

9. Nem volt, ZH! Egy legalább két csúcsú teljes gráf néhány, egy csúcshoz illeszkedő élét elhagyjuk. Bizonyítsuk be, hogy az így kapott gráf perfekt.



10. ZH! Legyen $G$ egy olyan egyszerű gráf, melynek pontjai számozhatók úgy, hogy minden pont legfeljebb kettő nála nagyobb sorszámú ponttal van összekötve. Mutasd meg, hogy $\chi(G)\leq 3$.

11. Nem volt Bizonyítsuk be, hogy az 5 pontú teljes gráf élgráfja, $L(K_5)$ nem perfekt!

12. ZH! Legyen $G$ a $V=\{p_1,p_2, \cdots, p_{2001}\}$ ponthalmazon adott gráf, ahol $\{p_i,p_j\}\in E$ pontosan akkor, ha $0<\vert i-j\vert\leq 2$. Mennyi $G$ élkromatikus száma, azaz ${\chi}_e(G)$?

13. A 4. példában leírt gráfokban milyen $k$-ra van Hamilton kör?

14. ZH!, * Mennyi $\chi_e(K_{2n+1})$ és $\chi_e(K_{2n})$?

15. Nem volt * Legyen $G_1$ és $G_2$ két olyan perfekt gráf, melyek metszete teljes gráf. (A metszet pontjai a közos pontok, élei a közös élek.) Mutasd meg, hogy $G_1\cup G_2$ is perfekt! (Az únió pontjai a két ponthalmaz együtt, élei az élhalmazok úniója.)