Šetnja (teorija grafova)

Šetnja, pojam iz teorije grafova. Njome se naziva alternirajući niz vrhova i bridova.

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.

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 $v_0$ do vrha $v_i$ duljine je i u grafu G i čini ju niz o i bridova $v_0{v}_1,v_1{v}_2,\dots ,v_{i-1}{v}_i$ .

Obično se šetnju označava s $v_0{v}_1{v}_1{v}_2\dots v_{i-1}{v}_i$.

Kad su prvi i zadnji vrh jednaki, šetnja je zatvorena. 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.

Izvori

walk