Graf

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 23:57, 10 december 2005
TomazPisanski (Pogovor | prispevki)
Glej tudi
← Prejšnja različica
Različica od 08:28, 11 december 2005
TomazPisanski (Pogovor | prispevki)

Naslednja različica →
Vrstica 3: Vrstica 3:
Z grafi lahko ponazorimo in rešimo marsikateri problem iz življenja. 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''). +Š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'').
 +==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 negibih točk, ki polpovezavi določi njeno nasprotno polpovezavo.
 + 
==Glej tudi== ==Glej tudi==
-* [[Hamiltonov cikel]]+* [[predgraf]]
-* [[Povezan graf]] +
-* [[Podgraf]]+
-* [[Digraf]]+
-* [[Predgraf]]+
-* [[Vozlišče]]+
-* [[Povezava]]+
-* [[Lok]]+
 +[[Kategorija:Diskretna matematika]]
[[Kategorija:Pojmovnik]] [[Kategorija:Pojmovnik]]
-[[Kategorija:Diskretna matematika]] 

Različica od 08:28, 11 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).

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 negibih točk, ki polpovezavi določi njeno nasprotno polpovezavo.

Glej tudi

Osebna orodja