Auzokidetasun-matrize

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu

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

Auzokidetasun-matrizearen eraikuntza grafo batetik abiatuta[aldatu | aldatu iturburu kodea]

  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[aldatu | aldatu iturburu kodea]

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

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



   \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[aldatu | aldatu iturburu kodea]

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

2. irudiko grafo zuzenduaren auzokidetasun-matrizea hau da:



   \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[aldatu | aldatu iturburu kodea]

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



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

Ikus, gainera[aldatu | aldatu iturburu kodea]

Commonsen badira fitxategi gehiago, gai hau dutenak: Auzokidetasun-matrize Aldatu lotura Wikidatan