Matrika sosednosti

Matrika sosednosti je eden izmed načinov prikaza grafa v obliki matrike. Druga oblika prikaza grafa je incidenčna matrika. Matrika sosednosti pove katero vozlišče (točka) je sosednje danemu vozlišču.

Matrika sosednosti končnega grafa, ki ima vozlišč, je matrika z razsežnostjo , ki ima elemente zunaj diagonale enake , kar pomeni, da so to povezave med vozliščem in . Elementi na diagonali so v odvisnosti od dogovora, enkratno ali dvakratno število povezav iz vozlišča v samega sebe (to so zanke). Grafi so lahko usmerjeni ali neusmerjeni.

Odnose med grafi in lastnimi vrednostmi in lastnimi vektorji v matrikah sosednosti proučuje spektralna teorija grafov.

ZgledUredi

V naslednjem zgledu neusmerjenega označenega grafa je dodana tudi njegova matrika sosednosti

graf matrika sosednosti
   

Matrika sosednosti za dvodelne grafeUredi

Matrika sosednosti za dvodelni graf (bipartitni graf), ki ima   in   vozlišč ima obliko

 

kjer je

  •   matrika z razsežnostjo  
  •   ničelna matrika
  •   enolično predstavlja dvodelni graf, ki ga predstavlja dvososednostna matrika.

ZnačilnostiUredi

  • Predpostavimo, da imamo dva usmerjena ali dva neusmerjena grafa   in  , ki imata matriki sosednosti   in  . Potem sta   in   izomorfna, če in samo, če obstoja permutacijska matrika   tako, da velja
 .
Pri tem sta   in   podobni matriki (imata isti karakteristični polinom, minimalni polinom, lastne vrednosti, determinanto in sled matrike).
  • Če je   matrika sosednosti usmerjenega ali neusmerjenega grafa  , potem imajo posamezni elementi matrike   (n-kratni produkt matrik   posebni pomen. Element v vrstici   in stolpcu   lahko pripišemo število prehodov z dolžino <math< n \,</math> od vozlišča   do vozlišča  .
  • Glavna diagonala vsake matrike sosednosti, ki pripada grafu brez zank, ima same ničle.

Posebne oblike matrik sosednostiUredi

Posebna oblika matrike sosednosti je Seidelova matrika sosednosti, ki jo označujejo tudi kot (0, -1, 1) matrika sosednosti. Ta matrika ima ničle na glavni diagonali, če element predstavlja povezavo, ima vrednost -1 in +1, če ne predstavlja povezave. Ta vrsta matrik se uporablja za raziskave strogo regularnih grafov in dvografov (bigraf).

Druga posebna oblika matrike sosednosti je matrika razdalj. V tej matriki ne povemo samo katera vozlišča so povezana, ampak tudi razdalje med njimi. Običajno je enota povezav 1. Posebna oblika matrika je še tista, ki za enoto nima samo 1, ampak imajo različne povezave tudi različne enote za merjenje dolžin med vozlišči.

Glej tudiUredi

Zunanje povezaveUredi

  • Weisstein, Eric Wolfgang. "Adjacency Matrix". MathWorld (angleščina).
  • Matrika sosednosti na PlanethMath (angleško)
  • Lekcije iz teorija grafov (angleško)
  • Matrika sosednosti in lastne vrednosti (angleško)
  • Matrika sosednosti na ProofWiki (angleško)