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

2002. március 7.

1. ZH! Mennyi $\nu(G)$, $\alpha(G)$, $\tau(G)$, $\rho(G)$ és $\chi(G)$ értéke a Petersen gráf esetén?

2. Mennyi $\nu(G)$, $\alpha(G)$, $\tau(G)$, $\rho(G)$ és $\chi(G)$ értéke a $K_{n,m}$ gráf esetén?



3. Az állatkertben nekünk kell megszervezni az éjjeliőrök munkabeosztását, akiknek a lajhárra, az oroszlánra, a zebrára, a csigára és a tigrisre kell vigyázniuk. Az Első Őr a reumája miatt nem tud szaladni így csak a lajhárra vagy a csigára tud vigyázni. A Második Őr ruhájához nem illik a csíkos minta, ezért ilyen állatot nem hajlandó felügyelni. A Harmadik Őr ellenben csak csíkos állattal hajlandó foglalkozni. A Negyedik Őr kedveli a kihívásokat, ezért ő a tigrisre vagy az oroszlánra szeretne vigyázni. Az Ötödik Őr a csigára nem akar vigyázni. A Hatodik Őr a lajhár, a csiga, az oroszlán és a tigris kivételével bármit válal. Minden őr egyszerre csak egy állatra tud vigyázni és még az is van, hogy a tigrisre két embernek kell figyelnie. Ki lehet-e osztani az őröket úgy, hogy a fenti feltételek teljesüljenek?

4. Egy egyszerű $G$ gráf csúcsainak száma 2000. Tudjuk továbbá, hogy $\tau(G)=678$. Igazoljuk, hogy $G$-ben nincs teljes párosítás!

5. ZH! Legyenek a $G_n$ gráf pontjai az $n$ hosszú 0-1 sorozatok, két pont akkor legyen összekötve, ha a nekik megfelelő sorozatok pontosan egy helyen térnek el. Határozzuk meg $\nu(G_n)$, $\alpha(G_n)$, $\tau(G_n)$, $\rho(G_n)$ és $\chi(G_n)$ értékét minden $n$-re!

6. HF!!! ZH! A $2n$ csúcsú egyszeru $G$ gráfban minden pont foka legalább $n$. Igazoljuk, hogy $\tau(G) \ge n$ .

7. HF!!! Mutassuk meg, hogy egy $n$ pontú, egyszerű $G$ gráfban $\chi(G)\geq \frac{n}{\alpha(G)}$.

8. HF!!! ZH! Legyen a $G$ gráf ponthalmaza $\{1,2,...,2000\}$ és élhalmaza az összes olyan $\{x,y\}$ pár, ahol $x$ és $y$ közül az egyik osztója a másiknak. Határozzuk meg $G$ kromatikus számát!




9. Keressünk maximális párosítást (persze mutassuk meg azt is, hogy amit találtunk az az):

10. ZH! Legyen a $H$ gráf csúcshalmaza $V=\{1,2\ldots, 2001\}$ és két $i\not =j$ pont akkor legyen összekötve, ha $i+j$ hárommal osztva 1 maradékot ad. Határozzuk meg $\nu(H)$, $\alpha(H)$, $\tau(H)$, $\rho(H)$ és $\chi(H)$ értékét!

11. Az állatkertben szeretnénk az állatokat minél kevesebb cellába elhelyezni. De a bárány fél a tigristől és az oroszlántól, valamint a csiga fél, hogy eltapossa a zebra. A medve és a tigris viszont gusztustalannak tartja a csigát. Továbbá a bagoly okoskodása idegesíti a zebrát, a medvét és a bárányt, a medve horkolása viszont zavarja az oroszlánt. Hány cellában tudjuk elhelyezni az állatokat, ha azt akarjuk, hogy mindegyik jól érezze magát?

12. Legyen $G$ egy $2n$ pontú gráf, mely egy $2n-1$ pontú $L$ útból és egy $c$ pontból áll, ami $L$ minden pontjával össze van kötve. Mennyi $\tau(G)$?

13. Legyen $G$ egy 100 csúcsú, egyszerű síkgráf komplementere. Mutassuk meg, hogy $\tau(G)\geq 96$.

14. Határozzuk meg az $\alpha(G), \tau(G), \nu(G)$ és $\rho(G)$ értékeket, ha
(a) $G=K_n$ (teljes gráf), illetve
(b) $G=C_n$ ($n$ hosszú kör).

15. Mutassuk meg, hogy egy $n$ pontú, egyszerű $G$ gráfban $\chi(G)\leq \tau(G)+1$.

16.* Tekintsünk a $V$ véges csúcshalmazon két egyszerű gráfot, $G_1$-et és $G_2$-t. Jelölje $G_1\cup G_2$ azt a gráfot $V$-n, melynek élhalmaza $G_1$ és $G_2$ éleinek az uniója. Bizonyítsuk be, hogy $\chi(G_1 \cup G_2)\leq \chi(G_1)\cdot \chi(G_2)$.

17.*, ZH! Tekintsünk két véges, egyszerű gráfot $G_1$-et és $G_2$-t, melyek kromatikus száma 3. Definiáljuk az $F$ gráfot a következőképpen: $F$ csúcsai az $(u,v)$ rendezett párok, ahol $u\in V(G_1)$ és $v\in V(G_2)$ és $(u_1,v_1)$ és $(u_2,v_2)$ között akkor megy él, ha $\{u_1, u_2\}$ él $G_1$-ben és $\{v_1, v_2\}$ él $G_2$-ben. Mutassuk meg, hogy $F$ kromatikus száma is 3.

18. *, ZH! Legyen $G$ olyan véges, egyszerű gráf, melynek 1000 csúcsa van és minden csúcs foka legalább 6. Igazoljuk, hogy $\nu(G)\geq 6$.