Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,737

ГРАФЫ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ И ИХ ПРИЛОЖЕНИЕ К ЗАДАЧАМ ОПТИМИЗАЦИИ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

Ерусалимский Я.М. 1
1 ФГАОУ ВО «Южный федеральный университет»
Определены два типа ограничений на достижимость вершин графа (возможность соединить одну вершину графа с другой путем): вершинная смешанная и вершинная барьерная. В случае вершинной смешанной достижимости на графе выделено подмножество вершин, по которым путь не может проходить подряд более определенного количества раз. Барьерная достижимость предполагает, что на графе выделены два подмножества вершин. Вершины первого подмножества увеличивают энергетический показатель движущегося по пути объекта, а вершины второго подмножества могут быть пройдены только при условии, что энергетический показатель достиг определенного уровня. Показано, как эти виды ограничений на достижимость, определенные в терминах вершин графа, свести к соответствующим типам ограничений на дугах графа. Рассмотрена задача нахождения оптимального пути выполнения технологического процесса при наличии ограничений на последовательность выполнения отдельных операций.
технологический процесс
достижимость
путь
граф
1. Басангова Е.О. Различные виды смешанной достижимости / Е.О. Басангова, Я.М. Ерусалимский // Алгебра и дискретная математика: сб. – Элиста: КГУ. – 1985. – C.70-75.
2. Водолазов Н.Н. Об особенностях потока в сетях с барьерной достижимостью / Н.Н.Водолазов // Вестник ДГТУ. – 2008. – Т.8. – № 2 (37). – С.127-136.
3. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью /Я.М. Ерусалимский // Модели, графы и алгебраические структуры: сб. – Элиста: КГУ, 1989. – С.45-48.
4. Ерусалимский Я.М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев-Кав. регион. Естественные науки. – 2003. – № 2. – C.3-5.
5. Ерусалимский Я.М. Графы с нестандартной достижимостью. Задачи, приложения: моногр. / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян. – Ростов-на-Дону: ЮФУ, 2009. – 195с.

В прикладных задачах, как правило, изучается не сам граф, а процессы на нём. Большинство из них связано с перемещениями по путям на графе. В классическом определении путь – это последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга. Соединимость одной вершины путём, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной (алгоритмической) теории графов связаны с достижимостью. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях по вершинам графа и задачи о потоках в сетях, поскольку поток можно считать перемещением (транспортировкой) «вещества» (информации, материи, товаров, жидкости, энергии и т.п.) из источника в сток по путям, ведущим из источника в сток.

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

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

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

Изучение графов с ограничениями на достижимость (далее – нестандартная достижимость) началось сравнительно недавно. Первые работы в этой области принадлежат Я.М. Ерусалимскому и Е.О. Басанговой ([1],[3]), следующие результаты принадлежат Я.М. Ерусалимскому, А.В. Скороходову, А.Г. Петросяну, М.В. Кузьминовой и Н.Н. Водолазову ([3]–[5]). В этих работах были определены и изучены различные типы нестандартной достижимости, в частности: смешанная, магнитная, вентильная, барьерная. Все эти типы ограничений формулировались в виде некоторых требований, предъявляемых к последовательности дуг, допустимых этим типом достижимости путей.

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

Ниже мы определим различные виды нестандартной достижимости, определяемые в терминах последовательности вершин пути. Будет показано, что каждый из введенных типов вершинной нестандартной достижимости сводится к соответствующему типу достижимости, определенному в терминах дуг графа (т.е. с определением пути как последовательности дуг). Тем самым результаты, полученные ранее (см. [5]), переносятся на графы с вершинной нестандартной достижимостью.

1. Вершинная смешанная достижимость порядка k

Определение 0.1. Ориентированным графом называют тройку , где – множество вершин графа, – множество дуг графа, – отображение смежности (инцидентности).

Определение 1.1. ▼ Пусть – орграф. Множество вершин графа . Вершинно-смешанным путем порядка k () на графе будем называть путь, на котором вершины из множества встречаются не более чем k раз подряд. ▲

Вершины множества будем называть нейтральными, а множества – запрещенными.

Определение 1.2. Графом с вершинной смешанной достижимостью порядка k будем называть граф, на котором допустимыми являются только смешанные пути порядка k.

Пример 1.1. ▼ На рис. 1.1. изображен граф с вершинной смешанной достижимостью порядка 3. Черная заливка – запрещенные вершины, серая – разрешенные вершины.

Рис. 1.1.

На этом графе пути 1– 2–4–6–8­– 10, 1–3–5– 7–9–10, 1–2–9–10, 1–2–4–6–8–3–5–7–9–10 запрещенные, а разрешенным путем из вершины 1 в вершину 10 является только один путь 1– 2–4–6–8­–7–9–10.▲

Со случаем, когда k=2 все обстоит очень просто, нужно из графа удалить дуги, обе граничные вершины которых находятся во множестве , и рассматривать обычную достижимость на полученном графе.

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

После такого перехода можно согласно [5] построить развёртку исходного графа – вспомогательный граф, позволяющий решать задачи о кратчайших путях, случайных блужданиях и потоках на развертке, а их решения интерпретировать как решение соответствующей задачи на исходном графе с ограничением на достижимость.

2. Вершинная барьерная достижимость высоты h

Пусть - граф, , множества , и попарно не пересекаются. Множество – множество нейтральных вершин, – множеством вершин, увеличивающих барьерный показатель (множество увеличивающих вершин), – множество барьерных вершин.

Определение 1.3. ▲ С каждым отрезком (где ) пути свяжем числовую характеристику , определенную индуктивно следующим:

1.

2.

Характеристика называется величиной накопленной энергии на отрезке пути .▼

Определение 1.4. ▼ Графом с барьерной достижимостью высоты будем называть граф , все пути , на котором удовлетворяют условию:

. ▲ (1.2)

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

Пример 1.2. ▼ Рассмотрим граф, изображенный на рис 4.11 с барьерной вершинной достижимостью порядка 2. Черная заливка – барьерные вершины, серая – увеличивающие вершины, без заливки – нейтральные вершины.

Рис. 1.2.

На этом графе пути 1– 2–4–6–8­– 10, 1–3–5– 7–9–10, 1–2–9–10 запрещенные, а разрешенным путем из вершины 1 в вершину 10 является путь 1–3–5–6–8­– 10▲

Как задачу о вершинной барьерной достижимости высоты h свести к барьерной достижимости высоты h (см. [5]), определенной на дугах графа?

Ясно, что нужно положить

; ,

и рассмотреть барьерную достижимость (на дугах графа) высоты h при определенном нами разбиении множества дуг графа.

После такого перехода можно построить развёртку исходного графа (см. [5]) – вспомогательный граф, позволяющий решать задачи о кратчайших путях, случайных блужданиях и потоках на развертке, а их решения интерпретировать как решение соответствующей задачи на исходном графе с вершинной барьерной достижимостью.

3. Возможные приложения смешанной достижимости

Рассмотрим описание технологического процесса в виде графа, вершины которого соответствуют различным состояниям изделия, в котором оно может находиться в процессе изготовления. Дуги графа соответствуют выполняемым операциям, переводящим изделие из одного состояния в другое.

Граф технологического процесса в этом случае представляет собой классическую сеть с одним входом (источником) и одним выходом (стоком).

Если под длиной дуги, ведущей из вершины x в вершину y, понимать стоимость выполнения операции, переводящей изделие из состояния x в состояние y, то мы получаем задачу поиска оптимального по стоимости пути выполнения технологического процесса.

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

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

Выводы

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

Рецензенты:

Наседкин А.В., д.ф.-м.н., профессор, профессор кафедры математического моделирования, Южный федеральный университет, г. Ростов-на-Дону;

Белявский Г.И., д.т.н., профессор, заведующий кафедрой исследования операций и высшей математики, Южный федеральный университет, г. Ростов-на-Дону.


Библиографическая ссылка

Ерусалимский Я.М. ГРАФЫ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ И ИХ ПРИЛОЖЕНИЕ К ЗАДАЧАМ ОПТИМИЗАЦИИ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ // Современные проблемы науки и образования. – 2014. – № 6.;
URL: http://science-education.ru/ru/article/view?id=15477 (дата обращения: 18.08.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252