Matrika sosednosti

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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 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.

Zgled[uredi | uredi kodo]

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

graf matrika sosednosti
6n-graph2.svg

Matrika sosednosti za dvodelne grafe[uredi | uredi kodo]

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čilnosti[uredi | uredi kodo]

  • 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 sosednosti[uredi | uredi kodo]

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 tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]