Graf

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 22:10, 25 december 2005
TomazPisanski (Pogovor | prispevki)
Glej tudi
← Prejšnja različica
Različica od 23:43, 8 januar 2006
TomazPisanski (Pogovor | prispevki)
Glej tudi
Naslednja različica →
Vrstica 51: Vrstica 51:
* [[družina grafov]] * [[družina grafov]]
* [[Graphviz]] * [[Graphviz]]
 +* [[Predstavitev grafa v računalniku]]
[[Kategorija:Diskretna matematika]] [[Kategorija:Diskretna matematika]]
[[Kategorija:Pojmovnik]] [[Kategorija:Pojmovnik]]

Različica od 23:43, 8 januar 2006

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 \to V, preslikava začetek, ki določi krajišče polpovezave,
  • r:S \to S, involucija obrat brez negibnih točk, ki polpovezavi določi njeno nasprotno polpovezavo.

Povezava je (neurejeni) par nasprotnih polpovezav {u,v}. Krajišči take povezave sta vozlišči i(u) in i(v). Če sta enaki, je povezava zanka.

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. Predtavimo ga lahko z irefleksivno simetrično relacijo na vozliščih.

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) ...

Glej tudi

Osebna orodja