Алгоритм построения Эйлерова цикла

Обратимся к задаче об эйлеровом цикле, уже рассмотренной нами в предыдущем параграфе. Пусть — связный граф, степени всех вершин которого — четные числа. Теорема 1 §2 гарантирует существование эйлерова цикла.

Как фактически построить его? Оказывается, что достаточно выполнять следующие правила.

Алгоритм.

1°. Выбрать произвольно некоторую вершину .

2°. Выбрать произвольно некоторое ребро , инцидентное , и присвоить ему номер 1. (Назовем это ребро «пройденным».)

3°. Каждое пройденное ребро вычеркивать и присваивать ему номер, на единицу больший номера предыдущего вычеркнутого ребра.

4°. Находясь в вершине, не выбирать ребра, соединяющего с вершиной , если только есть возможность другого выбора.

5°. Находясь в вершине , не выбирать ребра, которое является «перешейком» (при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру).

6°. После того, как в графе будут занумерованы все ребра, цикл , образованный ребрами с номерами от 1 до , где число ребер в графе, есть эйлеров цикл.

Дата добавления: 2014-01-03