Циклус (теорија графова) — разлика између измена
Садржај обрисан Садржај додат
Нова страница: {{МАТФKA2016}} File:Graph cycle.gif|thumb| Граф са обојеним ивицама који илуструје пут H-A-B (зелено), затворе… |
м Разне исправке; козметичке измене |
||
Ред 1:
{{МАТФKA2016}}
[[
У [[Теорија графова
== Дефиниције ==
'''Затворену шетњу''' чини низ чворова који почиње и завршава се у истом чвору и у коме су свака два суседна чвора повезана. Код усмереног графа, свака грана мора бити оријентисана по позицијама чворова у низу. Избор почетног чвора није битан.
Ред 10:
'''Прост цикл''' се дефинише као затворена шетња без понављања грана и чворова, осим првог, тј. последњег чвора, или као скуп грана у таквој шетњи. 'Ќружни пут''' је затворена шетња са дозвољеним понављањем чворова али не и грана, али то може бити и прост цикл, па је потребра експлицитна дефиниција.
== Цикл без тетива ==
'''Цикл без тетива''' представља цикл, код којег ниједан чвор није повезан са неким другим чвором осим гранама које припадају циклу. На претходној слици цикл H-D-G-H је без тетива, док graf F-E-C-B-D садржи тетиву D-C и тетиву D-E, па није цикл без тетива.
'''Обим''' графа је дужина најмањег цикла у графу, који је обавезно без тетива.
== Уочавање цикла ==
Постојање цикла у усмереном или неусмереном графу се може одредити [[
Све повратне гране које (DFS) прескочи су део цикла. <ref name="sedgewick">{{citation
|
| title=Algorithms | chapter=Graph algorithms
|
| publisher=Addison–Wesley |
}}</ref> У случају неусмерених графова, довољна је временска сложеност ''O''(''n'')
Многи алгоритми за [[
Код усмерених графова, Роча-Тате алгоритам<ref>{{citation|title=Distributed cycle detection in large-scale sparse graphs|first1=Rodrigo Caetano|last1=Rocha|first2=Bhalchandra|last2=Thatte|year=2015|url=http://rcorcs.github.io/papers/sbpo2015cycles.pdf|publisher=Simpósio Brasileiro de Pesquisa Operacional (SBPO)|format=PDF}}</ref> је дистрибуиран алгоритам за детектовање графа. Дистрибуирани алгоритми за уочавање графа су корисни за процесуирање великих графова јер користе систем за процесуирање графова на суперрачунарима.
== Покривање графа циклима ==
У свом раду ,,Седам мостова Кенигсберга" , који се сматра роћењем теорије графа, [[Леонард Ојлер]] је доказао да би коначан граф имао затворену шетњу код које се свака грана посећује тачно једном, морао да буде повезан и да би сваки чвор морао да има паран степен. '''Ојлеров цикл''' је цикл који сваку грану графа садржи тачно једном, а '''Ојлеров граф''' је повезан граф чији чворови имају паран степен.
Проблем проналажења простог цикла који сваки чвор садржи тачно једном је теже него налажење цикла који садржи све гране. Такав цикл је познат као [[Хамилтонов пут]], а одређивање да ли постоји је [[НП-комплетни проблеми
| author = [[Richard M. Karp]]
| chapter = Reducibility Among Combinatorial Problems
Ред 38:
| editor = R. E. Miller and J. W. Thatcher
| publisher = New York: Plenum
|
|
[[Датотека:Hamilton_path.gif|десно|оквир|Хамилтонов пут (црно) над графом (плаво).]]
== Класе графа дефинисане циклима ==
Постоји неколико класа графова које се могу дефинисати циклима.
* Бипартидни граф - граф без непарног цикла.
* Кактус граф - граф у коме је свака нетривијална повезана компонента цикл.
| |||