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

12. gyakorlat, 2005. december 5.

                                           Koblinger Egmont <egmont@cs.bme.hu>

Gráfok – Síkbarajzolhatóság

141. Síkbarajzolhatóak-e az ábrán látható gráfok?

142. Négy szomszéd mindegyike úgy épített utat a másik három házához, hogy azok nem keresztezik egymást. Egy

ötödik ember újabb házat épít.

• Bizbe, hogy nem tud úgy utakat építeni házától a másik négy házához, hogy az úthálózatban ne legyenek kereszteződések.

• Bizbe, hogy valamely három házhoz viszont tud kereszteződés nélkül utat építeni.

143. Bizonyítsuk be, hogy egy egyszerű síkbarajzolható gráfban nem lehet minden pont foka legalább 6.

144. Keressünk olyan 8 pontú gráfot, hogy se ő, se a komplementere ne legyen síkbarajzolható.

145. Keressük meg az összes 6 csúcsú nem síkgráfot.

146. Hány metszéspontja van maximálisan egy konvex 9-szög átlóinak?

147. Mutassuk meg, hogy egy nyolc csúcsú teljes gráfot a síkra lerajzolva legalább 10 élkeresztezés jön létre.

148. 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?

149. Egy hatelemű halmaz 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íkbarajzolható-e ez a gráf?

150. Tudjuk, hogy síkbarajzolható gráfok esetén n + t = e + 2. Hogyan módosul ez a képlet nem síkbarajzolható gráfok esetén?