Вестник Южно-Уральского государственного университета. Серия «Вычислительная математика и информатика»
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. ЮУрГУ. Сер. Выч. матем. информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2019, том 8, выпуск 1, страницы 36–53 (Mi vyurv205)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Программное обеспечение для построения A-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе

Т. А. Макаровских

Южно-Уральский государственный университет (454080 Челябинск, пр. им. В.И. Ленина, д. 76)

Аннотация: В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.

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

DOI: https://doi.org/10.14529/cmse190103

Полный текст: PDF файл (953 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 512.5, 519.1(075.8)
Поступила в редакцию: 24.07.2018

Образец цитирования: Т. А. Макаровских, “Программное обеспечение для построения A-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе”, Вестн. ЮУрГУ. Сер. Выч. матем. информ., 8:1 (2019), 36–53

Цитирование в формате AMSBIB
\RBibitem{Mak19}
\by Т.~А.~Макаровских
\paper Программное обеспечение для построения \textit{A}-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе
\jour Вестн. ЮУрГУ. Сер. Выч. матем. информ.
\yr 2019
\vol 8
\issue 1
\pages 36--53
\mathnet{http://mi.mathnet.ru/vyurv205}
\crossref{https://doi.org/10.14529/cmse190103}
\elib{https://elibrary.ru/item.asp?id=37074207}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vyurv205
  • http://mi.mathnet.ru/rus/vyurv/v8/i1/p36

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Т. А. Макаровских, А. В. Панюков, “Программное обеспечение для задачи построения траектории движения режущего инструмента для CAD/CAM систем технологической подготовки процессов раскроя”, Автомат. и телемех., 2021, № 3, 123–137  mathnet  crossref; T. A. Makarovskikh, A. V. Panyukov, “Software for the problem of constructing cutting tool paths in CAD/CAM systems for technological preparation of cutting processes”, Autom. Remote Control, 82:3 (2021), 468–480  crossref  isi  elib
  • Вестник Южно-Уральского государственного университета. Серия «Вычислительная математика и информатика»
    Просмотров:
    Эта страница:67
    Полный текст:24
    Литература:6
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022