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

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

graf	matrika sosednosti
	$\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 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 $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

• 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 $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

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 MathWorld (v angleščini)
• Matrika sosednosti na PlanethMath (v angleščini)
• Lekcije iz teorija grafov (v angleščini)
• Matrika sosednosti in lastne vrednosti (v angleščini)
• Matrika sosednosti na ProofWiki (v angleščini)