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

12. gyakorlat, 2006. december 6.

                                    Koblinger Egmont <egmont@cs.bme.hu>

Gráfok 2.

136. Rajzoljuk le a K_{4} gráf duálisát!

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

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

141. Hány különböző minimális súlyú feszítőfája van az alábbi gráfnak?

142. Mely k pozitív egészekre adható meg olyan, 2000 címkézett csúcsot és 2000 élet tartalmazó egyszerű összefüggő G gráf, amelyre igaz a következő: G-ben a 2000 él közül adható egynek 2 egységnyi, 1999nek pedig 1 egységnyi súly úgy, hogy a G-ből kiválasztható különböző minimális súlyú feszítőfák száma éppen k legyen?

143. Legyen G egy egyszerű irányítatlan gráf és A a szomszédossági mátrixa. Mutassuk meg, hogy az A^{3} mátrix főátlóbeli elemeinek összege a G-beli háromszögek számának hatszorosa.

144. Bizonyítsuk be, hogy egy irányítatlan egyszerű gráf szomszédossági mátrixában akkor és csak akkor van két sor, melyek skaláris szorzata legalább 2, ha a gráfban található pontosan 4 hosszúságú kör.

145. Legyen B egy egyszerű irányítatlan G gráf illeszkedési mátrixa, D pedig G élgráfjának szomszédossági mátrixa. Mit mondhatunk a B^{T} B − D mátrixról?