Gretimumo matrica

• Grafo $G = (V, U)$ gretimumo matrica yra kvadratinė $n$-osios eilės matrica $ S = [s_{ij}], i \in \{ 1, ..., n \}, j \in \{ 1, ..., n \}.$
• Jos elementas $s_{ij}$ apibrėžiamas taip: $$ s_{ij} = \begin{cases} 1, & (i, j) \in U, \\ 0, & (i, j) \notin U. \end{cases} $$
• Vienetukų skaičius $i$-ojoje eilutėje lygus $i$-osios viršūnės:
  • laipsniui neorientuotojo grafo atveju;
  • išėjimo puslaipsniui orientuotojo grafo atveju.

Pavyzdys - neorientuotas grafas

Pavyzdys - orientuotas grafas

Pratimas

Sudarykite duotų grafų gretimumo matricas

Atsakymas

Izomorfinių grafų gretimumo matricos

• Du grafai vadinami izomorfiškais, jei galima pirmojo grafo viršūnes pernumeruoti taip, kad gautume antrąjį grafą.
• Vieno grafo gretimumo matricą galimą transformuoti į kito paeiliui apkeitinėjant atitinkamas matricos eilutes ir stulpelius.
• Tegu $\varphi(x)$ - bijekcija, iš pirmojo grafo viršūnių į antrojo. Tada, jei $\varphi(i) = k$ ir $\varphi(j) = i (i \neq j, i \neq k)$, tai galima apkeisti stulpelių ir eilučių poras $(i, j)$.
• Taip gauname naują bijekciją $\varphi'(x)$, kurioje $\varphi'(i) = i, \varphi'(j) = k$.
• Su šia nauja bijekcija vėl galima atlikinėti apkeitimo žingsnį kol gausime $\forall x \in V: \varphi(x) = x$.

Pavyzdys

Pavyzdys

Pavyzdys

Pavyzdys

Pavyzdys

Pavyzdys

Pratimas

Sudarykite pirmojo grafo gretimumo matricą. Tada transformuokite ją į antrojo grafo gretimumo matricą.

Atsakymas

Įvertinimas

• Reikalingas atminties kiekis. Gretimumo matricai saugoti reikia $n^2$ elementų, nors dažnai didžioji jų dalis būna nuliai.
• Galimybė padaryti klaidą. Labai didelė esant dideliam viršūnių skaičiui. Nelabai aktualu rašant programą.
• Gretimų viršūnių radimas. Norint rasti viršūnes, gretimas $i$-ajai viršūnei, reikia nuskenuoti visą $i$-ąją gretimumo matricos eilutę ir rasti tokius $j$, kad $s_{ij} = 1$. Sudėtingumas $O(n)$.
• Išvada. Dažniausiai gretimumo matrica turi daugiau teorinę nei praktinę reikšmę. Tačiau ši struktūra gali būti naudinga, kuomet sprendžiamas uždavinys, kuriame:
  • Viršūnių skaičius nėra labai didelis;
  • Grafas yra tankus, t.y. turi daug briaunų.

Incidencijų matrica

• Grafo $G = (V, U)$ incidencijų matrica yra stačiakampė $(n \times m)$ formato matrica $ A = [a_{ij}], i \in \{ 1, ..., n \}, j \in \{ 1, ..., m \}. $
• Jos elementas $a_{ij}$ neorientuotojo grafo atveju apibrėžiamas taip: $ a_{ij} = \begin{cases} 1, & U_j = (i, k) \lor U_j = (k, i), k \in V, \\ 0, & \text{kitu atveju}. \end{cases} $
• Orientuotojo grafo atveju: $ a_{ij} = \begin{cases} 1, & U_j = (i, k), k \in V, \\ -1, & U_j = (k, i), k \in V, \\ 0, & \text{kitu atveju}. \end{cases} $

Pavyzdys - neorientuotas grafas

Pavyzdys - orientuotas grafas

Pratimas

Sudarykite duotųjų grafų incidencijų matricas.

Atsakymas

Įvertinimas

• Reikalingas atminties kiekis. Incidencijų matricai saugoti reikia $n \cdot m$ elementų, nors dažnai didžioji jų dalis būna nuliai.
• Galimybė padaryti klaidą. Labai didelė prie didesnių $n$ ir $m$ reikšmių. Nelabai aktualu rašant programą.
• Gretimų viršūnių radimas. Norint rasti viršūnes, gretimas $i$-ajai viršūnei, reikia nuskenuoti visą $i$-ąją incidencijų matricos matricos eilutę ir rasti tokius $j$, kad $a_{ij} = 1$. Kiekvienam tokiam $j$ tada reikia rasti visus $k$ tokius, kad $a_{kj} = 1$ ($-1$ orientuoto grafo atveju). Sudėtingumas $O(n \cdot m)$
• Išvada. Incidencijų matrica yra dar blogesnis grafo vaizdavimo būdas nei gretimumo matrica. Pritaikymas labiau teorinis nei praktinis.