Digraf

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Digraf ali usmerjeni graf D je matematična struktura D = (V,A,f,t). Pri tem je V razred vozlišč, A razred lokov ali usmerjenih povezav, f,t: A \to V pa sta preslikavi: f določa začetek, t pa konec povezave.

Zgled

V = {v1,v2,v3,v4,v5,v6}
A = {a1,a2,a3,a4,a5,a6,a7}
f(a1) = v1, t(a1) = v2
f(a2) = v2, t(a2) = v3
f(a3) = v3, t(a3) = v4
f(a4) = v4, t(a4) = v5
f(a5) = v5, t(a5) = v6
f(a6) = v6, t(a6) = v1
f(a7) = v1, t(a7) = v4
f(a8) = v1, t(a8) = v2
f(a9) = v4, t(a9) = v4
f(a10) = v4, t(a10) = v3

Konstrukcije digrafov

  • Vsaka kategorija določa digraf: vozlišča so objekti, morfizmi so loki.
  • Vsaka dvojiška relacija R nad množico X določa digraf: vozlišča so elementi množice X, med objektoma a in b pa je lok, če je (a,b) \in R.

Glej tudi

Osebna orodja