Matrika sosednosti

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Matrika sosednosti grafa G z urejenimi vozlišči \{1, 2, \ldots, n\} je kvadratna matrika A(G) = [aij], kjer je

a_{ij} = \begin{cases} 1, & i \sim j \\ 0, & \textrm{sicer}. \end{cases}

Zgled

1.) Neusmerjen graf:

Matrika sosednosti:

- Za neusmerjen graf je matrika sosednosti simetrična.

12345
1 0 1 0 0 1
2 1 0 1 0 1
3 0 1 0 1 0
4 0 0 1 0 1
5 1 1 0 1 0


2.) Usmerjen graf:
- Če sta u in v sosednji vozlišči in je povezava usmerjena od u k v, potem v matriko sosednosti dodamo številko 1, sicer dodamo 0.

Matrika sosednosti:

123456
1 0 1 0 1 0 0
20 0 0 0 1 0
3 0 0 0 0 1 1
4 0 1 0 0 0 0
5 0 0 0 1 0 0
6 0 0 0 0 0 1

Glej tudi

Osebna orodja