Put (teorija grafova): razlika između inačica
Bot: Automatski unos stranica |
m bnz |
||
| Redak 1: | Redak 1: | ||
Put''', pojam iz [[teorija grafova|teorije grafova]]. <ref name="E-math"/> | |||
[[Graf (teorija grafova)|Graf]] je u gruboj definiciji skup objekata: [[vrh (teorija grafova)|vrhova]], [[točka (teorija grafova)|točaka]] ili [[čvor (teorija grafova)|čvorova]] koje povezuju bridovi odnosno crte (linije). Brid spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.<ref name="E-math">[http://e.math.hr/math_e_article/br14/fosner_kramberger math.e, hrvatski matematički elektronički časopis] Maja Fošner i Tomaž Kramberger: ''Teorija grafova i logistika'' br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)</ref> | [[Graf (teorija grafova)|Graf]] je u gruboj definiciji skup objekata: [[vrh (teorija grafova)|vrhova]], [[točka (teorija grafova)|točaka]] ili [[čvor (teorija grafova)|čvorova]] koje povezuju bridovi odnosno crte (linije). Brid spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.<ref name="E-math">[http://e.math.hr/math_e_article/br14/fosner_kramberger math.e, hrvatski matematički elektronički časopis] Maja Fošner i Tomaž Kramberger: ''Teorija grafova i logistika'' br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)</ref> | ||
Posljednja izmjena od 24. ožujak 2022. u 08:49
Put, pojam iz teorije grafova. [1]
Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova koje povezuju bridovi odnosno crte (linije). Brid spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.[1]
Vrhovi u grafu su povezani ako postoji put u . Ako su na stazi svi vrhovi međusobno različiti, šetnju se naziva put.[2] Drugim riječima, put je oblik otvorene šetnje u kojoj se vrhovi ne ponavljaju pa prema tome nema ni bridova. Za graf kažemo da je povezan ako postoji put između bilo koja dva vrha u grafu. Graf se naziva stablom ako su svaka dva vrha u njemu povezana točno jednim putem. Put koji prolazi kroz svaku spojnicu (brid) samo jednom zove se Eulerova šetnja.[1]
U potrazi za najkraćim putem traži se najkraći put (npr. u težinskom grafu) između nekih dvaju vrhova.[1] Druga vrsta puta je inducirani put.
Izvori
- ↑ 1,0 1,1 1,2 1,3 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)
- ↑ Sveučilište J.J. Strossmayera u OsijekuOdjel za matematiku Marina Križić: Planarni grafovi, Osijek, 2013., str. 8 (pristupljeno 25. svibnja 2020.)