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

11. gyakorlat, 2005. november 28.

                                    Koblinger Egmont <egmont@cs.bme.hu>

Gráfok – Bevezetés

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

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

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

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

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

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

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

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

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

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

134. Rajzoljuk le azt a gráfot, melynek pontjai a 4 hosszú nullákból és egyesekbl álló sorozatok, és két csúcs akkor van éllel összekötve, ha egyik a másikból egy „forgatással” megkapható, azaz ha az egyik a (b_{1}, b_{2}, b_{3}, b_{4}), akkor a másik a (b_{2}, b_{3}, b_{4}, b_{1}) sorozathoz tartozó pont.

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

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

137. Hány különböző fa adható meg n ponton?

138. Rajzoljuk le a 447741 Prüfer-kódú fát.

139. Egy F fa Prüfer-kódja csupa különböző számból áll. Hogyan jellemezhetjük F -et?

140. Válasszuk meg az x értékét úgy, hogy az alábbi sorozat egy olyan fa Prüfer-kódja legyen, amelyben minden pont fokszáma páratlan szám. Adjuk is meg ezt a fát! A sorozat: 1, 1, 5, x, 6, 6, 8. (Egy n csúcsú fa Prüfer-kódjába most beleértjük annak (n − 1)-edik, n-nel egyenlő elemét is.)