=Paper=
{{Paper
|id=Vol-2064/paper12
|storemode=property
|title=
ОЕ-покрытие плоского графа цепями с разрешенными начальными вершинами
(The OE-cover for a plane graph by chains with allowed starting vertices)
|pdfUrl=https://ceur-ws.org/Vol-2064/paper12.pdf
|volume=Vol-2064
|authors=Tatiana Makarovskikh,Egor Savitsky
}}
==
ОЕ-покрытие плоского графа цепями с разрешенными начальными вершинами
(The OE-cover for a plane graph by chains with allowed starting vertices)
==
https://ceur-ws.org/Vol-2064/paper12.pdf
УДК 519.1
Савицкий Е.А., Макаровских Т.А.
Южно-Уральский государственный университет, г. Челябинск, Россия
OE-ПОКРЫТИЕ ПЛОСКОГО ГРАФА ЦЕПЯМИ С РАЗРЕШЕННЫМИ НАЧАЛЬНЫМИ
ВЕРШИНАМИ*
Аннотация
При использовании технологии лазерной резки листового материала требуется наличие
некоторого пространства для осуществления врезки. При использовании в качестве образа
раскройного плана плоского графа G, можно выделить множество граней Fin (G) F (G) , в
которые возможна врезка. Множество вершин Vin (G) V (G) , инцидентных грани Fin (G)
является множеством разрешенных начальных вершин покрывающих OE-цепей. Если путь в
графе G является OE-путем и его начальная вершина v1 Vin (G) , тогда этот путь
(названный PPOE-цепью) может использоваться при генерации команд раскройному
автомату лазерной резки. OE-покрытие графа G, состоящее из PPOE-цепей, названо PPOE-
покрытием. Построение PPOE-покрытия для графа G решает задачу определения пути
движения режущего инструмента с разрешенным множеством точек врезки. В статье
приводятся необходимые условия существования PPOE-покрытия.
Ключевые слова
Плоский граф; маршрут; точка врезки; реберно-непересекающееся покрытие; упорядоченное
охватывание.
Savitsky E.A., Makarovskikh T.A.
South Ural State University, Chelyabinsk, Russia
THE OE-COVER FOR A PLANE GRAPH BY CHAINS WITH ALLOWED STARTING VERTICES
Abstract
The technology of plasma cutting for sheet material claims presence of some space to place a pierce
point. Usage of a plane graph G as an image of cutting plan allows indicating a specified list of faces
Fin (G) F (G) allowing piercing. A set of vertices Vin (G) V (G) incident to Fin (G) is a set of allowed
starting vertices for OE-chains. If a path in graph G is the OE-path and its starting vertex v1 Vin (G)
then this path (called PPOE-chain) can be used for constructing a cutting-off program for plasma
cutting machine. OE-cover of graph G consisting of PPOE-chains is called PPOE-cover. Constructing of
PPOE-cover for graph G solves the stated routing problem for a cutter with allowed set of pierce points.
This paper is devoted to the necessary conditions of PPOE-cover existence.
Keywords
Plane graph; Path; Pierce point; edge-disjoint cover; ordered enclosing.
Введение
Лазерная резка является одной из основных технологий, используемых при обработке листового
материала, что делает актуальной задачу определения траектории движения режущего инструмента.
Задача определения траектории заключается в определении точной последовательности резов. Развитие
автоматизации производства привело к появлению технологического оборудования с числовым
программным управлением, используемого для резки листовых материалов. Новые технологии
позволяют осуществлять вырезание по произвольной траектории с достаточной для практики точностью.
* Труды II Международной научной конференции «Конвергентные когнитивно-
информационные технологии» (Convergent’2017), Москва, 24-26 ноября, 2017
Proceedings of the II International scientific conference "Convergent cognitive information
technologies" (Convergent’2017), Moscow, Russia, November 24-26, 2017
103
Преимуществом при использовании лазерной резки является минимальность таких показателей как
ширина реза и термические деформации. Целью задачи определения маршрута резки является поиск
такого пути режущего инструмента, при котором выполняются условия предшествования, а время,
затраченное на вырезание, минимально [1].
В терминах задачи лазерной резки под условием предшествования понимается требование к тому,
чтобы отрезанная от листа часть не требовала дополнительных разрезаний (т.е. все элементы
вложенного контура должны быть вырезаны прежде, чем внешний контур окажется полностью
вырезанным).
Общее время, требуемое на выполнение резки, можно представить как суммарное время для
осуществления всех вырезаний, времени на выполнение холостых переходов, времени на врезку и пр. Так
как основным условием предшествования при выполнении лазерной резки является требование к
отсутствию разрезаний для уже отрезанной части листа, то
- во-первых, все элементы внутренних контуров должны быть вырезаны прежде, чем будут полностью
отрезаны от листа внешние контуры;
- во-вторых, необходимо учитывать термальные эффекты, например, стоит избегать пересечения
имеющихся резов.
В [1] и [2] приводится классификация задач маршрутизации режущего инструмента и отмечается, что
технологии ECP (Endpoint Cutting Problem) и ICP (Intermittent Cutting Problem) за счет возможности
совмещения границ вырезаемых деталей позволяют сократить расход материала, длину резки, и длину
холостых проходов [2]. Проблемы уменьшения отходов материала и максимального совмещения
фрагментов контуров вырезаемых деталей решаются на этапе составления раскройного плана. В [1]
отмечено, что для решения задачи ECP известен алгоритм [3], который находит траекторию движения
режущего инструмента и минимизирует число точек врезки. Для решения этой задачи авторами статьи
[3] использован аппарат теории графов, предложенный в работе алгоритм строит дополнительные ребра
между вершинами нечетной степени графа, инцидентными одной грани. Тем не менее, в общем случае
при добавлении дополнительных ребер между парами вершин нечетной степени граф не будет плоским.
Более того, не все вершины нечетной степени могут выступать в качестве начальных вершин цепей.
В данной статье авторами рассматривается решение задачи оптимизации пути режущего инструмента
в случае, когда раскройный план является плоским неэйлеровым графом, а на траекторию движения
режущего инструмента наложены следующие ограничения: отрезанная от листа часть не требует
дополнительных разрезаний, а возможные точки врезки заданы.
Определения и обозначения
Для решения поставленной задачи раскройный план необходимо представить в виде плоского графа
[4]. Моделью раскройного листа будем считать плоскость S, моделью раскройного плана – плоский граф
G с внешней гранью f0 на плоскости S. Для плоского графа G далее через E(G) будем обозначать
множество его ребер, представляющих плоские жордановы кривые с попарно непересекающимися
внутренностями, гомеоморфные отрезкам. Через V (G) обозначим множество граничных точек этих
кривых.
Для любой части графа J G (части траектории движения режущего инструмента) обозначим через
Int J теоретико-множественное объединение его внутренних граней (объединение всех связных
компонент S ‚ J , не содержащих внешней грани). Тогда Int( J ) можно интерпретировать как
отрезанную от листа часть. Множества вершин, ребер и граней графа J будем обозначать через V ( J ) , E ( J )
и F ( J ) соответственно, а через |M | – число элементов множества M.
Начальную часть маршрута в графе G будем рассматривать как часть графа, содержащую все вершины
и ребра, принадлежащие этой части маршрута. Это позволяет формализовать требование к маршруту
режущего инструмента как условие отсутствия пересечения внутренних граней любой начальной части
маршрута в заданном плоском графе G с ребрами его оставшейся части [5]. Такие маршруты будем
называть маршрутами с упорядоченным охватыванием [6] (или для кратости OE-маршрутами, где OE – от
англ. “ordered enclosing”).
Определение 1 [5]. Цепь C v1e1v2e2 vk в плоском графе G имеет упорядоченное охватывание
(является OE-цепью), если для любой его начальной части Cl v1e1v2e2 el l (| E |) выполнено условие
Int Cl G .
Определение 2 [6]. Упорядоченная последовательность реберно-непересекающихся OE-цепей
C 0 v0 e10 v10 e20 ...ek00 vk00 , C1 v1e11v11e12 ...e1k1 v1k1 , ,
C n 1 v n 1e1n 1v1n 1e2n 1 ...eknn11 vknn11 ,
104
покрывающая граф G и такая, что
m :m n , m 1
l 0
Int(C l )
n 1
l m
C l ,
называется маршрутом с упорядоченным охватыванием (OE-маршрутом).
Построение OE-маршрута графа G решает поставленную задачу раскроя. Наибольший интерес
представляют маршруты с минимальным числом цепей, поскольку переход от одной цепи к другой
соответствует холостому проходу режущего инструмента.
Определение 3. ОЕ-маршрут, содержащий минимальную по мощности упорядоченную
последовательность реберно-непересекающихся цепей в плоском графе G будем называть эйлеровым
маршрутом с упорядоченным охватыванием (эйлеровым OE-маршрутом), а составляющие его OE-цепи –
эйлеровым OE-покрытием.
Топологическое представление плоского графа G (V , E ) на плоскости S с точностью до
гомеоморфизма определяется заданием для каждого ребра e E следующих функций [4]:
• vk (e) , k 1, 2 – вершины, инцидентные ребру e;
• f k (e) – грань, находящаяся справа при движении по ребру e от вершины vk (e) к вершине
v3k (e) , k 1, 2 ;
• lk (e) – ребро, инцидентное грани f3 k (e) и vk (e) , k 1, 2 ;
• rk (e) – ребро, инцидентное грани f k (e) и vk (e) , k 1, 2 .
Поскольку функции vk (e) , f k (e) , lk (e) , rk (e) , k 1, 2 , построенные на ребрах графа G (V , E ) , для
каждого ребра определяют инцидентные вершины, инцидентные грани и смежные ребра, то справедливо
следующее
Утверждение. Функции vk (e) , f k (e) , lk (e) , rk (e) , k 1, 2 , построенные на ребрах графа G (V , E ) ,
определяют плоский граф G (V , E ) с точностью до гомеоморфизма.
Данное утверждение справедливо, поскольку функции vk (e) , f k (e) , lk (e) , rk (e) , k 1, 2 , построенные
для ребер графа G , определяют инцидентные вершины для каждого ребра, инцидентные грани и
смежные ребра. Далее будем считать, что все рассматриваемые плоские графы представлены указанными
функциями. Пространственная сложность такого представления будет O(| E | log2 | V |) . Построение
данных функций не составляет проблем. Фактически, они определяются на этапе кодирования графа G .
Это минимальная информация, необходимая для представления любого плоского графа с точностью до
гомеоморфизма. Используя известные координаты прообразов вершин графа G (V , E ) и размещения
фрагментов раскройного плана, являющихся прообразами ребер графа G (V , E ) , любой маршрут в
графе G (V , E ) можно интерпретировать как траекторию режущего инструмента.
Приведем понятие ранга ребра, используемое в рассуждениях ниже.
Определение 4 [7]. Рангом ребра e E (G) будем называть значение функции rank(e) : E(G) N ,
определяемую рекурсивно: пусть E1 {e E : e f 0 } – множество ребер, ограничивающих внешнюю грань
1
f0 графа G (V , E ) , тогда e E rank(e) 1 ; пусть
Ek (G) – множество ребер ранга 1 графа
k 1
Gk V , E \ El ,
l 1
тогда e Ek rank(e) k .
Ранг ребра определяет его удаленность от внешней грани и показывает, какое минимальное число
граней необходимо пересечь, чтобы добраться от внешней грани f0 до этого ребра.
Мощность эйлерова OE-покрытия
Рассмотрим произвольный плоский связный граф. В этом случае справедлива следующая теорема об
оценке мощности эйлерова OE-покрытия.
Теорема 1 [8]. Пусть G – плоский связный граф, Vodd (G) – множество вершин нечетной степени графа
G, тогда для мощности N эйлерова OE-покрытия графа G имеет место неравенство
| V (G) |
k odd N | Vodd (G) | 2k.
2
Причем, как верхняя, так и нижняя оценки достижимы.
Доказательство. Из теоремы Листинга–Люка следует, что нижняя оценка не может быть меньше k.
Эта граница достигается для графов без мостов, имеющих хотя бы одну вершину нечетной степени,
105
инцидентную внешней грани (см. алгоритм OE-Cover). Так, в [9] предложен алгоритм построения
упорядоченной последовательности цепей, удовлетворяющей условию упорядоченного охватывания и
покрывающей граф без мостов не более чем k 1 цепями. Маршруты, которые реализуют построенное
покрытие, содержат дополнительные ребра между концом текущей цепи и началом последующей.
Достижимость верхней оценки иллюстрирует пример, приведенный на рисунке 1.
Действительно, любая из вершин нечетной степени v1* , v2* , , v2*k может быть только началом
покрывающей OE-цепи, так как маршрут, заканчивающийся в любой из этих вершин, не может быть OE-
маршрутом.
Рис. 1. Пример графа, в котором все вершины нечетной степени должны быть началом покрывающей OE-цепи
Таким образом, для указанного примера мощность эйлерова OE-покрытия (т.е. наименьшего по
мощности) не меньше величины 2k .
Для доказательства, что 2k является точной верхней оценкой мощности эйлерова OE-покрытия,
опишем процесс построения OE-покрытия, в котором каждая из вершин нечетной степени является
началом цепи [8].
Алгоритм параллельный. Организуем 2k процессов, которые стартуют в вершинах v1* , v2* , , v2*k . Начнем
построение OE-цепей с помощью процедуры ParallelFormChain() из вершин v1* , v2* , , v2*k . Для
синхронизации процессов используется глобальная переменная cur_rank. Процедура ждет продолжение
построения цепи, если ранг текущего ребра оказывается ниже cur_rank.
Процедура ParallelFormChain
Внешняя переменная: cur _ rank – синхронизатор по рангам ребер;
Входные данные: w – первая вершина цепи;
Выходные данные: v – последняя вершина текущей цепи v w ; e Q(v) ;
Do
e1 arg max eQ ( v ) rank(e) ;
e2 arg max eQ ( v ): f1 ( e ) f2 (e ) rank(e) ;
\\ Найти ребро максимального ранга, по возможности не являющееся мостом
If rank(e1 ) rank(e2 )
e e2 ;
Else
e e1 ;
EndIf
Wait ( rank(e) cur _ rank );
If ( e E (G) )
E(G) E(G) ‚ {e} ; \\ Удалить ребро e и объединить грани, разделенные ребром e
If v v1 (e)
REPLACE(e);
\\ Перестановка индексов функций ребра e с k на 3–k, k 1, 2 .
EndIf
Trailw Trailw {e} ;
v v1 (e) ;
EndIf
106
While ( (v
Vodd ) (Q(v) ) );
Return v;
EndProcedure
На каждом этапе будем добавлять по одному ребру в каждую из этих цепей.
Каждый из запущенных процессов вернет либо вершину нечетной степени, либо вершину,
инцидентную внешней грани. После окончания данных процессов необходимо упорядочить полученные
цепи по убыванию ранга стартовой вершины v1* , v2* , , v2*k . Сказанное выше можно обобщить в алгоритме
Parallel OE-Cover.
Алгоритм Parallel OE-Cover
Входные данные: G (V , E ) – плоский связный граф; Vodd V – множество вершин нечетной степени
графа G;
Выходные данные: Trail – OE-покрытие как упорядоченный массив ребер.
Initiate();
Order ();
SortOdd (); \\Сортировка вершин нечетной степени по убыванию их ранга
For each ( w Vodd ) DoParallel
\\Синхронизация процессов
cur _ rank max rank(Q(v)) ;
vVodd
\\Построение OE-цепи
ParallelFormChain ( w, v );
EndFor
Trail Trail (v1 ) • Trail (v2 ) • • Trail (v2k ) ;
Конец алгоритма
Таким образом, будет построено не более, чем 2k цепей.
Теорема доказана.
В качестве примера рассмотрим граф, приведенный на рис. 2.
Рис. 2. Пример графа для демонстрации работы алгоритма Parallel OE-Cover. Для каждого ребра указан его ранг
Выполнение алгоритма Parallel OE-Cover можно представить в виде следующей таблицы.
Таблица. Трассировка работы алгоритма Parallel OE-Cover по шагам
cur _ rank P1 P2 P3 P4 P5
4 v11 – – – –
4 v11 – – – –
3 v6 v12 v13 v14 v15
107
3 v6 v12 v13 v14 v15
2 v1 v7 v8 v9 v10
2 – v7 v8 v9 v10
2 – v5 v4 v3 v2
2 – v1 v5 v2 v5
2 – v2 – – –
1 – v5 v4 v3 –
1 – – v3 – –
Всего будет запущено шесть процессов по числу вершин нечетной степени. Первым начнется
построение цепи из вершины v11 максимального ранга. Остальные процессы будут дожидаться, когда
ранг текущего ребра совпадет со значением cur _ rank . Так, на третьей итерации алгоритма стартует еще
четыре процесса из вершин v12 , v13 , v14 и v15 . Шестой процесс, который должен стартовать из вершины v1 ,
не будет начат, так как эта вершина будет достигнута первым процессом, и она станет концевой для цепи,
построенной этим процессом. Так, в результате работы процессов будет построено пять OE-цепей,
которые, будучи упорядоченными в соответствии с убыванием ранга начальной вершины, дадут
эйлерово OE-покрытие графа, представленного на рисунке 2. Следовательно, построенное покрытие
представляет собой последовательность цепей: C1 v11v11v6 v6 v1 ; C2 v12 v12 v7 v7 v5v1v2 v5 ; C3 v14 v14 v9 v9 v3v2 v3 ;
C4 v15v15v10 v10 v2 v5 ; C5 v13v13v8v8v4 v5v4 v3 .
Таким образом, на мощность покрытия влияет факт наличия мостов в графе. В случае графа без мостов
достиается нижняя граница, если существует хотя бы одна верина нечетной степени, смежная внешней
грани. Если таких вершин нет, то мощность покрытия на единицу больше нижней оценки.
Ограничения со стороны технологического процесса
В данном разделе будем рассматривать только графы, для которых достигается нижняя оценка, т.е.
графы, не имеющие мостов и имеющие хотя бы одну вершину нечетной степени, смежную внешней грани.
Одним из критериев оценки упаковки деталей на листе раскроя может быть возможность или
невозможность выполнения построенного раскроя автоматом плазменной резки. Технология
плазменной резки требует наличия некоторого пространства для размещения точки врезки рядом с
местом начала реза по контуру детали. В связи с этим возникает необходимость формировать маршрут
инструмента с учетом этого ограничения. Кроме того, время, затраченное на осуществление врезки,
сильно влияет на суммарное время вырезания. В соответствии с этими ограничениями возникает задача
допустимости осуществления плазменной резки для заданной упаковки деталей. Более того, возникает и
задача минимизации числа точек врезки. В соответствии с теоремой 1 число точек врезки для плоского
графа, не имеющего мостов и имеющего хотя бы одну вершину, смежную внешней грани, равно | Vodd | /2 .
Тем не менее, в теореме 1 отсутствуют ограничения на выбор точек врезки.
Например, рассмотрим раскройные планы, приведенные на рисунке 2. Заметим, что при
формировании этих раскройных планов использовалось совмещение резов, таким образом, врезка для
рассматриваемого примера технологически возможна только с внешней грани (в общем случае – только
с граней, допускающих врезку). Следовательно, реализация раскроя инструментом плазменной резки
возможна для раскройного плана, приведенного на рисунке 2.б) и не возможна для раскройного плана на
рисунке 2.а), так как для него необходимо ввести дополнительные точки врезки для вырезания
внутренних прямоугольников R4 и R5 (см. рис.2.а)). Для раскройного плана, представленного на рисунке
2.б) возможно разместить все точки врезки на внешней грани соответствующего графа.
Формализуем рассмотренную задачу следующим образом.
Предположим, что грани Fin (G) F (G) допускают размещение точки врезки. Тогда обозначим через
Vin (G) V (G) вершины нечетной степени, инцидентные Fin (G) . Если маршрут в графе является OE-
маршрутом и начальная вершина v1 Vin (G) , то на его основе может быть построена программа раскроя
для автомата плазменной резки. Такой маршрут будем называть PPOE-маршрутом (ОЕ-маршрутом с
разрешенными точками врезки).
108
а) б)
в) г)
Рисунок 2. Пример нереализуемого и реализуемого раскройных планов для технологии плазменной резки (в вершинах,
отмеченных белым, допустима врезка)
Определение 5. OE-цепь C v1e1v2e2 vk называется PPOE-цепью, если ее начальная вершина v1 Vin (G) .
Определение 6. Упорядоченная последовательность реберно-непересекающихся PPOE-цепей,
покрывающая все ребра графа G, называется PPOE-покрытием.
Определение 7. Эйлеровым PPOE-покрытием называется минимальная по мощности упорядоченная
последовательность реберно-непересекающихся PPOE-цепей.
Графы на рисунках 2.в) и 2.г) являются образами раскройных планов на рисунках 2.а) и 2.б)
соответственно. Вершины Vin не закрашены. В окрестностях этих вершин допускается размещение точки
врезки. Напротив, в вершинах, закрашенных черным, невозможно размещение точки врезки. Таким
образом, для графа на рисунке 2.г) существует PPOE-покрытие, например, C1 v1v3v5v6 v9 v8v5 ; C2 v3v7 v8 ;
C3 v7 v11v10 v9 ; C4 v11v12 v10 ; C5 v12 v4 v6 ; C6 v4 v2 v1v2 . Для графа на рисунке 2.в) такого покрытия не
существует.
Задачу определения возможности реализации раскроя инструментом плазменной резки можно
сформулировать в терминах задачи идентификации существования эйлерова PPOE-покрытия для
данного графа. В соответствии с отмеченными выше ограничениями (вершина, соответствующая точке
врезки, должна принадлежать либо внешней грани, либо другой грани, допускающей наличие таких
вершин) можно сформулировать следующее необходимое условие существования PPOE-покрытия.
Теорема 2 (необходимое условие существования PPOE-покрытия). Пусть G – плоский граф,
имеющий 2k вершин нечетной степени. Если в графе существует PPOE-покрытие, то | Vin (G) | k .
а) б)
Рисунок 3. Примеры графов, не имеющих PPOE-покрытия
109
Например, граф на рисунке 3.а) не может быть покрыт PPOE-цепями. Он имеет восемь вершин
нечетной степени, может быть покрыт как минимум четырьмя цепями, из них только три могут
начинаться в вершинах, допускающих начало PPOE-цепи. Данное условие является необходимым, но не
достаточным. Так, для графа на рисунке 3.б) существует четыре вершины, которые могут служить
началом PPOE-цепи, и столько же вершин, которые не могут являться началами такой цепи. Тем не менее,
для этого графа не существует PPOE-покрытия.
Пути, реализующие PPOE-покрытие, можно представить как упорядоченную последовательность
PPOE-цепей, соединенных т.н. дополнительными (фиктивными) ребрами между концом текущей и
началом следующей цепей. Такие переходы образуют паросочетание в двудольном орграфе
D (Vin vout Vin , E) , где Vin – множество всех вершин нечетной степени, которые могут выступать в
качестве начала PPOE-цепи (точки врезки); Vout – множество вершин нечетной степени, которые могут
выступать только концами построенных цепей (точки выхода).
Теорема 3 (необходимое условие существования PPOE-покрытия). Для существования PPOE-цепи
необходимо, чтобы в смешанном графе G D существовал цикл, все дуги которого принадлежат
{(v, u) : v Vout Vin ,u Vin }.
Доказательство. PPOE-покрытие является частным случаем OE-покрытия, следовательно, оно
является ориентированным циклом, содержащем ребра графа G и ребра паросочетания M на множестве
вершин Vodd G , где Vodd Vin Vout . Поскольку PPOE-покрытие состоит из PPOE-цепей, тогда ребра из
паросочетания M должны быть пройдены в направлении Vout Vin Vin . В случае указанной ориентации
ребер паросочетания они будут совпадать с дугами из D. Таким образом, для существования PPOE-
покрытия необходимо существование цикла в смешанном графе G D , в котором все дополнительные
ребра являются дугами из Vout Vin в Vin . Теорема доказана.
Теорема 4 (необходимое условие существования PPOE-покрытия). Для существования PPOE-
покрытия в плоском связном графе G необходимо, чтобы мощность минимального {Vin , Vout } -разреза
превосходила | Vout | .
Доказательство. Предположим, что существует PPOE-покрытие графа G. Тем не менее, мощность
{Vin , Vout } -разреза не превосходит | Vout | . Так как ни одна из PPOE-цепей, формирующих покрытие, не
может начинаться в вершинах u Vout , то покрытие будет состоять из не менее, чем | Vout | путей из вершин
v Vin в вершины u Vout . В этом случае некоторые пути могут оказаться реберно-непересекающимися,
откуда следует противоречие с определением PPOE-покрытия. Теорема доказана.
В качестве примера можно обратиться к графу на рисунке 3.б). Начало PPOE-цепи может располагаться
только в неокрашенной вершине. В графе имеется десять вершин нечетной степени, следовательно,
достаточно минимум пяти стартовых вершин. Граф имеет пять таких вершин, тем не менее, невозможно
покрыть граф цепями, начинающимися в этих вершинах. Можно построить максимум три цепи,
начинающиеся в неокрашенной (белой) вершине, и заканчивающиеся в окрашенной (черной), например,
C1 v5v9 v8v10 v9 , C2 v3v8v7 v6v8 , C3 v4 v3v2 v6 . Таким образом, минимальный разрез между окрашенными и
неокрашенными вершинами имеет три ребра.
Построение PPOE-покрытия графа G позволяет решить задачу маршрутизации для пути режущего
инструмента с ограничениями на выбор точки врезки.
Заключение
Для реализации технологии вырезания деталей раскройного плана с совмещенными резами
существует достаточно мало алгоритмов.
Найденные в статье необходимые условия возможности реализации раскроя машиной лазерной резки
с ограничениями на врезку следует учитывать при составлении раскройных планов.
Тем не менее, вопрос формулировки достаточных условий остается открытым. К направлениям
дальнейших исследований можно отнести следующие случаи: вершина может выступать как точкой
врезки, так и точкой выхода; точками врезки могут выступать вершины четной степени.
Благодарности
Статья выполнена при поддержке Правительства РФ (Постановление №211 от 16.03.2013 г.),
соглашение № 02.A03.21.0011.
Литература
1. Dewil, R., Vansteenwegen, P., Cattrysse, D. A review of cutting path algorithms for laser cutters // International Journal Adv Manuf.
Technol., – 2016. – Vol. 87. – P. 1865-1884.
110
2. Dewil, R., Vansteenwegen, P., Cattrysse, D., Laguna, M., Vossen, T. An improvement heuristic framework for the laser cutting tool
path problem // International Journal of Production Research. – 2015. – Vol.53, Iss. 6. – P. 1761-1776.
3. Manber U., Israni S. Pierce point minimization and optimal torch path determination in flame cutting // J. Manuf. Syst. – 1984. -Vol.
3(1). P. 81-89.
4. Макаровских Т. А., Савицкий Е. А. Абстрагирование раскройного плана до плоского графа для эффективного решения
задачи вырезания деталей // Вестник УГАТУ. – 2015. – Т. 19. № 3 (69). – С. 190–196.
5. Panioukova T. A., Panyukov А. V. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs // Proc. 6th
Workshop on Computer Science and Information Technologies CSIT’2003. – 2003. – Vol. 1. P. 134-138.
6. Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. – 2007. – Vol. 46,
No. 1. – P. 83-92.
7. Makarovskikh Т. А., Panyukov А. V., Savitsky E. A. Mathematical Models and Routing Algorithms for CAM of Technological Support
of Cutting Processes // IFAC-PapersOnLine 49–12. – 2016. – 821-826.
8. Макаровских Т.А. Оценка мощности OE-покрытия плоского графа // Вестник Уфимского государственного авиационного
технического университета. – 2017. – Т. 21. № 2 (76). – С. 112-118.
9. Панюкова Т.А. Цепи с упорядоченным охватыванием в плоских графах // Дискретный анализ и исследование операций. –
2006. – Т. 13, № 2. – С. 31–43.
References
1. Dewil, R., Vansteenwegen, P., Cattrysse, D. A review of cutting path algorithms for laser cutters // International Journal Adv Manuf.
Technol., – 2016. – Vol. 87. – P. 1865-1884.
2. Dewil, R., Vansteenwegen, P., Cattrysse, D., Laguna, M., Vossen, T. An improvement heuristic framework for the laser cutting tool
path problem // International Journal of Production Research. – 2015. – Vol.53, Iss. 6. – P. 1761-1776.
3. Manber U., Israni S. Pierce point minimization and optimal torch path determination in flame cutting // J. Manuf. Syst. – 1984. -Vol.
3(1). P. 81-89.
4. Makarovskikh T.A., Savitsky E.A. Abstragirovanie raskrojnogo plana do ploskogo grafa dlja jeffektivnogo reshenija zadachi
vyrezanija detalej // Vestnik UGATU. – 2015. – Vol. 19. № 3 (69). – P. 190–196.
5. Panioukova T. A., Panyukov А. V. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs // Proc. 6th
Workshop on Computer Science and Information Technologies CSIT’2003. – 2003. – Vol. 1. P. 134-138.
6. Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. – 2007. – Vol. 46,
No. 1. – P. 83-92.
7. Makarovskikh Т. А., Panyukov А. V., Savitsky E. A. Mathematical Models and Routing Algorithms for CAM of Technological Support
of Cutting Processes // IFAC-PapersOnLine 49–12. – 2016. – 821-826.
8. Makarovskikh T.A. Ocenka moshhnosti OE-pokrytija ploskogo grafa // Vestnik Ufimskogo gosudarstvennogo aviacionnogo
tehnicheskogo universiteta. – 2017. – Vol. 21. № 2 (76). – P. 112-118.
9. Panyukova T.A. Cepi s uporjadochennym ohvatyvaniem v ploskih grafah // Diskretnyj analiz i issledovanie operacij. – 2006. – Vol.
13, №2. – P. 31–43.
Об авторах:
Макаровских Татьяна Анатольевна, кандидат физико-математических наук, доцент, доцент кафедры
«Математическое и компьютерное моделирование», Южно-Уральский государственный
университет, Makarovskikh.T.A@susu.ru
Савицкий Егор Александрович, ассистент кафедры «Математическое и компьютерное моделирование»,
Южно-Уральский государственный университет, egor88@inbox.ru
Note on the authors:
Makarovskikh Tatiana A., candidate of Physics and Mathematics, Associate professor of department of
Mathematical and Computer Modeling, South Ural State University, Makarovskikh.T.A@susu.ru
Savitsky Egor A., assistant of department of Mathematical and Computer Modeling, South Ural State University,
egor88@inbox.ru
111