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  n \, vozlišč, je matrika z razsežnostjo  n \times n \,, ki ima elemente zunaj diagonale enake  a_{ij} \,, kar pomeni, da so to povezave med med vozliščem  i \, in  j \,. Elementi na diagonali  a_{ii} \, so v odvisnosti od dogovora, enkratno ali dvakratno število povezav iz vozlišča  I \, 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 \begin{bmatrix}
1 & 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}

Matrika sosednosti za dvodelne grafe[uredi | uredi kodo]

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

A = \begin{bmatrix} O & B \\ B^T & O \end{bmatrix},

kjer je

  •  B \, matrika z razsežnostjo  r \times s \,
  •  O \, ničelna matrika
  •  B \, enolično predstavlja dvodelni graf, ki ga predstavlja dvososednostna matrika.

Značilnosti[uredi | uredi kodo]

  • Predpostavimo, da imamo dva usmerjena ali dva neusmerjena grafa  G_1 \, in  G_2 \,, ki imata matriki sosednosti  A_1 \, in  A_2 \,. Potem sta  G_1 \, in  G_2 \, izomorfna, če in samo, če obstoja permutacijska matrika  P \, tako, da velja
P A_1 P^{-1} = A_2 \,.
Pri tem sta  A_1 \, in  A_2 \, podobni matriki (imata isti karakteristični polinom, minimalni polinom, lastne vrednosti, determinanto in sled matrike).
  • Če je  A \, matrika sosednosti usmerjenega ali neusmerjenega grafa  G \,, potem imajo posamezni elementi matrike  A^n \, (n-kratni produkt matrik  A \, posebni pomen. Element v vrstici  i \, in stolpcu  j \, lahko pripišemo število prehodov z dolžino <math< n \,</math> od vozlišča  i \, do vozlišča  j \,.
  • 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]