Kihagyás

3. gyakorlat

Summary

Gráfok wow

Gráfok

\(G\) gráf: \(G = (V, E)\), ahol \(V\) a csúcsok halmaza, \(E\) az élek halmaza. \(E \subseteq V \times V\)

Lényeges, hogy a gráf irányított, vagy irányítatlan. Reprezentáció függő.

"Egy élt csúcspárként adok meg pl.: \((u,u) : u \in V\) (ez egy hurok)"

Mi csak egyszerű gráfokkal fogunk foglalkozni, tehát nincsenek hurokélek és párhuzamos élek.

Irányított/irányítatlan gráf

Irányított gráf az az, ahol \((u,v) \in G\) de \((v,u) \not\in G\), irányítatlan gráfnál ez a feltétel teljesül.

Ábrázolási módok:

  • Szomszédossági mátrix
  • Szomszédossági lista

  • Szöveges megadás

    • irányított (jele: ->)

      1 -> 2;4 2 -> 4;5 3 -> 1 5 -> 2;3

    • irányítatlan (jele: -)

      1 - 2;4 2 - 4 3 - 4

Szomszédsági mátrix

Note

Két csúcsot akkor kötünk össze ha az adott sor/oszlopban 1 szerepel, egyébként nincsenek összekötve.

Example

1 -> 2;4
2 -> 4;5
3 -> 1
5 -> 2;3

Mátrixként reprezentálva:

1 2 3 4 5
1 | 0 1 0 1 0
2 | 0 0 0 1 1
3 | 1 0 0 0 0
4 | 0 0 0 0 0
5 | 0 1 1 0 0

Hint

Irányítatlan gráfoknál a szomszédsági mátrix minden esetben szimetrikus, ezért elég a felső háromszöget tárolni.

Szomszédossági lista

Note

Minden tömbben lévő elemhez tartozik egy láncolt lista ami csak a szomszédokat tartalmazza.

Tömbben tárolt láncolt listák:

Example

[1]: 2 -> 4
[2]: 4 -> 5
[3]: 1
[4]: []
[5]: 2 -> 3
Mátrix to szomszédsági lista

Disclaimer: Might not work

    matrix.foreach(x => x.foreach(y => if y /= null then p = list[x]; while p.next /= null { p=p.next }; p.next=y else continue; ) )

Befok, kifok

Befok[i] = hány él mutat i csúcsba

Kifok[i] = hány él indul ki i csúcsból (láncolt lista hossza)

Transzponált gráf

Minden él irányát megfordítjuk

Komplementer/Különbség gráf

Csak azokat az éleket tartjuk meg, amelyek nincsenek benne az eredeti gráfban. Egy gráf komplementer gráfja az a gráf, amelynek csúcshalmaza megegyezik az eredetivel, de az élhalmaza az az eredeti gráf élhalmazának komplementere. Magyarul ha az eredeti gráfban két csúcs között nincs él, akkor a komplementer gráfban van, és fordítva.