illeszkedési mátrix

• IPA:

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.

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

${\displaystyle B={\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}}}$

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

• Csúcsok: ${\displaystyle V=\{v_{1},v_{2},v_{3}\}}$,
• Élek: ${\displaystyle E=\{e_{1},e_{2},e_{3}\}}$, ahol
  • ${\displaystyle e_{1}}$ köti össze ${\displaystyle v_{1}}$-et és ${\displaystyle v_{2}}$-t,
  • ${\displaystyle e_{2}}$ köti össze ${\displaystyle v_{2}}$-t és ${\displaystyle v_{3}}$-at,
  • ${\displaystyle e_{3}}$ köti össze ${\displaystyle v_{1}}$-et és ${\displaystyle v_{3}}$-at.

Az illeszkedési mátrix:

${\displaystyle B={\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\end{bmatrix}}}$

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

${\displaystyle B={\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:

• ${\displaystyle e_{1}}$: ${\displaystyle v_{1}\to v_{2}}$,
• ${\displaystyle e_{2}}$: ${\displaystyle v_{2}\to v_{3}}$,
• ${\displaystyle e_{3}}$: ${\displaystyle v_{3}\to v_{1}}$.

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

${\displaystyle B={\begin{bmatrix}1&0&-1\\-1&1&0\\0&-1&1\end{bmatrix}}}$

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 ${\displaystyle 1}$ és egy ${\displaystyle -1}$ található.

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

• 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)