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.

Zgled 

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

 Matrika sosednosti polnega grafa ima povsod enice, samo na diagonali ima ničle.
 Matrika sosednosti za prazen graf je ničelna matrika

Matrika sosednosti za dvodelne grafe 

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 

 Matrika sosednosti neusmerjenih grafov je simetrična in tako ima popolno skupino realnih lastnih vrednosti in bazo ortogonalnih lastnih vektorjev. Množica lastnih vrednosti se imenuje spekter grafa.

 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 

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 

 seznam vrst matrik
 matrika razdalj

Zunanje povezave 

 
 Matrika sosednosti  na PlanethMath 
 Lekcije iz teorija grafov  
 Matrika sosednosti in lastne vrednosti  
 Matrika sosednosti na ProofWiki 

Matrike
Teorija grafov
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 . Zgled V naslednjem zgledu neusmerjenega označenega grafa je dodana tudi njegova matrika sosednosti Matrika sosednosti polnega grafa ima povsod enice , samo na diagonali ima ničle . Matrika sosednosti za prazen graf je ničelna matrika Matrika sosednosti za dvodelne grafe 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 Matrika sosednosti neusmerjenih grafov je simetrična in tako ima popolno skupino realnih lastnih vrednosti in bazo ortogonalnih lastnih vektorjev . Množica lastnih vrednosti se imenuje spekter grafa . 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 Posebna oblika matrike sosednosti je Seidelova matrika sosednosti , ki jo označujejo tudi kotmatrika sosednosti . Ta matrika ima ničle na glavni diagonali , če element predstavlja povezavo , ima vrednostin +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 Posebna oblika matrika je še tista , ki za enoto nima samo ampak imajo različne povezave tudi različne enote za merjenje dolžin med vozlišči . Glej tudi seznam vrst matrik matrika razdalj Zunanje povezave Matrika sosednosti na PlanethMath Lekcije iz teorija grafov Matrika sosednosti in lastne vrednosti Matrika sosednosti na ProofWiki Matrike Teorija grafov