Ciklus (teorija grafova)

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

Ciklus, pojam iz teorije grafova. To je zatvorena staza u kojoj su svi unutarnji vrhovi (tj. svi vrhovi osim krajeva) međusobno različiti. Ako je graf povezan i bez ciklusa, onda je taj graf stablo.[1] Staza je pozitivne duljine. Ciklus [math]\displaystyle{ C_k }[/math], duljine [math]\displaystyle{ k }[/math], naziva se [math]\displaystyle{ k }[/math]-ciklus. Ako je [math]\displaystyle{ k }[/math] paran onda je i [math]\displaystyle{ k }[/math]-ciklus paran, odnosno neparan ako je [math]\displaystyle{ k }[/math] neparan.[2] U nekom grafu, ciklus predstavlja put u kojemu se prvi i posljednji vrh podudaraju. Duljinu najkraćeg ciklusa u grafu nazivamo struk grafa. [3]

Izvori

  1. Teorija grafova i logistika, Hrvatski matematički elektronički časopis
  2. Sveučilište J.J. Strossmayera u OsijekuOdjel za matematiku Marina Križić: Planarni grafovi, Osijek, 2013., str. 8
  3. math.e Snježana Majstorović i Luka Boras: Petersenov graf, br. 27. (pristupljeno 25. svibnja 2020.)