Számítástudomány elemei gyakorlat
4. feladatsor (2002. okt. 3.)

1. Síkba rajzolhatók-e a következő gráfok? Ha igen, rajzold le élkereszteződés nélkül; ha nem, mutass bennük egy Kuratowski-gráffal topologikusan izomorf részgráfot!

   
   

   $$\unitlength 1.3mm \raisebox{1cm}{\hbox{$\left(\textup{a}\rig... ...x*{!}{25mm}{\includegraphics{abrak/sikbarajz_k5_pluszpont.eps}}$$
   
   
   
   
   $$\ \unitlength 10mm \raisebox{1.5cm}{\hbox{$\left(\textup{d}\... ...e(1,1){1}} \multiput(1,1)(0,2){2}{\line(1,-1){1}} \end{picture}$$
   
   

2. Legyenek a $G_n$ gráf csúcsai az $\{1,2,...,n\}$ számok, és két csúcs pontosan akkor legyen összekötve, ha a nekik megfelelő számok egyike osztója a másiknak. Bizonyítsuk be, hogy $n\geq16$ esetén $G_n$ nem síkba rajzolható! (Pótzh, 2001. máj.)

3. Egy hatelemű halmaz kételemű részhalmazai legyenek egy gráf pontjai. Két pont akkor legyen összekötve éllel, ha a nekik megfelelő részhalmazok diszjunktak (metszetük üres). Síkba $\textup{rajzolható-e}$ ez a gráf?

4. Hány csúcsa van annak a $G$ összefüggő 4-reguláris síkgráfnak, amelynek a síkba rajzolásakor 10 tartomány keletkezik? (Vizsga, 2001. dec.)

5. Egy 20 csúcsú konvex poliéder lapjainak száma 12. Hány oldala van az egyes lapoknak, ha tudjuk, hogy ez a szám minden lapra azonos? Melyik ez a poliéder?

6. Keress gyengén izomorfakat az alábbi gráfok között!
   
   $$\raisebox{.6cm}{\hbox{$\left(\textup{a}\right)$ }} \resizeb... ...ebox*{!}{1.7cm}{\includegraphics{abrak/gyenge_izomorfia_5.eps}}$$
   
   

7. 1. Rajzoltam egy nyolc csúcsú fát. Mi lehet a duálisa?

   2. Bizonyítsd be, hogy tetszőleges két $n$ csúcsú fa gyengén izomorf egymással!

8. Legyen $G$ egy 20 pontú, összefüggő, 3-reguláris síkgráf. Hány pontja van $G$ duálisának, $G^*$-nak? (ZH, 2001. máj.)

9. Egy nemzetközi konferencián egy asztalnál öt különböző ország egy-egy képviselője ül. Bizonyítsuk be, hogy van közöttük kettő, akiknek az országa nem szomszédos!