Graf
Iz MaFiRaWiki
Različica od 23:30, 18 december 2005; poglej trenutno različico
←Starejša različica | Novejša različica→
←Starejša različica | Novejša različica→
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.
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) ...