Том 18, номер 2, 2011 г., Стр. 64-74
УДК 519.6
Панюкова Т. А.
Оптимальные эйлеровы покрытия с упорядоченным охватыванием для плоских графов
Аннотация:
Одним из критериев оптимальности последовательности цепей с упорядоченным охватыванием является суммарная длина участков маршрута между концом текущей и началом следующей цепей. Известен алгоритм построения покрытия, не учитывающий этот критерий. В статье предлагается алгоритм нахождения эйлерова покрытия с упорядоченным охватыванием, дающим минимальное значение указанного критерия.
Ил. 1, библиогр. 12.
Ключевые слова: плоский граф, цепь, покрытие, маршрут, упорядоченное охватывание.
Панюкова Татьяна Анатольевна 1
1. Южно-Уральский гос. университет,
пр. Ленина, 76, 454080 Челябинск, Россия
е-mail: kwark@mail.ru
Статья поступила 24 августа 2010 г.
Исправленный вариант — 13 ноября 2010 г.
Литература
[1] Панюкова Т. А. Построение эйлеровых циклов специального вида в планарном графе // Материалы VII междунар. семинара «Дискретная математика и ее приложения», Ч.II / Под ред. О. Б. Лупанова. — М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2001. — C. 149.
[2] Панюкова Т. А. Построение маршрутов с упорядоченным охватыванием в плоских графах // 36-я регион. молодеж. конференция «Проблемы теоретической и прикладной математики» (Екатеринбург, 30 января–4 февраля 2005 г.): Труды. — Екатеринбург: УрО РАН, 2005. — C. 61–66.
[3] Панюкова Т. А. Обходы с упорядоченным охватыванием в плоских графах // Дискрет. анализ и исслед. операций. — 2006. — Т. 13, № 2. — C. 31–43.
[4] Панюкова Т. А. Некоторые критерии оценки раскройных планов // IV всерос. конференция «Проблемы оптимизации и экономические приложения» (Омск, 29 июня–4 июля 2009 г.): Материалы. — Омск: Полиграфический центр КАН, 2009. — C. 238.
[5] Панюкова Т. А. Покрытия с упорядоченным охватыванием с минимальной длиной дополнительных построений // Всерос. конф. «Дискретная оптимизация и исследование операций»: Материалы конференции (Новосибирск, 27 июня–2 июля 2010 г.). — Новосибирск: Изд-во Ин-та математики СО РАН, 2010. — C. 150.
[6] Фляйшнер Г. Эйлеровы графы и смежные вопросы. — М.: Мир, 2002. — 335 с.
[7] Fleischner H. Eulerian graphs and related topics. Part 1, Vol. 2 // Ann. Discrete Math. — 1991. — N 50. — 336 c.
[8] Panioukova T. A., Panyukov A. V. Algorithms for construction of ordered enclosing traces in planar eulerian graphs // Int. Workshop Comput. Sci. Information Technologies’2003 (Ufa, September 16–18, 2003). Vol. 1.: Proc. — Ufa: Ufa State Technical Univ., 2003. — P. 134–138.
[9] Panyukov A. V., Panyukova T. A. The algorithm for tracing of flat Euler cycles with ordered enclosing // Proc. Chelyabinsk Sci. Center #4(9), 2000. — P. 18–22. http://www.sci.urc.ac.ru/news/2000_4/2000_4_1_4.pdf
[10] Panyukova T. Chain sequences with ordered enclosing // J. Comput. Syst. Sci. Int. — 2007. — Vol. 46, N 1. — P. 83–92.
[11] Panyukova T. Cover with ordered enclosing for flat graphs // Electron. Notes Discrete Math. — 2007. — N 28. — P. 17–24.
[12] Panyukova T. A., Panyukov A. V. Decreasing of length for routes with ordered enclosing // Междунар. науч. конференция «Дискретная математика, алгебра и их приложения» (Минск, 19–22 октября 2009 г.).: Тез. докл. — Минск: Ин-т математики НАН Беларуси, 2009. — С. 155–157.
|