illeszkedési mátrix

Magyar

Kiejtés

• IPA: [ ˈilːɛskɛdeːʃimaːtriks]

Főnév

illeszkedési mátrix

1. (matematika, gráfelmélet) 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{cases}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{cases}}$

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={\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\end{bmatrix}}$

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{cases}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{cases}}$

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={\begin{bmatrix}1&0&-1\\-1&1&0\\0&-1&1\end{bmatrix}}$

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ó.

Fordítások

• angol: incidence matrix (en)
• német: Inzidenzmatrix (de)

További információk

• illeszkedési mátrix - Értelmező szótár (MEK)
• illeszkedési mátrix - Etimológiai szótár (UMIL)
• illeszkedési mátrix - Szótár.net (hu-hu)
• illeszkedési mátrix - DeepL (hu-de)
• illeszkedési mátrix - Яндекс (hu-ru)
• illeszkedési mátrix - Google (hu-en)
• illeszkedési mátrix - Helyesírási szótár (MTA)
• illeszkedési mátrix - Wikidata
• illeszkedési mátrix - Wikipédia (magyar)