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

12. gyakorlat, 2004. december 5.

                                           Koblinger Egmont <egmont@cs.bme.hu>

Gráfok – Síkbarajzolhatóság

121. Van-e olyan (legalább két pontú) gráf, melyben minden pont foka különböző?

122. Van-e olyan egyszerű gráf, amelyben a pontok foka rendre

(a) 1, 2, 2, 3, 3, 3; (b) 1, 1, 2, 2, 3, 4, 4; (c) 5, 5, 5, 6, 6, 6, 7, 7, 7;  (d) 1, 2, 2, 3, 4, 4, 5, 6, 6; (e) 1, 1, 3, 3, 3, 3, 5, 6, 8, 9; (e) 2, 3, 3, 4, 5, 6, 7 ?

123. Igazoljuk, hogy tetszőleges gráfban a páratlan fokú pontok száma páros.

124. Hány olyan egyszerű gráf van, melynek fokszámai: 2,3,3,4,6,6,6?

125. Milyen komponensekből állhat egy gráf, ha minden pontjának a foka legfeljebb 2?

126. Hány 3 hosszú kör található abban a gráfban, amelyet az n szögpontú K_{n} teljes gráfból kapunk, ha egy élét elhagyjuk?

127. Rajzoljuk fel az összes 3, 4, ill. 5 pontú fát (az izomorfakat csak egyszer).

128. Hány olyan, páronként nem izomorf 5 pontú és 8 élű egyszerű gráf létezik, melyben pontosan két darab harmadfokú pont van?

129. Hány páronként nem izomorf 4 pontú és 3 élű egyszerű irányított gráf létezik?

130. Egy gráf izomorf a komplementerével. Mutassuk meg, hogy összefüggő.

131. Rajzoljunk a komplementerével izomorf 5, ill. 6 pontú gráfot.

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

133. 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.

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

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

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

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

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

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

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

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