Relációk mátrixos ábrázolása

Egy relációt szemléletesen és könnyen kezelhető módon ábrázolhatunk mátrix segítségével. A mátrixos ábrázolás különösen hasznos számítógépes feldolgozásnál és gráfok vizsgálatánál.

Formális leírás

Legyen A = {a₁, a₂, …, an} egy halmaz, és R egy reláció A-n. A reláció mátrixa egy n×n-es 0–1 mátrix M, ahol:

A sorok és oszlopok ugyanabba a sorrendben vannak indexelve az A elemeivel. Az M[i,j] bejegyzés 1, ha a_i-ből a_j-ig kapcsolat van, egyébként 0.

Példa

Legyen A = {1,2,3}, R = { (1,2), (2,3) }.

A mátrix:

1. sor (1-hez): kapcsolódik 2-höz, így a második bejegyzés 1. 2. sor (2-höz): kapcsolódik 3-hoz, így a harmadik bejegyzés 1. Minden más 0.

Tulajdonságok mátrixos formában

• A reflexív relációknál a főátlóban 1-esek vannak.
• A szimmetrikus relációknál a mátrix szimmetrikus a főátlóra.
• Ha a reláció tranzitív, a mátrix hatványozásával (kompozícióval) előállíthatók az új kapcsolatok.
• A mátrixos ábrázolás megkönnyíti a számítógépes algoritmusok megvalósítását.

Összefoglalás

A relációk mátrixos ábrázolása egyszerű módja a kapcsolatok rögzítésének: a halmaz elemei közötti összes kapcsolatot 0–1 mátrix formájában mutatjuk meg. Ez különösen hasznos a gráfok elemzésében és a számítógépes feldolgozásban.

Gyakorló feladat