Auzokidetasun-matrize

Auzokidetasun-matrizea Matrize karratu bat da, erlazio bitarrak adierazteko erabiltzen dena..

Auzokidetasun-matrizearen eraikuntza grafo batetik abiatuta

1. Zero matrize bat sortzen da, zeinen zutabeek eta errenkadek grafoaren erpinak adierazten dituzten.
2. Bi erpin lotzen duen ertz bakoitzeko, 1 gehitu behar diogu matrizeko dagokion kokagunean lehendik dagoen balioari.

   Ertza begizta bat bada eta grafoa ez zuzendua bada, orduan 2 gehitzen da 1-aren ordez.

Azkenik, matrize bat lortzen da, erpin (elementuak) bikoteen arteko ertzen (erlazioak) kopurua adierazten duena .

Grafo bakoitzeko auzokidetasun-matrize bakar bat existitzen da (errenkaden edo zutabeen permutazioak kontuan izan gabe), eta alderantziz.

Grafo ez zuzenduaren adibidea

1. irudia: Grafo ez zuzenduaren adibide bat, zeinetarako auzokidetasun-matrizea kalkulatzen den.

1. irudiko grafo ez zuzenduaren auzokidetasun-matrizea hau da:

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

Grafo zuzenduaren adibidea

2. irudia: Grafo zuzenduaren adibide bat, zeinetarako auzokidetasun-matrizea kalkulatzen den.

2. irudiko grafo zuzenduaren auzokidetasun-matrizea hau da:

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

Auzokidetasun-matrizearen propietateak

• Grafo ez zuzenduaren kasuan auzokidetasun-matrizea simetrikoa da.
• C_i,j(k) bideen kopurua, i adabegitik j adabegitarako k hertz zeharkatuz, auzokidetasun-matrizearen k-garren berreturaren elementu batek ematen du:

${\displaystyle C_{i,j}(k)=[\mathbf {A} ^{k}]_{ij}}$

Ikus, gainera

• matrize laplaciarra

Kanpo estekak