8. Gráfok mátrixai

Question 1

Adjacencia/csúcsmátrix: 1. Legyen $G=(V,E)$ egy tetszőleges egyszerű irányítatlan gráf, $V={v_1, …, v_n}$ a csúcsok egy tetszőleges, rögzített felsorolása. A G gráf csúcsmátrixa az $A∈ {0, 1}^{n×n}$ mátrix, ahol

Answer 1

1. Legyen $G=(V,E)$ egy tetszőleges egyszerű irányítatlan gráf, $V={v_1, …, v_n}$ a csúcsok egy tetszőleges, rögzített felsorolása. A G gráf csúcsmátrixa az $A∈ {0, 1}^{n×n}$ mátrix, ahol
   $[A]_{i,j} =\begin{cases}1 & { v_i, v_j } \in E - húzódik\ köztük\ él \0 & ha\ nem\end{cases}$

Question 2

Adjacencia/csúcsmátrix: 2. Ha $G$ irányított és egyszerű

Answer 2

2. Ha $G$ irányított és egyszerű
   $[A]_{i,j} :=\begin{cases}+1 & ha\ (v_i, v_j) \in E \1 & ha\ (v_j, v_i) \in E\ 0 & ha\ egyik\ sem\end{cases}$

Question 3

Adjacencia/csúcsmátrix: 3. Ha G irányítatlan de tetszőleges, van multiplicitása, $m(e) ∈ \N$

Answer 3

3. Ha G irányítatlan de tetszőleges, van multiplicitása, $m(e) ∈ \N$
   $[A]_{i,j} :=\begin{cases}m({v_i , v_j}) & bármikor\2m ({v_j , v_i})\ hurokél & j=i\ 0 & ha\ {v_i , v_j} \notin E\end{cases}$

Question 4

Adjacencia/csúcsmátrix: 4. Ha G súlyozott élű, melyben hurokélek lehetnek de többszörös élek nem, w:E→ R + pozitív súlyfüggvény, ekkor a csúcsmátrix $A∈ R^{n×m}_+$, ahol

Answer 4

4. Ha G súlyozott élű, melyben hurokélek lehetnek de többszörös élek nem, w:E→ R + pozitív súlyfüggvény, ekkor a csúcsmátrix $A∈ R^{n×m}+$, ahol
   $[A]{i,j} :=\begin{cases}w(v_i , v_j ) & ha\ {v_i , v_j} ∈ E, i \neq j\ 0\ vagy\ +\infty & ha\ {v_i , v_j} \notin E\end{cases}$

Question 5

Tulajdonságok: elemi összefüggések

Answer 5

1. Az A csúcsmátrix tetszőleges sorában/oszlopában levő elemek összege a megfelelő csúcs fokszámával egyenlő, azaz$\sum_{j=1}^n[A]{ij}= \delta(v_i)$
   és
   $\sum{i=1}^n[A]_{ij}= \delta(v_j)$
2. $\sum_{i=1}^n[A]_{ii}=Sp(A)=Tr(A)$
   a mátrix nyoma (Spur/Trace) a főátlóban lévő elemek összege
3. Az A csúcsmátrix összes elemének összege az élek kétszeresével egyenlő, azaz
   $\sum_{i=1}^n \sum_{i=j}^n [A]_{ij}= 2*|E|$

Question 6

Élmátrix: 1. ha $G$ egyszerű
Legyen $G=(V,E)$ tetszőleges gráf, csúcsainak és éleinek egy adott felsorolása legyen $V=(v_1, …, v_n)$ és $E=(e_1, …, e_m)$. Ekkor a gráf élmátrixa $B∈ \R^{n×m}$ ahol $1 ≤ i ≤ n , 1 ≤ j ≤ m$ esetén

Answer 6

1. ha $G$ egyszerű, akkor legyen
   $[B]_{ij} := 1$ ha $v_i ∈ e_j$
   $0$ egyébként

Question 7

Élmátrix: 2. ha $G$-ben többszörös és hurokélek is lehetnek
Legyen $G=(V,E)$ tetszőleges gráf, csúcsainak és éleinek egy adott felsorolása legyen $V=(v_1, …, v_n)$ és $E=(e_1, …, e_m)$. Ekkor a gráf élmátrixa $B∈ \R^{n×m}$ ahol $1 ≤ i ≤ n , 1 ≤ j ≤ m$ esetén

Answer 7

2. ha $G$-ben többszörös és hurokélek is lehetnek, akkor legyen
   $[B]_{ij} := k$ ha $v_i ∈ e_j$ $k$-szoros él nem hurokél
   $2k$ ha $v_i ∈ e_j$ $k$-szoros hurokél
   $0$ egyébként

Question 8

Élmátrix: 3. ha $G$ irányított
Legyen $G=(V,E)$ tetszőleges gráf, csúcsainak és éleinek egy adott felsorolása legyen $V=(v_1, …, v_n)$ és $E=(e_1, …, e_m)$. Ekkor a gráf élmátrixa $B∈ \R^{n×m}$ ahol $1 ≤ i ≤ n , 1 ≤ j ≤ m$ esetén

Answer 8

3. ha $G$ irányított, akkor legyen
   $[B]_{ij} := 1$ ha $e_j$ nem hurokél és kezdőpontja $v_i$
   $-1$ ha $e_j$ nem hurokél és végpontja $v_i$
   $0$ egyébként

Question 9

Mikor használjunk élmátrixot és mikor csúcsmátrixot?

Answer 9

A $[B]$ élmátrixot akkor használjuk ha kevés az él, az $[A]$ csúcsmátrixot akkor használjuk ha sok az él.

Question 10

Adjacencia mátrix hatványa:

Answer 10

• Az adjacencia mátrix $(k)$-adik hatványának $(i,j)$-edik eleme megadja a $(v_i)$ és $(v_j)$ közötti pontosan $(k)$ hosszúságú utak számát. - $[A^k]_{ij}$
• Az $(A^3)$ mátrix főátlójában lévő elemek összege megadja a háromszögek számát a gráfban, figyelembe véve, hogy minden háromszög hatszor jelenik meg (minden csúcs háromszor számít).

Tetszőleges $k ∈ \N, k>1$ természetes számra

$[A^k]_{ij} =$ a $v_i$ és $v_j$ csúcsok között húzódó, pontosan $k$ hosszúságú utak száma, és az útban levő köröket $2×$ kell számolni.
* $Sp[A^3]=G$-ben a háromszögek száma * 6.