Šetnja (teorija grafova)

Izvor: Hrvatska internetska enciklopedija
Inačica 438411 od 22. ožujka 2022. u 09:06 koju je unio WikiSysop (razgovor | doprinosi) (bnz)
(razl) ←Starija inačica | vidi trenutačnu inačicu (razl) | Novija inačica→ (razl)
Skoči na:orijentacija, traži

Šetnja, pojam iz teorije grafova. Njome se naziva alternirajući niz vrhova i bridova.[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]

Niz u šetnji počinje i završava vrhom. Svaki vrh iz šetnje incidentan je prethodećem mu bridu i bridu koji mu slijedi u tom nizu. Vrh prethodeći bridu i vrh koji slijedi taj brid krajnji su vrhovi tog brida. Šetnja od vrha [math]\displaystyle{ v_0 }[/math] do vrha [math]\displaystyle{ v_i }[/math] duljine je i u grafu G i čini ju niz o i bridova [math]\displaystyle{ v_{0}v_{1}, v_{1}v_{2}, \ldots, v_{i-1}v_{i} }[/math] . [1]

Obično se šetnju označava s [math]\displaystyle{ v_{0}v_{1}v_{1}v_{2}\ldots v_{i-1}v_{i} }[/math]. [1]

Kad su prvi i zadnji vrh jednaki, šetnja je zatvorena.[1] Ako su prvi i zadnji vrh različiti, šetnja je otvorena. Ako u ovoj vrsti šetnje nema ponavljanja vrhova pa prema tome ni bridova, zovemo je put. [1]

Izvori

  1. 1,0 1,1 1,2 1,3 1,4 1,5 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.)

walk