Циклус (теорија графова)
У теорији графова, постоји више типова објеката са називом циклус.
Дефиниције уреди
Затворену шетњу чини низ чворова који почиње и завршава се у истом чвору и у коме су свака два суседна чвора повезана. Код усмереног графа, свака грана мора бити оријентисана по позицијама чворова у низу. Избор почетног чвора није битан.
Прост циклус се дефинише као затворена шетња без понављања грана и чворова, осим првог, тј. последњег чвора, или као скуп грана у таквој шетњи. Ќружни пут је затворена шетња са дозвољеним понављањем чворова али не и грана, али то може бити и прост циклус, па је потребра експлицитна дефиниција.
Циклус без тетива уреди
Циклус без тетива представља циклус, код којег ниједан чвор није повезан са неким другим чвором осим гранама које припадају циклу. На претходној слици циклус H-D-G-H је без тетива, док graf F-E-C-B-D садржи тетиву D-C и тетиву D-E, па није циклус без тетива.
Обим графа је дужина најмањег циклуса у графу, који је обавезно без тетива.
Уочавање циклуса уреди
Постојање циклуса у усмереном или неусмереном графу се може одредити претрагом у дубину (DFS) која налази грану која води до претка тренутног чвора (садржи повратну грану).[1] У неусмереном графу, налажење већ посећене гране ће показати повратну грану.
Све повратне гране које (DFS) прескочи су део циклуса. [2] У случају неусмерених графова, довољна је временска сложеност O(n) да би се пронашао циклус у графу са n чворова.
Многи алгоритми за тополошко сортирање ће пронаћи циклус, јер су они препрека за постојање тополошког реда.
Код усмерених графова, Роча-Тате алгоритам[3] је дистрибуиран алгоритам за детектовање графа. Дистрибуирани алгоритми за уочавање графа су корисни за процесуирање великих графова јер користе систем за процесуирање графова на суперрачунарима.
Покривање графа циклусима уреди
У свом раду „Седам мостова Кенигсберга" , који се сматра роћењем теорије графа, Леонард Ојлер је доказао да би коначан граф имао затворену шетњу код које се свака грана посећује тачно једном, морао да буде повезан и да би сваки чвор морао да има паран степен. Ојлеров циклус је циклус који сваку грану графа садржи тачно једном, а Ојлеров граф је повезан граф чији чворови имају паран степен.
Проблем проналажења простог циклуса који сваки чвор садржи тачно једном је теже него налажење циклуса који садржи све гране. Такав циклус је познат као Хамилтонов пут, а одређивање да ли постоји је НП комплетан проблем.[4]
Класе графа дефинисане циклусима уреди
Постоји неколико класа графова које се могу дефинисати циклусима. То су:
- Бипартидни граф - граф без непарног циклуса.
- Кактус граф - граф у коме је свака нетривијална повезана компонента циклус.
- Циклични граф - граф који се састоји од једног циклуса.
- Граф са тетивом - граф без циклуса већих од 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 978-0-201-06672-2
- ^ 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
Литература уреди
- Tucker, Alan (2006). „Chapter 2: Covering Circuits and Graph Colorings”. Applied Combinatorics (5th изд.). Hoboken: John Wiley & sons. стр. 49. ISBN 978-0-471-73507-6.