Корисник:Vladinemir/песак

У теорији графова, постоји више типова објеката са називом цикл.

Дефиниције[уреди | уреди извор]

Затворену шетњу чини низ чворова који почиње и завршава се у истом чвору и у коме су свака два суседна чвора повезана. Код усмереног графа, свака грана мора бити оријентисана по позицијама чворова у низу. Избор почетног чвора није битан.

Прост цикл се дефинише као затворена шетња без понављања грана и чворова, осим првог, тј. последњег чвора, или као скуп грана у таквој шетњи. 'Ќружни пут је затворена шетња са дозвољеним понављањем чворова али не и грана, али то може бити и прост цикл, па је потребра експлицитна дефиниција.

Цикл без тетива[уреди | уреди извор]

Цикл без тетива представља цикл, код којег ниједан чвор није повезан са неким другим чвором осим гранама које припадају циклу. На претходној слици цикл H-D-G-H је без тетива, док graf F-E-C-B-D садржи тетиву D-C и тетиву D-E, па није цикл без тетива.

Обим графа је дужина најмањег цикла у графу, који је обавезно без тетива.

Уочавање цикла[уреди | уреди извор]

Постојање цикла у усмереном или неусмереном графу се може одредити претрагом у дубину (DFS) која налази грану која води до претка тренутног чвора (садржи повратну грану).^[1] У неусмереном графу, налажење већ посећене гране ће показати повратну грану. Све повратне гране које (DFS) прескочи су део цикла. ^[2] У случају неусмерених графова, довољна је временска сложеност O(n) да би се пронашао цикл у графу са n чворова.

Многи алгоритми за тополошко сортирање ће пронаћи цикл, јер су они препрека за постојање тополошког реда.

Код усмерених графова, Роча-Тате алгоритам^[3] је дистрибуиран алгоритам за детектовање графа. Дистрибуирани алгоритми за уочавање графа су корисни за процесуирање великих графова јер користе систем за процесуирање графова на суперрачунарима.

Покривање графа циклима[уреди | уреди извор]

У свом раду ,,Седам мостова Кенигсберга" , који се сматра роћењем теорије графа, Леонард Ојлер је доказао да би коначан граф имао затворену шетњу код које се свака грана посећује тачно једном, морао да буде повезан и да би сваки чвор морао да има паран степен. Ојлеров цикл је цикл који сваку грану графа садржи тачно једном, а Ојлеров граф је повезан граф чији чворови имају паран степен.

Проблем проналажења простог цикла који сваки чвор садржи тачно једном је теже него налажење цикла који садржи све гране. Такав цикл је познат као Хамилтонов пут, а одређивање да ли постоји је НП комплетан проблем.^[4]

Хамилтонов пут (црно) над графом (плаво).

Класе графа дефинисане циклима[уреди | уреди извор]

Постоји неколико класа графова које се могу дефинисати циклима. Tо су:

Бипартидни граф - граф без непарног цикла.
Кактус граф - граф у коме је свака нетривијална повезана компонента цикл.
Циклични граф - граф који се састоји од једног цикла.
Граф са тетивом - граф без цикла већих од 3.
Усмерени ациклични граф - усмерени граф без цикла
Перфектни граф - граф без индукованог цикла или нјегових непарних комплемената већих од 3.
Псеудошума - граф код кога свака повезана компонента има највише један цикл.
Чврсто повезани граф - усмерени граф код ког свака грана припада неком циклу.
Граф без троугла - граф без цикла са 3 чвора.

Види још[уреди | уреди извор]

Теорија графова

Референце[уреди | уреди извор]

^ Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (5th изд.). Hoboken: John Wiley & sons. стр. 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), Ур.: R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, New York: Plenum, стр. 85—103 .

[1] Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (5th изд.). Hoboken: John Wiley & sons. стр. 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), Ур.: R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, New York: Plenum, стр. 85—103 .

[1]

[2]

[3]

[4]