Алгоритми пошуку циклу Ейлера і гамільтонового циклу в графах
Abstract
Теорія графів - це розділ математики, що вивчає графи, які є математичними структурами, що моделюють парні відношення між об'єктами. Графи використовуються в багатьох додатках, таких як мережевий аналіз, транспортне планування та аналіз соціальних мереж. Однією з найбільш фундаментальних проблем теорії графів є проблема пошуку циклів у графах. Два типи циклів, які часто вивчаються, - це цикл Ейлера та гамільтонів цикл. Цикл Ейлера - це цикл, який проходить через кожне ребро графа рівно один раз, тоді як гамільтонів цикл - це цикл, який проходить через кожну вершину графа рівно один раз. У цій тезі ми обговоримо алгоритми знаходження циклу Ейлера та гамільтонового циклу в графах.
References
Седжвік, Р., та Вейн, К. (2011). Алгоритми (4-е вид.). Addison-Wesley Professional.
Кормен, Т. Х., Лейзерсон, К. Е., Рівест, Р. Л., і Штейн, К. (2009). Вступ до алгоритмів (3-тє вид.). MIT Press.
Еппштейн, Д. (2011). Знаходження Ейлерових турів та шляхів у орієнтованих графах. Журнал графових алгоритмів та застосувань, 15(1), 21-41.
Джонатан Л. Гросс і Джей Єллен (2013). Теорія графів та її застосування
