EN|RU

Том 18, номер 2, 2011 г., Стр. 64-74

УДК 519.6
Панюкова Т. А.
Оптимальные эйлеровы покрытия с упорядоченным охватыванием для плоских графов

Аннотация:
Одним из критериев оптимальности последовательности цепей с упорядоченным охватыванием является суммарная длина участков маршрута между концом текущей и началом следующей цепей. Известен алгоритм построения покрытия, не учитывающий этот критерий. В статье предлагается алгоритм нахождения эйлерова покрытия с упорядоченным охватыванием, дающим минимальное значение указанного критерия.
Ил. 1, библиогр. 12.

Ключевые слова: плоский граф, цепь, покрытие, маршрут, упорядоченное охватывание.

Панюкова Татьяна Анатольевна 1
1. Южно-Уральский гос. университет,
пр. Ленина, 76, 454080 Челябинск, Россия
е-mail: kwark@mail.ru

Статья поступила 24 августа 2010 г.
Исправленный вариант — 13 ноября 2010 г.

 © Институт математики им. С. Л. Соболева, 2015