О числе OE-цепей для заданной системы переходов
Бесплатный доступ
Ранее установлено существование ОЕ-цепи в плоском эйлеровом графе и предложен алгоритм построения такой цепи. В статье исследуется вопрос о числе ОЕ-цепей с системой переходов, индуцируемой отдельной ОЕ-цепью и установлено, что верхняя оценка этого числа не превышает удвоенной суммы количества вершин, смежных внешней грани, и суммы степеней разделяющих вершин. Построенная оценка достижима, если система переходов является системой переходов A-цепи. Исследован вопрос существования ОЕ-цепей, удовлетворяющих произвольной системе переходов.
Плоский граф, эйлеров цикл, система переходов, а-цепь, упорядоченное охватывание, а-trail
Короткий адрес: https://sciup.org/147158994
IDR: 147158994 | DOI: 10.14529/mmph160101
Список литературы О числе OE-цепей для заданной системы переходов
- Панюкова, Т.А. Оптимальные эйлеровы покрытия с упорядоченным охватыванием для плоских графов/Т.А. Панюкова//Дискретный анализ и исследование операций. -2011. -Т. 18, № 2. -С. 64-74.
- Makarovskikh, T.A. The Algorithm for Constructing of Cutter Optimal Path/T.A. Makarovskikh//Journal of Computational and Engineering Mathematics. -2014. -Vol. 1, № 2. -P. 52-61.
- Фроловский, В.Д. Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ/В.Д. Фроловский//Информационные технологии в проектировании и производстве. -2005. -Вып. 4. -С. 63-66.
- Panioukova, T.A. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing/T.A. Panioukova, A.V. Panyukov//Известия Челябинского научного центра УрО РАН. -2000. -№ 4(9). -P. 18-22.
- Fleischner, H. Eulerian Graphs and Related Topics, Part 1, Vol. 1/H. Fleischner//Ann. Discrete Mathematics. -1990. -Vol. 45. -450 c.
- Белый, С.Б. О самонепересекающихся и непересекающихся цепях/С.Б. Белый//Математические заметки. -1983. -№ 34. -Вып. 4. -С. 625-628.
- Панюкова, Т.А. Обходы с упорядоченным охватыванием в плоских графах/Т.А. Панюкова//Дискретный анализ и исследование операций. Сер. 2. -2006. -Т. 13, № 2. -C. 31-43.
- Панюкова, Т.А. Построение эйлеровых циклов с упорядоченным охватыванием как математическая модель решения задачи раскроя/Т.А. Панюкова//Современные информационные технологии и ИТ-образование: cборник избранных трудов VIII Международной научно-практической конференции. Под ред. проф. В.А. Сухомлина. М.: ИНТУИТ.РУ, 2013. -С. 706-713.
Статья научная
