Illeszkedési mátrix

1. Sablon:Label Az **illeszkedési mátrix** (incidenciamátrix) egy gráf matematikai reprezentációja, amely azt mutatja meg, hogy a gráf csúcsai és élei hogyan kapcsolódnak egymáshoz.

Definíció

Legyen adott egy **G(V, E)** gráf, ahol $V$ a csúcsok halmaza, és $E$ az élek halmaza. Az illeszkedési mátrix egy $|V|\times |E|$-es méretű mátrix, amelyet $B$-vel jelölünk, és amelyben:

$B[i][j]=\{\begin{array}{cc}1,& \text{ha az i -edik csúcs és a j -edik él között kapcsolat van},\\ 0,& \text{ha az i -edik csúcs és a j -edik él között nincs kapcsolat}.\end{array}$

Példa

Tegyük fel, hogy egy egyszerű gráf:

• Csúcsok: $V=\{v_1,v_2,v_3\}$,
• Élek: $E=\{e_1,e_2,e_3\}$, ahol
  • $e_1$ köti össze $v_1$-et és $v_2$-t,
  • $e_2$ köti össze $v_2$-t és $v_3$-at,
  • $e_3$ köti össze $v_1$-et és $v_3$-at.

Az illeszkedési mátrix:

$B=\left[\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\end{array}\right]$

Irányított gráfok esetén

Irányított gráfoknál az illeszkedési mátrix figyelembe veszi az él irányát is:

$B[i][j]=\{\begin{array}{cc}1,& \text{ha az i -edik csúcs a j -edik él kezdőcsúcsa},\\ -1,& \text{ha az i -edik csúcs a j -edik él végcsúcsa},\\ 0,& \text{ha az i -edik csúcs nem kapcsolódik a j -edik élhez}.\end{array}$

Példa:

• $e_1$: $v_1\to v_2$,
• $e_2$: $v_2\to v_3$,
• $e_3$: $v_3\to v_1$.

Az irányított illeszkedési mátrix:

$B=\left[\begin{array}{ccc}1& 0& -1\\ -1& 1& 0\\ 0& -1& 1\end{array}\right]$

Tulajdonságok

1. Az illeszkedési mátrix sorai a gráf csúcsait, az oszlopai pedig az éleket reprezentálják.
2. Az egyszerű gráfok illeszkedési mátrixában minden oszlopban pontosan két darab 1-es van (az él két végpontja miatt).
3. Irányított gráf esetén minden oszlopban egy $1$ és egy $-1$ található.

Sablon:Ford

• Sablon:En: Sablon:T
• Sablon:De: Sablon:T