Ciklus (teorija grafova)

U teoriji grafova, postoji više tipova objekata sa nazivom ciklus.

Graf sa obojenim ivicama koji ilustruje put H-A-B (zeleno), zatvoren put ili šetnju sa ponavljanjem čvorova B-D-E-F-D-C-B (plavo) i cikl bez ponavljanja grana i čvorova H-D-G-H (crveno)

Definicije uredi

Zatvorenu šetnju čini niz čvorova koji počinje i završava se u istom čvoru i u kome su svaka dva susedna čvora povezana. Kod usmerenog grafa, svaka grana mora biti orijentisana po pozicijama čvorova u nizu. Izbor početnog čvora nije bitan.

Prost ciklus se definiše kao zatvorena šetnja bez ponavljanja grana i čvorova, osim prvog, tj. poslednjeg čvora, ili kao skup grana u takvoj šetnji. Ќružni put je zatvorena šetnja sa dozvoljenim ponavljanjem čvorova ali ne i grana, ali to može biti i prost ciklus, pa je potrebra eksplicitna definicija.

Ciklus bez tetiva uredi

Ciklus bez tetiva predstavlja ciklus, kod kojeg nijedan čvor nije povezan sa nekim drugim čvorom osim granama koje pripadaju ciklu. Na prethodnoj slici ciklus H-D-G-H je bez tetiva, dok graf F-E-C-B-D sadrži tetivu D-C i tetivu D-E, pa nije ciklus bez tetiva.

Obim grafa je dužina najmanjeg ciklusa u grafu, koji je obavezno bez tetiva.

Uočavanje ciklusa uredi

Postojanje ciklusa u usmerenom ili neusmerenom grafu se može odrediti pretragom u dubinu (DFS) koja nalazi granu koja vodi do pretka trenutnog čvora (sadrži povratnu granu).[1] U neusmerenom grafu, nalaženje već posećene grane će pokazati povratnu granu.

Sve povratne grane koje (DFS) preskoči su deo ciklusa. [2] U slučaju neusmerenih grafova, dovoljna je vremenska složenost O(n) da bi se pronašao ciklus u grafu sa n čvorova.

Mnogi algoritmi za topološko sortiranje će pronaći ciklus, jer su oni prepreka za postojanje topološkog reda.

Kod usmerenih grafova, Roča-Tate algoritam[3] je distribuiran algoritam za detektovanje grafa. Distribuirani algoritmi za uočavanje grafa su korisni za procesuiranje velikih grafova jer koriste sistem za procesuiranje grafova na superračunarima.

Pokrivanje grafa ciklusima uredi

U svom radu „Sedam mostova Kenigsberga" , koji se smatra roćenjem teorije grafa, Leonard Ojler je dokazao da bi konačan graf imao zatvorenu šetnju kod koje se svaka grana posećuje tačno jednom, morao da bude povezan i da bi svaki čvor morao da ima paran stepen. Ojlerov ciklus je ciklus koji svaku granu grafa sadrži tačno jednom, a Ojlerov graf je povezan graf čiji čvorovi imaju paran stepen.

Problem pronalaženja prostog ciklusa koji svaki čvor sadrži tačno jednom je teže nego nalaženje ciklusa koji sadrži sve grane. Takav ciklus je poznat kao Hamiltonov put, a određivanje da li postoji je NP kompletan problem.[4]

 
Hamiltonov put (crno) nad grafom (plavo).

Klase grafa definisane ciklusima uredi

Postoji nekoliko klasa grafova koje se mogu definisati ciklusima. To su:

  • Bipartidni graf - graf bez neparnog ciklusa.
  • Kaktus graf - graf u kome je svaka netrivijalna povezana komponenta ciklus.
  • Ciklični graf - graf koji se sastoji od jednog ciklusa.
  • Graf sa tetivom - graf bez ciklusa većih od 3.
  • Usmereni aciklični graf - usmereni graf bez ciklusa
  • Perfektni graf - graf bez indukovanog ciklusa ili njegovih neparnih komplemenata većih od 3.
  • Pseudošuma - graf kod koga svaka povezana komponenta ima najviše jedan ciklus.
  • Čvrsto povezani graf - usmereni graf kod kog svaka grana pripada nekom ciklusu.
  • Graf bez trougla - graf bez ciklusa sa 3 čvora.

Vidi još uredi

Reference uredi

  1. ^ Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (5th izd.). Hoboken: John Wiley & sons. str. 49. ISBN 978-0-471-73507-6. 
  2. ^ Sedgewick, Robert (1983), „Graph algorithms”, Algorithms, Addison–Wesley, ISBN 978-0-201-06672-2 
  3. ^ Rocha, Rodrigo Caetano; Thatte, Bhalchandra (2015), Distributed cycle detection in large-scale sparse graphs (PDF), Simpósio Brasileiro de Pesquisa Operacional (SBPO) 
  4. ^ Richard M. Karp (1972), „Reducibility Among Combinatorial Problems” (PDF), Ur.: R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, New York: Plenum, str. 85—103 

Literatura uredi

  • Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (5th izd.). Hoboken: John Wiley & sons. str. 49. ISBN 978-0-471-73507-6.