Korisnik:Vladinemir/pesak

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

Definicije

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 cikl 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 cikl, pa je potrebra eksplicitna definicija.

Cikl bez tetiva

Cikl bez tetiva predstavlja cikl, kod kojeg nijedan čvor nije povezan sa nekim drugim čvorom osim granama koje pripadaju ciklu. Na prethodnoj slici cikl 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 cikl bez tetiva.

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

Uočavanje cikla

Postojanje cikla 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 cikla. ^[2] U slučaju neusmerenih grafova, dovoljna je vremenska složenost O(n) da bi se pronašao cikl u grafu sa n čvorova.

Mnogi algoritmi za topološko sortiranje će pronaći cikl, 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 ciklima

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 cikl je cikl koji svaku granu grafa sadrži tačno jednom, a Ojlerov graf je povezan graf čiji čvorovi imaju paran stepen.

Problem pronalaženja prostog cikla koji svaki čvor sadrži tačno jednom je teže nego nalaženje cikla koji sadrži sve grane. Takav cikl 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 ciklima

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

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

Vidi još

Teorija grafova

Reference

^ 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.
^ Sedgewick, Robert (1983), „Graph algorithms”, Algorithms, Addison–Wesley, ISBN 0-201-06672-6
^ Rocha, Rodrigo Caetano; Thatte, Bhalchandra (2015), Distributed cycle detection in large-scale sparse graphs (PDF), Simpósio Brasileiro de Pesquisa Operacional (SBPO)
^ 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 .

[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.

[sedgewick-2] Sedgewick, Robert (1983), „Graph algorithms”, Algorithms, Addison–Wesley, ISBN 0-201-06672-6

[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 .

[1]

[2]

[3]

[4]