Graf
Iz MaFiRaWiki
| Različica od 15:48, 24 december 2005 TomazPisanski (Pogovor | prispevki) Morfizmi grafov ali grafne preslikave ← Prejšnja različica |
Različica od 09:08, 25 december 2005 AndrejBauer (Pogovor | prispevki) Formalna definicija Naslednja različica → |
||
| Vrstica 1: | Vrstica 1: | ||
| '''Graf''' je struktura v [[diskretna matematika|diskretni matematiki]], s katero lahko ponazorimo omrežje (cest, železnic, www, sistem kanalov, molekul, ...). Graf je sestavljen iz [[vozlišče|vozlišč]] ali točk (kraji, postaje, računalniki, atomi, ...) in povezav (ceste, žice, kanali, vezi ...), ki lahko nosijo različne lastnosti. | '''Graf''' je struktura v [[diskretna matematika|diskretni matematiki]], s katero lahko ponazorimo omrežje (cest, železnic, www, sistem kanalov, molekul, ...). Graf je sestavljen iz [[vozlišče|vozlišč]] ali točk (kraji, postaje, računalniki, atomi, ...) in povezav (ceste, žice, kanali, vezi ...), ki lahko nosijo različne lastnosti. | ||
| - | ==Formalna definicija== | + | ==Definicija== |
| '''Graf''' G = (V,S,i,r) je matematična struktura, pri kateri je | '''Graf''' G = (V,S,i,r) je matematična struktura, pri kateri je | ||
| * V razred vozlišč, | * V razred vozlišč, | ||
Različica od 09:08, 25 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 |
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. Morfizem f, ki je bijekcija tako na množici vozlišč kakor na množici povezav in je njegov inverz f-1 tudi morfizem, je izomorfizem grafov. Grafa, med katerima obstaja izomorfizem pa sta izomorfna. V praksi preverimo, da sta grafa izomorfna tako, da poiščemo preoznačevanje vozlišč in ustreznih povezav.
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)
...
