Kihagyás

Gráfok megvalósítása adatszerkezetekkel

Éllistás ábrázolás

Csúcsok felsorolása:

  • A rá illszkedő élek másik végponttal
  • A szomszédaival
    • (Jelen esetben az élek, mint önálló objektumok inszignifikánssak)
\[ \left\{1:\left[2,3\right],2:\left[1,3\right],3:\left[2,1,4\right],4:\left[,3\right]\right\} \]

Szomszédsági mátrix

\[ \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & 0 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 & 0 \\ 3 & 1 & 1 & 0 & 1 \\ 4 & 0 & 0 & 1 & 0 \\ \hline \end{array} \]

Illeszkedési mátrix (incidencia)

\(N_{i,j}\begin{cases} 1, \text{ha a csúcs éle illeszkedik} \\ 0, else \end{cases}\)

Címkézett / Súlyozott Gráf

Egy \(V\text{, bocsánat }G=(V,E,\varphi, f, C)\) ötöst címkézett gráfnak (élcímkézett) nevezünk, ha

  • \((V,E,\varphi)\) egy gráf???
  • \(f: E \to C\)
\[ C = \{fekete, piros, zöld, szaggatott\} \]

Ez egy gráf, ez egy gráf, ez egy gráf, ez egy gráf, ez egy grá-á-á-á-á-áf

C: számhalmaz esetén (\(\N, \Z, \R, \R^+, \R^+_0\)) \(\iff\) élsúlyozott gráf

A súlyokat akár az adjacenciamátrixba is beírhatjuk:

Ez nem felel meg a WCAG-nek :(

\[ \begin{bmatrix} 0 & 12 & 12 \\ 12 & 0 & 30 \\ 20 & 30 & 0 \end{bmatrix} \]

Adjacenciamátrix TÖBB, mint egy táblázat:

  1. Az \(M\) mátrix k-adig hatványa

    \(\left(M^k\right)_{i,j}\) \(i\)-ből \(j\)-be vezető \(k\) hosszú séták száma

  2. Valószínűségi címkék esetén (irányított gráf)

pl. %-os valószínűség minden élre(akár magára is)

Valószínűség gráf

\[M= \begin{bmatrix} 0 & 0.7 & 0.3 \\ 0.2 & 0.45 & 0.35 \\ 0.3 & 0.1 & 0 \end{bmatrix} \qquad \begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 0 & 0.7 & 0.3 \\ 2 & 0.2 & 0.45 & 0.35 \\ 3 & 0.3 & 0.1 & 0 \\ \hline \end{array} \]

\(M^k\): \(i, j\) elem: \(k\) lépésben \(i\)-ből indulva milyen eséllyel leszek \(j\)-ben

Alkalmazásai

  • Társasjáték
  • Nyelvészet
  • Google keresőmotor \(^{(\text{Pagerank})}\)

Cél: minimális költségű "hálózat kialakítása"

4 város közötti utak ára

Feladat: minimális költségű feszítőfa keresése

Input: egy véges, összefüggő, pozitív élsúlyozott rendezet gráf

Output: Egyik minimális össz-élsúlyú feszítőfa

Megoldás: Kruskal algoritmus

Init: vegyük azt a részgráfot, mely az összes csúcsot tartalmazza, de nincs éle

Ciklus amíg nem összefüggő:

  • Adjuk hozzá a részgráfunkhoz az (egyik) legkisebb súlyú élt azok közül, melyekkel nem keletkezik kör

Mohó algoritmus (greedy)

Minden lépésben az aktuálisan legjobbnak tűnő opciót választja Egy \(G\) gráf Euler-vonalán olyan vonalat értünk (vonal: nem ismétlünk éleket), melyben \(G\) összes éle szerepel

Mikor van G-bel Euler-vonal?

A kezdő- és végpont kivételével minden csúcson áthaladásonk \(\rightarrow\) páros fok

G-ben \(\exists\) zárt euler vonal \(\iff\) \(\forall\) csúcs foka páros