Graf

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 08:28, 11 december 2005
TomazPisanski (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
TomazPisanski (Pogovor | prispevki)

Vrstica 1: Vrstica 1:
-je struktura v [[diskretna matematika|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. +'''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 [[povezava|povezav]] (ceste, žice, kanali, vezi ...), ki lahko nosijo različne lastnosti. Matematična disciplina, ki proučuje lastnost grafov se imenuje [[teorija grafov]].
-Š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'').+V veljavi je več različnih abstraktnih definicij grafa, od katerih nekatere dopuščajo zanke (povezave od vozlišča k istemu vozlišču) druge pa ne, nekatere dopuščajo večkratne povezave (več kot eno povezavo med dvema vozliščema) druge ne ipd.
-==Formalna definicija==+ 
-'''Graf''' G = (V,S,i,r) je matematična struktura, pri kateri je +==Definicija==
-* V razred vozlišč,+'''Graf''' <math>G = (V,S,i,r)</math> je matematična struktura, pri kateri je
-* S razred polpovezav,+* <math>V</math> razred vozlišč,
-* i:S &rarr; V, preslikava '''začetek''', ki določi krajišče polpovezave,+* <math>S</math> razred polpovezav,
-* r:S &rarr; S, [[involucija]] '''obrat''' brez negibih točk, ki polpovezavi določi njeno nasprotno polpovezavo.+* <math>i:S \to V</math>, [[preslikava]] '''začetek''', ki določi krajišče polpovezave,
 +* <math>r:S \to S</math>, [[involucija]] '''obrat''' brez [[negibna točka|negibnih točk]], ki polpovezavi določi njeno nasprotno polpovezavo.
 + 
 +'''Povezava''' je (neurejeni) par nasprotnih polpovezav <math>\{u,v\}</math>. '''Krajišči''' take povezave sta vozlišči <math>i(u)</math> in <math>i(v)</math>. Če sta enaki, je povezava '''zanka'''.
 + 
 +Za vsako vozlišče v &isin; V je moč praslike |i<sup>-1</sup>(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 [[zanka|zanke]] in [[vzporedna povezava|vzporedne povezave]] (ali večkratne povezave). Graf brez zank in vzporednih povezav je [[enostaven graf|enostaven]]. Predstavimo ga lahko z [[irefleksivna relacija|irefleksivno]] [[simetrična relacija|simetrično]] relacijo na vozliščih.
 + 
 +==Morfizmi grafov ali grafne preslikave==
 +Preslikava f: G &rarr; 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 &isin; 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 [[kategorija|kategorijo]]. Morfizem f, ki je bijekcija tako na množici vozlišč kakor na množici povezav in je njegov inverz f<sup>-1</sup> 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==
 + 
 +<graphviz layout="neato">
 +graph G {
 +v2 [pos="0,0"]
 +v6 [pos="0,3"]
 +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)}
 +: i(a1,v1) = v1, r(a1,v1) = (a1,v2) ...
==Glej tudi== ==Glej tudi==
 +
* [[predgraf]] * [[predgraf]]
 +* [[digraf]]
 +* [[enostaven graf]]
 +* [[družina grafov]]
 +* [[Graphviz]]
 +* [[Graf (podatkovna struktura)]]
 +* [[matrika sosednosti]]
 +* [[omrežje]]
-[[Kategorija:Diskretna matematika]] +[[Kategorija:Teorija grafov]]
-[[Kategorija:Pojmovnik]]+

Trenutna 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. Matematična disciplina, ki proučuje lastnost grafov se imenuje teorija grafov.

V veljavi je več različnih abstraktnih definicij grafa, od katerih nekatere dopuščajo zanke (povezave od vozlišča k istemu vozlišču) druge pa ne, nekatere dopuščajo večkratne povezave (več kot eno povezavo med dvema vozliščema) druge ne ipd.

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 (ali večkratne povezave). Graf brez zank in vzporednih povezav je enostaven. Predstavimo 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