Gráfelmélet - felmérő

Felmérő gráfelméletből kedden, máj. 27-én.

Pontozás:

Lehet pluszpontokat felhasználni.

Tétel

Hivatalból 2 pont jár. Minden feladat 1 pontot ér.

1.

Adott egy nemirányított gráf az alábbi szomszédsági listákkal. Legalább hány élet kell törölni ahhoz, hogy két összefüggő komponense legyen és miért? (var 70)

    1: 2,4,5
    2: 1,3
    3: 2,5,4
    4: 1,3
    5: 3,1

Megoldás

0 él törlése nem elég, mert jelenleg a gráf összefüggő (egy komponense van). 1 él törlése szintén nem elég (rendre megpróbáljuk őket törölni, a gráf minden esetben összefüggő marad). 2 él törlése elég, pl. a [2,1], [2,3] pontok törlése izolálja a 2-es csomópontot.

2.

Adott egy 6 pontú nemirányított gráf melynek élei: [1,2], [1,4], [2,3], [3,5], [3,6], [4,5], [5,6]. Hány különböző út van az 1-ből a 6-ba? Írjuk le őket! (var 84)

Megoldás

Végigpróbáljuk az összes lehetőséget, 4 út van:

    1, 2, 3, 6
    1, 2, 3, 5, 6
    1, 4, 5, 6
    1, 4, 6, 3, 6

3.

Egy 8 pontú irányított gráf élei: (1,2), (2,3), (3,1), (4,5), (6,5), (5,7), (7,6), (7,4), (8,7). Legalább hány élet kell hozzáadni ahhoz, hogy erősen összefüggő legyen? (var 76)

Megoldás

Jelenleg a gráfnak három erősen összefüggő komponense van:

    4, 5, 6, 7
    8
    1, 2, 3

Ezek közül csak a másodikból az elsőbe van átjárás. Még el kellene tudjunk jutni az elsőből a másodikba, a harmadikból az első kettőbe, illetve a másodikból a harmadikba.

Ez egy él hozzáadásával nem megoldható (mert a harmadik komponenst figyelve vagy csak oda, vagy csak onnan kifelé tud majd vinni).

Két él viszont már elég: az egyik a harmadik komponensból a másodikba, a másik az elsőből a harmadikba, pl. (1,8) és (7,1).

4.

Egy 5 pontú irányított gráf élei: (1,2), (1,5), (2,1), (2,3), (2,5), (3,4), (5,2), (5,4). Adjunk meg egy maximális hosszúságú utat 1-ből 4-be! (var 82)

Megoldás

Egy ilyen út az 1 5 2 3 4, melynek hossza 4. Hosszabb nem lehet, mert a pontok nem ismétlődhetnek és már szerepel rajta minden pont.

5.

Adott egy 9 pontú fa, melynek ősvektora (apák tömbje): (8,8,8,2,6,2,9,0,2). Adjuk meg, hogy hány levele van a fának és soroljuk fel a 2-es csomópont leszármazottait! (var 74)

Megoldás

A fának 5 levele van: 1, 3, 4, 5, 7. A 2-es csomópont leszármazottai: 4, 5, 6, 7, 9.

6.

Adott egy 6 pontú fa a mellékelt szomszédsági mátrixszal. Írjuk le az összes olyan pontot, melyet gyökérnek választva a fának maximális számú levele lesz! (var 87)

    0 1 0 0 0 1
    1 0 1 1 1 0
    0 1 0 0 0 0
    0 1 0 0 0 0
    0 1 0 0 0 0
    1 0 0 0 0 0

Megoldás

Végigpróbáljuk az összes megválasztást, az 1-es és 2-es pontot választva négy levele lesz, a többi esetén kevesebb.

7.

Végezzünk mélységi bejárást az 1. feladat gráfján az 1-es csomópontból indulva! Írjuk le a csomópontok meglátogatásának egy lehetséges sorrendjét, illetve, hogy hogyan alakul bejáráshoz felhasznált adatszerkezet!

Megoldás

A verem alakulása és a végső sorrend az adott pontok szomszédainak sorrendjétől függ (melyik szomszéd felé indulunk előbb).

Egy lehetséges megoldásban a verem:

    1
    1 2
    1 2 3
    1 2 3 4
    1 2 3
    1 2 3 5
    1 2 3
    1 2
    1

Ekkor a pontok bejárási sorrendje: 1 2 3 4 5.

8.

Hány olyan n pontú nemirányított gráf létezik, amelyben az 1-es pont fokszáma 3? (n egy pozitív egész)

Megoldás

Az 1-es pontot nem tartalmazó algráfban az élek megválasztása tetszőleges, erre van 2^komb(n-1,2) lehetőségünk.

Az 1-es pont három másikkal kell szomszédos legyen, erre van comb(n-1,3) lehetőségünk ha n ≥ 4, különben egy sincs.

A válasz tehát:

    {
        0, ha n < 4
        comb(n-1,3) * 2^comb(n-1,2), ha n ≥ 4
    }