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

11. gyakorlat, 2006. november 29.

                                    Koblinger Egmont <egmont@cs.bme.hu>

Gráfok – Bevezetés

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

118. 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;

(f) 2, 3, 3, 4, 5, 6, 7 ?

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

120. Van-e olyan 100 csúcsú egyszerű gráf, amelyben minden pont foka 54?

121. Bizonyítsuk be, hogy minden fában van olyan pont, amit az összes leghosszabb út tartalmaz.

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

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

124. Hány olyan páronként nem izomorf 6 pontú összefüggő egyszerű gráf létezik, melyben két másodfokú és négy harmadfokú pont van?

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

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

127. Egy négyreguláris (minden csúcs fokszáma 4) összefüggő gráfból töröljük egy fa éleit. Bizonyítsuk be, hogy a maradék legalább két kört tartalmaz.

128. Az előre megszámozott (címkézett) n darab pont közé hányféleképp húzhatunk be éleket úgy, hogy egyszerű gráfhoz jussunk?

129. Hány különböző olyan körmentes gráf létezik n címkézett ponton, amelyben az élek száma valamilyen n − 1-nél kisebb fix k szám, és amiben pontosan n − k − 1 izolált pont van?

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

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

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

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

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

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