Graf

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 17:38, 12 december 2005
TomazPisanski (Pogovor | prispevki)
Glej tudi
← Prejšnja različica
Različica od 17:43, 12 december 2005
TomazPisanski (Pogovor | prispevki)
Glej tudi
Naslednja različica →
Vrstica 21: Vrstica 21:
Grafi z morfizmi določajo [[kategorija|kategorijo]]. Grafi z morfizmi določajo [[kategorija|kategorijo]].
 +
 +==Zgled==
 +
 +<graphviz>
 +graph G {
 +v1--v2[label= a1]
 +v2--v3[label= a2]
 +v3--v4[label= a3]
 +v4--v5[label= a4]
 +v5--v6[label= a5]
 +v6--v1[label= a6]
 +v1--v4[label= a7]
 +v1--v2[label= a8]
 +v4--v4[label= a9]
 +v4--v3[label= a10]
 +}
 +</graphviz>
 + 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)}
 + 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
==Glej tudi== ==Glej tudi==

Različica od 17:43, 12 december 2005

je struktura v diskretni matematiki, s katero lahko ponazorimo omrežje (cest, železnic, www, sistem kanalov, molekula, ...). 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.

Z grafi lahko ponazorimo in rešimo marsikateri problem iz življenja.

Še za matematične ljubitelje: Graf G = (V,E), kjer je V množica vozlišč (angleško vertex) in E množica povezav med njimi (angleško edge).

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

Glej tudi

Osebna orodja