From Wikipedia, the free encyclopedia
У теорији графова, постоји више типова објеката са називом циклус.
Затворену шетњу чини низ чворова који почиње и завршава се у истом чвору и у коме су свака два суседна чвора повезана. Код усмереног графа, свака грана мора бити оријентисана по позицијама чворова у низу. Избор почетног чвора није битан.
Прост циклус се дефинише као затворена шетња без понављања грана и чворова, осим првог, тј. последњег чвора, или као скуп грана у таквој шетњи. Ќружни пут је затворена шетња са дозвољеним понављањем чворова али не и грана, али то може бити и прост циклус, па је потребра експлицитна дефиниција.
Циклус без тетива представља циклус, код којег ниједан чвор није повезан са неким другим чвором осим гранама које припадају циклу. На претходној слици циклус H-D-G-H је без тетива, док graf F-E-C-B-D садржи тетиву D-C и тетиву D-E, па није циклус без тетива.
Обим графа је дужина најмањег циклуса у графу, који је обавезно без тетива.
Постојање циклуса у усмереном или неусмереном графу се може одредити претрагом у дубину (DFS) која налази грану која води до претка тренутног чвора (садржи повратну грану).[1] У неусмереном графу, налажење већ посећене гране ће показати повратну грану.
Све повратне гране које (DFS) прескочи су део циклуса.[2] У случају неусмерених графова, довољна је временска сложеност O(n) да би се пронашао циклус у графу са n чворова.
Многи алгоритми за тополошко сортирање ће пронаћи циклус, јер су они препрека за постојање тополошког реда.
Код усмерених графова, Роча-Тате алгоритам[3] је дистрибуиран алгоритам за детектовање графа. Дистрибуирани алгоритми за уочавање графа су корисни за процесуирање великих графова јер користе систем за процесуирање графова на суперрачунарима.
У свом раду „Седам мостова Кенигсберга" , који се сматра роћењем теорије графа, Леонард Ојлер је доказао да би коначан граф имао затворену шетњу код које се свака грана посећује тачно једном, морао да буде повезан и да би сваки чвор морао да има паран степен. Ојлеров циклус је циклус који сваку грану графа садржи тачно једном, а Ојлеров граф је повезан граф чији чворови имају паран степен.
Проблем проналажења простог циклуса који сваки чвор садржи тачно једном је теже него налажење циклуса који садржи све гране. Такав циклус је познат као Хамилтонов пут, а одређивање да ли постоји је НП комплетан проблем.[4]
Постоји неколико класа графова које се могу дефинисати циклусима. То су:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.