Graf

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 23:30, 18 december 2005
TomazPisanski (Pogovor | prispevki)
Zgled
← Prejšnja različica
Različica od 13:36, 24 december 2005
TomazPisanski (Pogovor | prispevki)
Formalna definicija - valenca
Naslednja različica →
Vrstica 7: Vrstica 7:
* i:S → V, [[preslikava]] '''začetek''', ki določi krajišče polpovezave, * i:S → V, [[preslikava]] '''začetek''', ki določi krajišče polpovezave,
* r:S → S, [[involucija]] '''obrat''' brez negibnih točk, ki polpovezavi določi njeno nasprotno polpovezavo. * r:S → S, [[involucija]] '''obrat''' brez negibnih točk, ki polpovezavi določi njeno nasprotno polpovezavo.
 +
 +Za vsako vozlišče v &isin; V je moč praslike |i<sup>-1</sup>(v)| '''valenca''' ali '''stopnja''' vozlišča v. Označujemo jo z val(v) (pogosto tudi z deg(v) ali d(v)).
V splošnem ima lahko graf [[zanka|zanke]] in [[vzporedna povezava|vzporedne povezave]]. Graf brez zank in vzporednih povezav je [[enostaven graf|enostaven]]. V splošnem ima lahko graf [[zanka|zanke]] in [[vzporedna povezava|vzporedne povezave]]. Graf brez zank in vzporednih povezav je [[enostaven graf|enostaven]].

Različica od 13:36, 24 december 2005

Graf je struktura v diskretni matematiki, s katero lahko ponazorimo omrežje (cest, železnic, www, sistem kanalov, molekul, ...). Graf je sestavljen iz vozlišč ali točk (kraji, postaje, računalniki, atomi, ...) in povezav (ceste, žice, kanali, vezi ...), ki lahko nosijo različne lastnosti.

Vsebina

Formalna definicija

Graf G = (V,S,i,r) je matematična struktura, pri kateri je

  • V razred vozlišč,
  • S razred polpovezav,
  • i:S → V, preslikava začetek, ki določi krajišče polpovezave,
  • r:S → S, involucija obrat brez negibnih točk, ki polpovezavi določi njeno nasprotno polpovezavo.

Za vsako vozlišče v ∈ V je moč praslike |i-1(v)| valenca ali stopnja vozlišča v. Označujemo jo z val(v) (pogosto tudi z deg(v) ali d(v)).

V splošnem ima lahko graf zanke in vzporedne povezave. Graf brez zank in vzporednih povezav je enostaven.

Morfizmi grafov ali grafne preslikave

Preslikava f: G → G', med grafoma G = (V,S,i,r) in G' = (V',S',i',r'), ki slika V v V' in S v S', tako da za vsako polpovezavo e ∈ S velja:

  • i'(f(e)) = f(i(e))
  • r'(f(e)) = f(r(e))

se imenuje morfizem grafov ali grafna preslikava.

Grafi z morfizmi določajo kategorijo.

Zgled

V = {v1,v2,v3,v4,v5,v6}
S = {(a1,v1),(a1,v2),(a2,v2),(a2,v3),(a3,v3),(a3,v4),(a4,v4),(a4,v4),(a5,v5),(a5,v6),
(a7,v1),(a7,v4),(a8,v1),(a8,v2),(a9,v4,1),(a9,v4,2),(a10,v3),(a10,v4)}
i(a1,v1) = v1, r(a1,v1) = (a1,v2)
...

Glej tudi

Osebna orodja