Савицкий Е.А., Макаровских Т.А.

Abstract

При использовании технологии лазерной резки листового материала требуется наличие некоторого пространства для осуществления врезки. При использовании в качестве образа раскройного плана плоского графа 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.

THE OE-COVER FOR A PLANE GRAPH BY CHAINS WITH ALLOWED STARTING VERTICES 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.

Plane graph; Path; Pierce point; edge-disjoint cover; ordered enclosing. Преимуществом при использовании лазерной резки является минимальность таких показателей ширина реза и термические деформации. Целью задачи определения маршврлуятеатсярезпкоиискя такого пути режущего инструмента, при котором выполняются условия предшествования, а в затраченное на вырезание, минимально [ 1 ].

В терминах задачи лазерной резки под условием предшествования понимается требование к чтобы отрезаннаяот листа часть не требовала дополнительных разрезаний (т.е. все элеме вложенного контура должны быть вырезаны прежде, чем внешний контур окажется полно вырезанным).

Общее время, требуемое на выполнение резки, можно представить как суммдалряное время осуществления всех вырезаний, времени на выполнение холостых переходов, времени на врезку и как основным условием предшествования при выполнении лазерной резки является требовани отсутствию разрезаний для уже отрезанной части листа, то

- во-первых, все элементы внутренних контуров должны быть вырезаны прежде, чем будут пол отрезаны от листа внешние контуры;

- во-вторых, необходимо учитывать термальные эффекты, например, стоит избегать пересечен имеющихся резов.

В [ 1 ] и [2] присвяодкилтассификация задач маршрутизации режущего инструмента и отмечается, ч технологии ECP (Endpoint Cutting Problem) и ICP (Intermittent Cutting Problem) за счет возм совмещения границ вырезаемых деталей позволяют сократить расход материраелзак,и, длиинудлину холостых проходов [2]. Проблемы уменьшения отходов материала и максимального совмеще фрагментов контуров вырезаемых деталей решаются на этапе составления раскройного плана. отмечено, что для решения задачи ECP известен алкгортоиртымй [3н]а,ходит траекторию движения режущего инструмента и минимизирует число точек врезки. Для решения этой задачи авторами [ 3 ] использован аппарат теории графов, предложенный в работе алгоритм строит дополнительные между вершинами нечетнсотйепени графа, инцидентными одной грани. Тем не менее, в общем с при добавлении дополнительных ребер между парами вершин нечетной степени граф не будет Более того, не все вершины нечетной степени могут выступать в качестве начпаелйь.ных вершин В данной статье авторами рассматривается решение задачи оптимизации пути режущего инстру в случае, когда раскройный план является плоским неэйлеровым графом, а на траекторию д режущего инструмента наложены следующие ограничения: отярезаонтна листа часть не требует дополнительных разрезаний, а возможтноычкеи врезки заданы. Определения и обозначения

Для решения поставленной задачи [4]. Моделью раскройного листа будем G с внешней граньfю0 на плоскостиS.

раскройный план необходимо представить в виде плоского

считкатоьстьпSл,осмоделью раскройного пл–апнлаоский граф Для плоского грGафдаалее черезE(G) будем обозначать множество его внутренностями, ребер, представляющих гомеоморфные отрезкам.

плоские жордановы ЧеVр(еGз) обозначим

кривырено с непеорпеасекающимися множество граничных точек этих кривых.

Для любой части грJафаG (части траектории движения режущего инструмента) обозначзим чере Int  J  теоретико-множественное объединение его внутренних граней (объединение всех связных компонент S ‚ J , не содержащих внешней грани). InТtо(Jгд)а можно интерпретировать как отрезанную

отислта часть. Множества вершин, ребер и граJнбеуйдемграфобаозначать черVе(зJ ) , E(J ) и F(J) соответственно, а черMез| –|число элементов

множестMв.а Начальную часть маршрута в Gгрбауфдем рассматривать как часть графа, содержащую все вершины и ребра, принадлежащие этой части маршрута. Это позволяет формализовать требование к ма режущего инструмента как условие отсутствия пересечения внутренних граней любой начальной маршрута в заданном плоском Gгрсаферебрами его оставшейся части [5]. Такие маршруты буде называть маршрутами с упорядоченным охватыванием [6] (или длOяE-мкаррашторсуттиами, гдOеE – от англ. o“rdered enclosing”).

Определение 1 [5]. Цепь C  v1e1v2e2 vk в плоском графе G имеет упорядоченное охватывание (является OE-цепью), если для любой его начальной части Cl  v1e1v2e2 el l  (| E |) выполнено условие Int Cl   G   .

Определение 2 [6]. Упорядоченная последовательность реберно-непересекающихся OE-цепей

C0  v0e10v10e20...ek00 vk00 , C1  v1e11v11e12...e1k1v1k1 , ,

Cn1  vn1e1n1v1n1e2n1...eknn11vknn11, m :m  n,  lm01Int(Cl )   n1 Cl   , lm называется маршрутом с упорядоченным охватыванием (OE-маршрутом).

Построение OE-маршрута графаG решает поставленную задачу раскроя. Наибольший представляют маршруты с минимальным числом цепей, поскольку переход от одной соответствует холостому проходу режущего инструмента.

Определение 3. ОЕ-маршрут, содержащий минимальную по мощности упорядоченную последовательность реберно-непересекающихся цепей в плоском графе G будем называть эйлеровым маршрутом с упорядоченным охватыванием (эйлеровым OE-маршрутом), а составляющие его OE-цепи – эйлеровым OE-покрытием.

Топологическое представлениеплоского графа G  (V , E) на плоскостиS с точностью гомеоморфизма определяется заданием для каждогоe реEбрслаедующих функций [4]: • vk (e) , k  1, 2 – вершины, инцидентныеебру e; fk (e) – грань, находящаяся справа

при движении поe отребвреуршиныvk (e) к вершине v3k (e) , k  1, 2 ; интерес

цепи к до lk (e) – ребро, инцидентное гранf3иk (e) и vk (e) , k  1, 2 ; rk (e) – ребро, инцидентное гранfkи(e) и vk (e) , k  1, 2 . Поскольку функцииvk (e) , fk (e) , lk (e) , rk (e) , k  1, 2 , построенные на ребрах гGраф(Vа , E) , для каждого ребра определяют инцидентные вершины, инцидентные грани и смтеожн ысперарвебдрлаи,во следующее

Утверждение. Функции vk (e) , fk (e) , lk (e) , rk (e) , k  1, 2 , построенные на ребрах графа G  (V , E) , определяют плоский граф G  (V , E) с точностью до гомеоморфизма.

Данное утверждение справедливо, поскольку

фунvкk(цeи) и, fk (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  f0} – множество ребер, ограничивающих внешнюю грань f0 графа G  (V , E) , тогда e  E1 rank(e)  1 ; пусть Ek (G) – множество ребер ранга 1 графа   k1 Gk V , E \    l1

  El  ,   тогда e  Ek rank(e)  k  .

Ранг ребра определяет его удаленность от внешней грани и показывает, какое минимальное граней необходимо пересечь, чтобы добраться от внешнfе0йдо грэатноиго ребра. Мощность эйлерова OE-покрытия

Рассмотрим произвольный плоский связный граф. В этом случае справедлива следующая теоре оценке мощности эйлероOвEа-покрытия.

Теорема 1 [8]. Пусть G – плоский связный граф, Vodd (G) – множество вершин нечетной степени графа G, тогда для мощности N эйлерова OE-покрытия графа G имеет место неравенство k  | Vodd (G) |  N | Vodd (G) | 2k.

2 Причем, как верхняя, так и нижняя оценки достижимы.

Доказательство. Из теоремы Листи–нЛгаюка селдует, что нижняя оценка не может бытьk. меньше Эта граница достигается для графов без мостов, имеющих хотя бы одну вершину нечетной

Рис. 1. Пример графа, в котором все вершины нечетной степени должны быть началом покрывающей OE-цепи Таким образом, для указанного примера мощность мощности) не мешнеь величины2k .

Для доказательства, чт2оk является точной верхней оценкой мощности опишем процесс построениOяE-покрытия, в котором каждая из вершин началом ецпи [8].

Алгоритм параллельный. Организуеkмпр2оцессов, которые стартуют в вершv1и, нv2*а,х, v2*k . Начнем * эOйEл-перооквраытия (т.е. наименьшего по

эйOлEе-рпоовкарытия, нечетной степени являет построение OE-цепей с помощью процедуPрaыrallelFormChain() из синхронизации процессов испольтзсуяе глобальная переменнcаuяr_rank. Процедура построения цепи, если ранг текущего ребра оказываеcтuсrя_ranнkи.же Процедура ParallelFormChain Внешняя переменная: cur _ rank – синхронизатор по рангам ребер; Входные данные: w – первая вершина цепи; Выходные данные: v – последняя вершина текущей цvепиw ; e  Q(v) ; Do вершинv1*, v2*, , v2*k .

Для ждет продолжение e1  arg maxeQ(v) rank(e) ; e2  arg maxeQ(v):f1(e) f2 (e) rank(e) ;

e  e2 ;

Else

e  e1 ;

EndIf

Wait ( rank(e)  cur _ rank ); \\ Найти ребро максимального ранга, по возможняовслтяиющнеееся мостом

If rank(e1)  rank(e2 ) If ( e  E(G) )

E(G)  E(G) ‚ {e}; \\ Удалить ребрeои объединить грани, разделенные рeебром If v  v1(e)

REPLACE(e); \\ Перестановка индексов функций рeебсрkана –3k, k  1, 2 .

EndIf

Trailw  Trailw {e}; v  v1(e) ;

EndIf

Return v;

EndProcedure

На каждом этапе будем добавлять по одному ребру в каждую из этих цепей. Каждый из запущенных процессов вернет либо вершину нечетной степени, либо вер инцидентную внешней грани. Покслонечаония данных процессов необходимо упорядочить полученные цепи по убыванию ранга стартовой веvр1*ш,vи2*,ны, v2*k . Сказанное выше можно обобщить в алгоритме Parallel OE-Cover.

Алгоритм Parallel OE-Cover Входные данные: G  (V , E) – плоский связный граVфod;d  V – множество вершин нечетной степени графа G; Выходные данные: Trail – OE-покрытие как упорядоченный массив ребер.

Initiate(); Order (); SortOdd (); \\Сортировка вершин нечетнотйепесни по убыванию их ранга

For each ( wVodd ) DoParallel

\\Синхронизация процессов cur _ rank  max rank(Q(v)) ; vVodd \\Построение O-Eцепи

ParallelFormChain ( w,v );

EndFor

Trail  Trail(v1) •Trail(v2 ) • •Trail(v2k ) ; Конец алгоритма Таким образом, будет построено не бол2еkе,цепчейм. Теорема доказана. В качестве примера рассмотрим граф, приведенный2. на рис. Рис. 2. Пример графа для демонстрации работы алгоритма Parallel OE-Cover. Для каждого ребра указан его ранг Выполнение алгоритмPаarallel OE-Cover можно представить в виде следующей таблицы. Таблица. Трассировка работы алгоритма Parallel OE-Cover по шагам cur _ rank 4 4 3

P 1 v11 v11 v6

P 2 – – v12

P 3 – – v13

P 4 – – v14

P 5 – – v15 Всего построение будет цепи запущено шесть процессов из вершиv1н1ымаксимального числу Олсьтаные вершин процессы нечетной будут степени. Первым дожидаться, когда на ранг текущего ребра совпадет со знаcчuеrн_иrеaмnk . Так, на третьей итерации алгоритма стартует еще четыре процесса из вершv12и,нv13 , v14 и v15 .

Шестой процесс, который должен стартовать из v1 ,вершины не будет начат, так как эта вершина будет достигнута первым процессом, и она станет концев построенной этим процессом. вТак,результате работы процессов будет построенOоE-цпепятейь, которые, будучи упорядоченными в соответствии с убыванием ранга начальной вершины, эйлерово OE-покрытие графа, представленного на рисунке 2. Следовательно, построенное покрыт представляет собой последовательность цепCе1й: v11v11v6v6v1 ; C2  v12v12v7v7v5v1v2v5 ; C3  v14v14v9v9v3v2v3 ; C4  v15v15v10v10v2v5 ; C5  v13v13v8v8v4v5v4v3 .

Таким образом, на мощность покрытия влияет факт наличия мостов в ргарфаафе.беВз мслоусчтаоев г достиается нижняя граница, если существует хотя бы одна верина нечетной степени, смежная грани. Если таких вершин нет, то мощность покрытия на единицу больше нижней оценки. Ограничения со стороны технологического процесса

В данномаздреле будем рассматривать только графы, для которых достигается нижняя оценка, графы, не имеющие мостов и имеющие хотя бы одну вершину нечетной степени, смежную внеш Одним из критериев оценки упаковки деталей на листе раскроя момжоежтносбтьытьиливоз невозможность выполнения построенного раскроя автоматом плазменной Терхензоклио.гия плазменной резки требует наличия некоторого пространства для размещения точки врезки ря местом начала реза по контуру Вдетсавляиз.и с этим возникоабехтодинмеость формировать маршрут инструмента с учетом этого ограничения. Кроме того, время, затраченное на осуществление сильно влияет на суммарное время вырезания. В соответствии с этими ограничениями возникает допустимости осуществления пзмлаенной резки для заданной упаковки деталей. Более того, возникает задача минимизации числа точек врезки. В соответствии с теоремой 1 число точек врезки дл графа, не имеющего мостов и имеющего хотя бы одну вершину, смежную вне ш|Vнoеddй| /2г.рани, равн Тем не менее, в теореме 1 отсутствуют ограничения на выбор точек врезки.

Например, рассмотрим раскройные планы, приведенные на рисунке 2. Заметим, что формировании этих раскройных планов использовалось совмещение ремзово, бртаазкоим, врезка для рассматриваемого примера технологически возможна только с внешней грани (в –отбощльемко случае с граней, допускающих врезку). Следовательно, реализация раскроя инструментом плазменной ре возможна для раскройного плана, привегдоеннао рисунке 2.б) и не возможна для раскройного план рисунке 2.а), так как для него необходимо ввести дополнительные точки врезки для в внутренних прямоугольниковR4 и R5 (см. рис.2.а)). Для рроайснкого плана, представленного на рисунке 2.б) возможно разместить все точки врезки на внешней грани соответствующего графа. Формализуем рассмотренную задачу следующим образом. Предположим, что гранFiиn(G)  F(G) допускают размещение точкиезквир. Тогда обозначим через Vin (G)  V (G) вершины маршрутом

и начальная для автомата плазменной резки. разрешенными точками врезки).

нечетной степени, инцидентнFiыn(еG) . Если маршрут в графе явOлEя-ется вершvи1наVin (G) , то на его

основе может быть постромемнаа рпарсокгрроая Такой маршрут

будем PPнOаEзы-мваартшь рутом О(Е-маршрутом с Рисунок 2. Пример нереализуемого и реализуемого раскройных планов для технологии плазменной резки (в вершинах, отмеченных белым, допустима врезка) Определение 5. OE-цепь C  v1e1v2e2 vk называется PPOE-цепью, если ее начальная вершина v1 Vin (G) . Определение 6. Упорядоченная последовательность реберно-непересекающихся PPOE-цепей, покрывающая все ребра графа G, называется PPOE-покрытием.

Определение 7. Эйлеровым PPOE-покрытием называется минимальная по мощности упорядоченная последовательность реберно-непересекающихся PPOE-цепей.

Графы на рисунках 2.в) и 2.г) яовблряаюзатмсяи раскройных планов на рисунках 2.а) и 2.б) соответственно. ВершиныVin не закрашены. В окрестностях этих вершин допускается размещение точк врезки. Напротив, в вершинах, закрашенных черным, образом, для графа на рисунке 2.г) суPщPеOсEтв-пуоектрытие, невозможно

размещение ит.очТкиакимврезк напримерC,1  v1v3v5v6v9v8v5 ; C2  v3v7v8 ; C3  v7v11v10v9 ; C4  v11v12v10 ; C5  v12v4v6 ; C6  v4v2v1v2 . Для грааф на рисунке 2.в) такого покрытия не существует.

Задачу определения возможности реализации раскроя инструментом плазменной резки сформулировать в терминах задачи идентификации существования эPйPлOеEр-опвоакрытия для данного графа. В соответствитимечсенноыми выше ограничениями (вершина, соответствующая точке врезки, должна принадлежать либо внешней грани, либо другой грани, допускающей наличие вершин) можно сформулировать следующее необходимое условие сущесPтPвOовEа-пноикярытия.

Теорема 2 (необходимое условие существования PPOE-покрытия). Пусть G – плоский граф, имеющий 2k вершин нечетной степени. Если в графе существует PPOE-покрытие, то | Vin (G) | k . мож а)

б) Рисунок 3. Примеры графов, не имеющих PPOE-покрытия Например, граф на рисунке 3.а) не может бытPьPOEп-цоекпряымти. Он имеет восемь вершин нечетной степени, может быть покрыт как минимум четырьмя цепями, из них только тр начинаться в вершинах, допускающих нPаPчOалEо-цепи. Данное условие является необходимым, но не достаточным. Так, для графа на рисунке 3.б) существует четыре вершины, которые могут началом PPOE-цепи, и столько же вершин, которые не могут являться началами такой цепи. Тем для этого графеа снуществуеPтPOE-покрытия.

Пути, реализующиеPPOE-покрытие, можно представить как упорядоченную последовательность PPOE-цепей, соединенных т.н. дополнительными (фиктивными) ребрами между концом текущей началом следующей цепей. Такие переходы образруоюсточетапнаие в двудольном орграфе D  (Vin vout Vin , E) , гдеVin – множество всех вершин нечетной степени, которые могут выступать качестве началаPPOE-цепи (точки врезкVиo)u;t – множество вершин нечетйно степени, которые могут выступать только концами построенных цепей (точки выхода).

Теорема 3 (необходимое условие существования PPOE-покрытия). Для существованиPяPOE-цепи необходимо, чтобы в смешанном гGрафDе существовал цикл, е вс дуги которого принадлежат {(v,u) : v Vout Vin,u Vin}.

Доказательство. PPOE-покрытие является частным случаOеEм-покрытия, следовательно, оно является ориентированным циклом, содержащем ребраG играфреабра паросочетанMияна множестве вершин Vodd G , гдеVodd  Vin Vout . ПосколькуPPOE-покрытие состоит PиPзOE-цепей, тогда ребра из паросочетания M должны быть пройдены в направVлoеuнtииVin Vin . В случае указанной ориентации ребер паросочетания они будут асотьвпадс дугами D.из Таким образом, для существовPаPнOиEяпокрытия необходимо существование цикла в смешанномG гDра,фев котором все дополнительные ребра являются дугамиVouиtзVin в Vin . Теорема доказана.

Теорема 4 (необходимое условие существования PPOE-покрытия). Для существованияPPOEпокрытия в плоском связном Gгранфеоебходимо, чтобы мощность минимальн{Vоiгn о,Vout} -разреза превосходила |Vout | . {Vin , Vout} -разреза Доказательство. Предположим, что существуPеPтOE-покрытие графаG. Тем не не превосход|иVтout | . Так как ни одPнPаOE-ицзепей, формирующих менее, мощность покрытие, не может начинаться в вершиuнаVхout , то покрытие будет состоять из не |Vмoеutн|ееп,утечйем из вершин v Vin в вершиныu Vout . В этом случае некоторые пути могут оказать-нсяепересбеекранюощимися, C1  v5v9v8v10v9 , C2  v3v8v7v6v8 , C3  v4v3v2v6 . Таким неокрашенными вершинами имеет три ребра.

Построение PPOE-покрытия графаG позволяет решить азчаду маршрутизации для пути режущего инструмента с ограничениями на выбор точки врезки. Заключение

Для реализации технологии вырезания деталей раскройного плана с совмещенными существует достаточно мало алгоритмов.

Найденные в статье необходимыоевиуяслвозможности реализации раскроя машиной лазерной резки с ограничениями на врезку следует учитывать при составлении раскройных планов.

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

Статья выполнена при соглашение № 02.A03.21.0011.

поддержке Правительства РФ (Постановление №211

отг.), 16.03.2013

References

наук, доцент, доцент кафедры -УЮржалньоский государственный

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 .

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 .

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 .

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 -C2S0I0T3'2 . 0 - 0V3o .l. 1. P. 134 - 138 .

Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. - 2007 . - Vol. 46 , No. 1. - P. 83 - 92 .

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.

Макаровских Т.А . Оценка мощност-ипокOрEытия плоского графа // ВестниимкскоУгфо государственного авиационного технического университета- . 2017 . - Т. 21. № 2 - С(7.6)1 . 1 - 2118 .

Technol. , - 2016 . - Vol. 87 . - P. 1865 - 1884 .

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 .

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 .

Makarovskikh T.A. , Savitsky E.A. Abstragirovanie raskrojnogo plana do ploskogo grafa dlja jeffektivnogo reshenija zadachi vyrezanija detalej // Vestnik UGATU . - 2015 . - Vol. 19 . № 3 - P( 6 .19) 9 . 0 - 196 .

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 -C2S0I0T3'2 . 0 - 0V3o .l. 1. P. 134 - 138 .

Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. - 2007 . - Vol. 46 , No. 1. - P. 83 - 92 .

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.

Makarovskikh T.A. Ocenka moshhnosti OE-pokrytija ploskogo grafa // Vestnik Ufimskogo gosudarstvennogo aviacionnogo tehnicheskogo universiteta . - 2017 . - Vol. 21 . № 2 ( 7 - 6P ).. 112 - 118 .

Panyukova T. A. Cepi s uporjadochennym ohvatyvaniem v ploskih grafah // Diskretnyj analiz i issledovanie operacij . - 2006 . - Vol.

13, № 2 -. P. 31 - 43 .