Put (teorija grafova): razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja |
Nema sažetka uređivanja |
||
Redak 3:
[[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>
Put je oblik otvorene [[šetnja (teorija grafova)|šetnje]] u kojoj se vrhovi ne ponavljaju pa prema tome nema ni bridova. Za graf kažemo da je [[povezan graf|povezan]] ako postoji put između bilo koja dva vrha u grafu. Graf se naziva [[stablo (teorija grafova)|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]].<ref name="E-math"/>
U [[potraga za najkraćim putem|potrazi za najkraćim putem]] traži se najkraći put (npr. u težinskom grafu) između nekih dvaju vrhova.<ref name="E-math"/> Druga vrsta puta je [[inducirani put]].
| |||