double arrow

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


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

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

Алгоритм.

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

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

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

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

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

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







Сейчас читают про: