×

Gráfelmélet 1. Mire használjuk a gráfokat? 2. Alapfogalmak 3. Irányított és nem irányított gráfok 4. Gráfok ábrázolási módjai 4.1. Illeszkedési mátrix 4.2. Éllista 4.3. Szomszédsági mátrix 4.4. Szomszédsági lista 5. Átalakítások 5.1. Szomszédsági mátrix → Illeszkedési mátrix 5.2. Szomszédsági mátrix → Éllista 5.3. Szomszédsági mátrix → Szomszédsági lista 5.4. Éllista → Szomszédsági lista 5.5. Illeszkedési mátrix → Éllista 5.6. Szomszédsági lista → Szomszédsági mátrix 5.7. Illeszkedési mátrix → Szomszédsági lista 5.8 Szomszédsági lista → Éllista 5.9 Szomszédsági lista → Illeszkedési mátrix 6. Gráfok bejárása 6.1. Szélességi bejárás 6.2. Mélységi bejárás 7. Legrövidebb utak meghatározása 7.1. Dijkstra algoritmusa 7.2. Útmátrix 8. Minimális feszítőfák 8.1. Kruskal algoritmusa 8.2. Prim algoritmusa 9. Ismeretellenőrzés Fagráfok: 10. A fák típusai 11. Gyökeres fák ábrázolása 12. Bináris fák ábrázolása 13. Bináris fák bejárása 14. Bináris keresőfa 15. Ismeretellenőrzés
Tartalom

Mire használjuk a gráfokat?

A gráfok segítségével nagyon jól lehet szemléltetni a matematika sokrétű alkalmazását. Meglepőnek tűnhet, hogy a matematikán kívül például az iparban, gazdaságban, közlekedésben és különböző szolgáltatásokban is használnak gráfokat. Például, az utazó ügynökök problémája, aki a lehető legrövidebb (legköltséghatékonyabb) útvonalon szeretnének eljutni különböző helyekre. A különböző útvonalak szemléletes megjelenítésére, modellezésére a gráfok tökéletesen alkalmasak.

Más alkalmazások:

  1. Facebook

    2. A Facebook közösségi portálhoz kapcsolható példa segítségével a gráfelmélet alapfogalmai nagyon jól szemléltethetők.

    A Facebook-felhasználók a gráf csúcsai. Bejelölésről vagy megjelölésről akkor beszélhetünk, ha egy személy ismerősnek kér fel egy másik embert. Ebben az esetben a kapcsolat még nem kölcsönös, hanem csak egy irányú, amit irányított élek használatával szemléltethetünk. Az irányított él a bejelölő személy felől a megjelölt személy irányába mutat. Az ismeretségek a gráf (irányítatlan) élei.

    Ha az egyik ember megjelöli a másikat vagy felkéri ismerősnek, úgy a kapcsolat még nem kölcsönös viszont ha a megjelölt személy visszajelöli az őt megjelölő személyt, akkor felőle egy irányított él fog az eredetileg megjelölő személy felé mutatni. Így a két csúcs között már két él van, irányuk ellentétes. A Facebook ezt a zavaró helyzetet a két irányított él „összeolvadásával" oldja fel, és egy irányítatlan él keletkezik, a két személy egymás ismerőse lesz. Ha már két személy ismerős, akkor nem lehet visszakövetni, hogy ki kezdeményezte a kapcsolatot.

    forrás: https://hirmagazin.sulinet.hu/hu/tudomany/grafok-mindenhol

  2. vízhálózatok
  3. vasúthálózatok
  4. úthálózatok
  5. családfa
  6. térkép színezés

    7. Például hogyan lehet egy térképet kiszínezni, minimális számú színt használva úgy, hogy két azonos színnel jelölt elem ne legyen egymás mellett.

Alapfogalmak

  1. Gráf: csomópontokból és az ezeket összekötő élekből áll.
  2. Szomszédos: egy él és egy pont szomszédos, ha a pont az él végpontja. Két pont szomszédos, ha él köti össze őket.
  3. Hurokél: olyan él, amely mindkét végpontjával ugyanahhoz a ponthoz illeszkedik.
  4. Többszörös él: ha két pontot több él is összeköt, többszörös élről beszélünk.
  5. Független élek: két él független, ha nem szomszédosak.
  6. Pont fokszáma: a ponthoz illeszkedő élek száma.
  7. Izolált pont: olyan pont, amelyhez egy él sem illeszkedik.
  8. Egyszerű gráf: olyan gráf, amely sem hurokélet, sem többszörös élet nem tartalmaz.
  9. Teljes gráf: olyan egyszerű gráf, amely bármely két különböző pontját él köti össze (bármely pont össze van kötve az összes többivel).
  10. Kiegészítő gráf: ha egy egyszerű, de nem teljes gráfot kiegészítünk teljes gráffá, akkor a gráf csomópontjait és a kiegészítésül megrajzolt élek az eredeti gráf kiegészítő gráfját adják.
  11. Részgráf: ha egy gráf bizonyos éleit, esetleg pontjait és a velük szomszédos éleket töröljük, akkor az adott gráf részgráfját kapjuk.
  12. Összefüggő gráf: egy olyan gráf, amely bármely két pontját út köti össze.
  13. Összefüggő komponens: ha egy gráf nem összefüggő pontjait olyan csoportokra osszuk, hogy az azonos csoportba eső bármely két pont között létezzen út, de különböző csoportokban levők között ne, akkor az azonos csoportban levő pontok és a hozzátartozó élek összessége a gráf egy összefüggő komponensét alkotják.
  14. Súlyozott gráf: egy olyan gráf, amelynek minden éléhez súlyt (értéket) rendelünk.

Irányított és nem irányított gráfok

Irányított gráfoknak nevezzük azokat a gráfokat, amelyeket csak az irányok betartásával lehet bejárni, nincs oda-vissza út. (Például G2)

Például lehetséges bejárás: x1 e1 x6 e3 x2 e6 x5 e10 x4 e9 x3 e8 x4

x1-ből eljuthatunk x6-ba, viszont fordítva nem az e1 élen keresztül

Nem irányított gráfoknak nevezzük azokat a gráfokat, amelyek nincsenek iránnyal ellátva, és működik az oda-vissza út. (Például G1)

Például lehetséges bejárás: x1e1 x2 e7 x5 e8 x1 e6 x4 e3 x3

x1-ből eljuthatunk x2-be és fordítva is az e1 élen keresztül

Gráfok ábrázolási módjai

Illeszkedési mátrix (pont-él mátrix, incidencia mátrix)

Adott egy gráf, amelynek n pontja és m éle van. Az adott gráfhoz hozzárendelhető egy n sorból és m oszlopból álló kétdimenziós tömb az alábbi szabály alapján:

15432e1e2e3e4e5e6e7e8
1 2 3 4 5 6 7 8
1 1 0 0 0 0 1 0 1
2 1 1 0 1 0 0 1 0
3 0 1 1 0 0 0 0 0
4 0 0 1 1 1 1 0 0
5 0 0 0 0 1 0 1 1
152436e1e2e3e4e5e6e7e8e9e10e11
1 2 3 4 5 6 7 8 9 10 11
1 1 0 0 0 1 0 0 0 0 0 0
2 0 0 1 1 0 1 1 0 0 0 0
3 0 1 0 1 0 0 0 1 1 0 0
4 0 0 0 0 0 0 1 1 1 1 0
5 0 0 0 0 1 1 0 0 0 1 1
6 1 1 1 0 0 0 0 0 0 0 0

Megjegyzések

Éllista

Adott egy gráf, amelynek n pontja és m éle van. Az adott gráfhoz hozzárendelhető egy m sorból és 2 oszlopból álló kétdimenziós tömb, amelynek minden sorában az adott sorszámú él egyik végpontja az első oszlopban, és a másik végpontja a második oszlopban található.

1 1 2
2 2 3
3 3 4
4 2 4
5 4 5
6 1 4
7 2 5
8 1 5
1 1 6
2 3 6
3 6 2
4 2 3
5 1 5
6 2 5
7 4 2
8 3 4
9 4 3
10 5 4
11 5 5

Szomszédsági mátrix (boole-mátrix, adjacenciamátrix)

Adott egy gráf, amelynek n pontja és m éle van. Az adott gráfhoz hozzárendelhető egy n sorból és n oszlopból álló kétdimenziós tömb az alábbi szabály alapján:

1 2 3 4 5
1 0 1 0 1 1
2 1 0 1 1 1
3 0 1 0 1 0
4 1 1 1 0 1
5 1 1 0 1 0
1 2 3 4 5 6
1 0 0 0 0 1 1
2 0 0 1 0 1 0
3 0 0 0 1 0 1
4 0 1 1 0 0 0
5 0 0 0 1 1 0
6 0 1 0 0 0 0

Megjegyzések

Szomszédsági lista (adjacencialista)

Adott egy gráf, amelynek n pontja van. Az adott gráfhoz hozzárendelhető egy n sorból és maximum m oszlopból álló kétdimenziós tömb, amelynek minden sorában az adott sorszámú ponttal szomszédos végpontok sorozata található.

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

Egyes feladatoknál célszerű a 0. oszlopba már beolvasásnál megadni a megfelelő sorban lévő elemek számát, így könnyebben tudunk hivatkozni egy adott elemre. Az alábbi kétdimenzios tömbben, a zölddel színezett oszlopban látható.

0 1 2 3
1 2 4 6
2 2 3 5
3 3 2 4 7
4 3 1 3 5

Átalakítások

Szomszédsági mátrix → Illeszkedési mátrix

Szomszédsági mátrix → Éllista

Szomszédsági mátrix → Szomszédsági lista

Éllista → Szomszédsági lista

Illeszkedési mátrix → Éllista

Szomszédsági lista → Szomszédsági mátrix

Illeszkedési mátrix → Szomszédsági lista

Szomszédsági lista → Éllista

Szomszédsági lista → Illeszkedési mátrix

Gráfok bejárása

Szélességi bejárás

út: 1 4 6 3 5 7 2

  • Kiválasztjuk a kiinduló csomópontot és elhelyezzük az ut tömbbe.
  • Az ut tömbbe elhelyezett minden elem esetén keressük az olyan egy él távolságra helyezkedő szomszédját, amely még nincs benne az ut tömbben.

Adatszerkezet

  • a gráf tárolása (például szomszédsági lista)
  • az út tárolása az ut vektor segítségével
  • a freq tömb segítségével tároljuk, hogy egy csomópont eleme az útnak
  • e – jelöli a feldolgozás alatt levő elem helyét az ut tömbben
  • u – jelöli az utolsó elem helyét az ut tömbben
1345762
0 1 2 3
1 2 4 6
2 2 3 5
3 3 2 4 7
4 3 1 3 5

Mélységi bejárás

út: 1 4 3 2 7 6 5

  • Kiválasztjuk a kiinduló csomópontot és elhelyezzük az ut tömbbe és a verembe.
  • Mindig, a verem tetején elhelyezendő elem esetén kivesszük az olyan egy él távolságra helyezkedő szomszédját, aki nem került még bele az ut tömbbe.
  • Az algoritmusnak akkor lesz vége, ha visszaléptünk a verem 0. szintjére.

Adatszerkezet

  • a gráf tárolása (például szomszédsági lista)
  • az út tárolása az ut tömb segítségével
  • a freq tömb segítségével tároljuk, hogy egy csomópont eleme az útnak
  • verem adatszerkezet tárolása a verem tömb segítségével
  • e – jelöli, hogy hol van az éppen feldolgozás alatt álló elem a veremben
1345762
0 1 2 3
1 2 4 6
2 1 3
3 3 2 4 7
4 2 1 3
5 1 6
6 2 1 5
7 1 3

Legrövidebb utak meghatározása

Adott egy élsúlyozott irányított gráf. Határozzuk meg a legrövidebb (legkisebb költségű) utak hosszát egy adott csomópontból a többibe.

Dijkstra algoritmusa

  • Kiválasztjuk a kiinduló csomópontot.
  • Feltöltjük az uth tömböt a direkt élek hosszával, illetve 0-át a kezdő csomópont helyére, a többibe pedig egy nagyon-nagy értéket helyezünk.
  • Megkeressük azt a legkisebb értéket az uth tömbben, amelyhez tartozó csomóponton keresztül még nem próbáltunk utat meghatározni. Ha ezen a csomóponton keresztül, létezik egy rövidebb út, aktualizáljuk az uth tömb elemeit.

Adatszerkezet

  • a gráf ábrázolására használt költségmátrix
  • az uth tömb, az utak hosszát tárolja
  • a freq frekvencia tömb, mutatja, hogy egy adott csomópontból próbált-e már utat építeni
1345623 8 1 1 5 3 2 2
kezdeti:
uth: 8 0 ∞ ∞ 1 ∞
freq: 0 0 0 0 0 0
végső:
uth: 6 0 3 3 1 9
freq: 1 1 1 1 1 1

Útmátrix

Egy adott gráfhoz hozzárendelhető egy n sorból és oszlopból álló kétdimenzióstömb, a következő szabályok alapján:

1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1
4 0 0 0 1 0 1 1
5 1 1 1 1 1 1 1
6 0 0 0 1 0 1 1
7 0 0 0 1 0 1 1
1436725

Minimális feszítőfák

A feszítőfa egy olyan fa, amely a gráf összes csúcsát tartalmazza és élei az eredeti gráf élei közül valók. A minimális feszítőfa egy összefüggő, irányítatlan gráfban található legkisebb élsúlyú feszítőfa. Egy gráf tetszőleges minimális feszítőfáját Kruskal illetve Prim algoritmusával határozzuk meg.

Kruskal algoritmusa

  • Rendezzük az éllistát az élek súlya szerint.
  • A csomópontokat külön komponensekbe helyezzük el.
  • Feldolgozzuk az éllistát, és ha egy él két olyan csomópontot köt össze, amelyek más-más komponensekhez tartoznak, kiválasztjuk, mint a feszítőfa éle és egyesítjük a két komponenset.

Adatszerkezet

  • éllista a gráf ábrázolására
  • egy egydimenziós tömb, amelynek n eleme van, azzal a jelentéssel, hogy a csomópontok melyik komponenshez tartoznak
1345624 5 3 3 3 2 2 2 3 4 2
1 2 3
1 1 4 2
2 3 5 2
3 4 6 2
4 5 6 2
5 2 5 3
6 3 4 3
7 3 6 3
8 1 6 4
9 2 3 4
10 1 2 5

Prim algoritmusa

feszítőfa: 3 5 6 4 1 2

  • Meghatározzuk a kezdő csomópontot, elhelyezzük a fába.
  • Meghatározzuk a fában elhelyezett csomópontból azt a kiinduló legkisebb súlyú élet, amely egy olyan csomóponthoz kapcsolódik, amely még nincs a fában.
  • Kiválasztjuk ezt az élet és csomópontot, elhelyezzük a fába.

Adatszerkezet

  • éllista súlyokkal
  • az n elemű freq tömb a fa csomópontjainak tárolására
  • freq[i] = 0, az i csomópont nincs a fában
  • freq[i] = 1, az i csomópont a fában van
1345624 5 3 3 3 2 2 2 3 4 2

A fák típusai

  1. Nyílt fák

    2. Ha egy nem irányított gráf összefüggő és körmentes, akkor azt (nyílt) fának nevezzük.

    Ha egy nem irányított gráf körmentes, akkor azt erdőnek nevezzük.

  1. Gyökeres fák

Gyökeresnek nevezzük az olyan fákat, amelyekben az egyik csomópontnak kitüntetett szerepe van a többihez képest, ezt a csomópontot gyökérnek nevezzük.

Jellemzők:

  • szint: azt jelöli, hogy egy csomópont hány él távolságra van a gyökértől (a gyökér tetszés szerint és feladattól függően lehet a 0. vagy az 1. szinten)
  • magasság: a gyökér és a tőle legtávolabb eső csomópont közötti élek száma → Például 4
  • leszármazott; ős → Például 3 őse az 1 csp
  • közvetlen (direkt) leszármazott: 1 él távolságra levő leszármazott
  • levél: olyan csomópont, amelynek nincs leszármazottja → Például 4 5 8 9 11 12 13
  • gyökér: olyan csomópont, amelynek nincs szülője → 1
1 2 8 1 1 5 4 3 10 6 7 9 11 13 12 1. szint2. szint3. szint4. szint5. szintgyökérlevél
a.) ábra
  1. Bináris fák

    2. A bináris fa olyan fa, amelyben bármely csomópontnak legtöbb 2 direkt leszármazottja lehet: egy jobboldali és egy baloldali leszármazott.

6 4 7 9 11 13 12 10 2 1 5 3 8
b.) ábra

Gyökeres fák ábrázolása

  1. Apa tömb

    2. Minden csúcsnak a direkt ősét egy egydimenziós tömb segítségével adjuk meg. A vektor indexe a csomópont, tartalma pedig jelöli azt a csomópontot, amelyhez kapcsolódik.

  2. Teljes zárójeles alak

    3. A gyökértől kiindulva zárójelekbe helyezzük a leszármazottakat. A levelek után *-ot írunk a zárójelek közé.

    példa: a.) ábra 1 ( 2( 5(*) ), 3( 6(8(*) ), 7(9(*), 10(13(*)), 11(*), 12(*))), 4(*) )

Bináris fák ábrázolása

  1. Apa tömb

    2. Minden csúcsnak a direkt ősét egy egydimenziós tömb segítségével adjuk meg.

  2. Teljes zárójeles alak

    3. A gyökértől kiindulva zárójelekbe helyezzük a leszármazottakat. Ha valamelyik csomópontnak csak egy leszármazottja van, *-ot írunk a másik helyére.

    példa: b.) ábra 1 ( 2(4(8,*), 5), 3(6(9,10(11,12)), 7(*,13)) )

  3. Bináris fa standard alakja

    4. Megjelöljük a gyökeret, majd minden egyes csomópontnak a jobb- és baloldali leszármazottját egy-egy egydimenziós tömb, vagy egy 2 soros és n oszlopú mátrix segítségével adjuk meg (n- csomópontok száma). A csomópontot a tömb sorszáma jelöli. Ha a csomópontnak nincs leszármazottja, a nulla értékkel jelöljük

    2 4 6 8 0 9 0 0 0 11 0 0 0 BAL
    3 5 7 0 0 10 13 0 0 12 0 0 0 JOBB
    1 2 3 4 5 6 7 8 9 10 11 12 13
  4. Bináris fa bináris alakja

    5. A bináris fák csomópontjait 0-1 sorozatoknak tekinthetjük. A gyökeret „1” jelöli. Ha a egy csomópont jelölése, akkor a bal és a jobb leszármazottjait (ha van) a0-val és a1-gyel jelöljük.

    példa: (1,1) (2,10) (3,11) (4,100) (5,101) (6,110) (7,111) (8,1000) (9,1100) (10,1101) (11,11010) (12,11011) (13,1111)

6 4 7 9 11 13 12 10 2 1 5 3 8 1100101110001111111101110110011011101011011

Bináris fák bejárása

  1. Preorder (gyökérkezdő) bejárás: gyökér, bal, jobb

    2. példa: D A C K G P L B F O M I H

  2. Inorder (gyökérközepű) bejárás: bal, gyökér, jobb

    3. példa: C A G K P L D F O B I M H

  3. Postorder (gyökérvégző) bejárás: bal, jobb, gyökér

    4. példa: C G L P K A O F I H M B D

DAG BC MF P K HOIL

Bináris keresőfa

Bármely bal oldali részfa minden csomópontja kisebb, mint a gyökere.

Bármely jobb oldali részfa minden csomópontja nagyobb, mint a gyökere.

8 10 6 4 7 9 11 13 12 15 16 14 2 1 5 3