Ейлерів ланцюг: відмінності між версіями
| [неперевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Виправлено неточності. |
Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3 |
||
Рядок 33:
*Оберіть будь-яку стартову вершину ''v'' та рухайтеся [[Ланцюг (теорія графів)|ланцюгом]] ребер розпочинаючи з цієї вершини допоки не повернетесь у ''v''. Неможливо застрягнути в будь-якій вершині окрім ''v'', бо парний степінь кожної вершини гарантує, що коли ланцюг досягає іншої вершини ''w'', то мусить існувати невикористане ребро з ''w''. Ланцюг, сформований таким чином — замкнений, тобто цикл, але може не покривати всіх ребер початкового графа.
*Допоки існує вершина ''u'', яка не належить до поточного ланцюга, але має інцидентні ребра не в ланцюзі, розпочніть інший ланцюг з ''u'', слідуючи невикористаними ребрами допоки не повернетеся в ''u'' та приєднайте новий цикл до вже наявного.
Використання такої структури як [[двобічно зв'язаний список]] уможливлює виконання кожної операції за сталий час (знаходження невикористаних ребер для кожної вершини, знаходження нової стартової вершини й поєднання двох циклів зі спільною вершиною), таким чином весь алгоритм потребує лінійного часу, <math>O(|E|)</math>.<ref>{{citation|title=Eulerian Graphs and Related Topics: Part 1, Volume 2|volume=50|series=Annals of Discrete Mathematics|first=Herbert|last=Fleischner|publisher=Elsevier|year=1991|isbn=978-0-444-89110-5|contribution=X.1 Algorithms for Eulerian Trails|pages=[https://archive.org/details/euleriangraphsre0001flei/page/ X.1–13]|url=https://archive.org/details/euleriangraphsre0001flei/page/}}.</ref>
== Примітки ==
| |||