Моделирование задачи землепользования на гиперграфах
Построена математическая модель задачи землепользования (рационального использования пахотных угодий) с применением аппарата гиперграфов. Проведено обоснование вычислительной сложности задачи, выделен ее полиномиально разрешимый подкласс и предложен соответствующий эффективный алгоритм ее решения. П...
Збережено в:
| Опубліковано в: : | Системні дослідження та інформаційні технології |
|---|---|
| Дата: | 2006 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2006
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/42191 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Моделирование задачи землепользования на гиперграфах / Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица // Систем. дослідж. та інформ. технології. — 2006. — № 3. — С. 99–109. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860260458178543616 |
|---|---|
| author | Заховалко, Т.В. Максишко, Н.К. Перепелица, В.А. |
| author_facet | Заховалко, Т.В. Максишко, Н.К. Перепелица, В.А. |
| citation_txt | Моделирование задачи землепользования на гиперграфах / Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица // Систем. дослідж. та інформ. технології. — 2006. — № 3. — С. 99–109. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Построена математическая модель задачи землепользования (рационального использования пахотных угодий) с применением аппарата гиперграфов. Проведено обоснование вычислительной сложности задачи, выделен ее полиномиально разрешимый подкласс и предложен соответствующий эффективный алгоритм ее решения.
Побудовано математичну модель задачі землекористування (раціонального використання орних угідь) із застосуванням апарату гіперграфів. Проведено обґрунтування обчислювальної складності задачі, виділено її підклас такий, що може бути поліноміально розв’язаний і запропоновано відповідний ефективний алгоритм цього розв’язання.
A mathematical model of the land use problem (rational use of arable lands) is built using hypergraph tools. The computational complexity of the problem is grounded, the polinomially solvable subclass is selected, and the proper effective algorithm of the solution is offered.
|
| first_indexed | 2025-12-07T18:54:35Z |
| format | Article |
| fulltext |
© Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица, 2006
Системні дослідження та інформаційні технології, 2006, № 3 99
TIДC
МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ,
ПРОБЛЕМИ І ТЕХНОЛОГІЇ ДОСЛІДЖЕННЯ
СКЛАДНИХ СИСТЕМ
УДК 519.8
МОДЕЛИРОВАНИЕ ЗАДАЧИ ЗЕМЛЕПОЛЬЗОВАНИЯ НА
ГИПЕРГРАФАХ
Т.В. ЗАХОВАЛКО, Н.К. МАКСИШКО, В.А. ПЕРЕПЕЛИЦА
Построена математическая модель задачи землепользования (рационального
использования пахотных угодий) с применением аппарата гиперграфов. Про-
ведено обоснование вычислительной сложности задачи, выделен ее полиноми-
ально разрешимый подкласс и предложен соответствующий эффективный ал-
горитм ее решения.
ВВЕДЕНИЕ
Как известно, аппарат теории графов — мощное средство моделирования
задач управления дискретными процессами и системами [1]. Однако неред-
ки случаи, когда с помощью инструментария обыкновенных графов невоз-
можно адекватно отразить в системном единстве сложную организацию
внутренних взаимосвязей моделируемой системы, а, следовательно, достичь
требуемой адекватности. Одним из путей разрешения создавшейся про-
блемной ситуации является использование инструментария гиперграфов
[1–3]. Необходимость такого перехода к аппарату гиперграфов возникает в
случае модификации известной задачи землепользования пахотными угодь-
ями [4, 5].
ПОСТАНОВКА ЗАДАЧИ
В работе [5] математическая модель задачи землепользования представлена
на 2-дольном графе. Вершинам первой (второй) доли соответствуют выра-
щиваемые культуры (поля, т.е. пахотные угодья хозяйства). Множество ре-
бер этого графа задает отношение возможности посева (размещения) опре-
деленной культуры на конкретном поле. Известна урожайность каждой
культуры на каждом поле. Так как урожайность культуры зависит от каче-
ства земли, на которой она выращивается, то общая эффективность исполь-
зования пахотных угодий (например, валовой выпуск) зависит от размеще-
ния культур по полям хозяйства. Структуру оптимального размещения
удается получить, используя методы теории графов (обыкновенных).
В настоящей работе рассматривается постановка, в которой требуется
учесть влияние на эффективность производства такого фактора, как удобре-
ния. В этом случае недостаточно аппарата обыкновенных графов. Матема-
Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица
ISSN 1681–6048 System Research & Information Technologies, 2006, № 3 100
тический аппарат гиперграфов триаду «культура, поле, удобрение» позволя-
ет адекватно представить 3-вершинным ребром, которое является элементом
(ребром) гиперграфа. Напомним, что гиперграфом [1] называется пара
( )EVG ,= , где }{vV = — множество вершин; }{eE = — множество ребер и
всякое ребро ( )rvvve ,...,, 21= степени re =deg есть r-элементное подмно-
жество Vvvv r ⊆},...,,{ 21 .
Использование инструментария гиперграфов возможно при выполне-
нии следующего условия: имеющийся запас удобрений разделен на «пор-
ции», каждая из которых используется полностью для какой-либо пары вида
«культура — поле» из определенного для фиксированной порции перечня
таких пар (в работе [5] этим парам соответствуют ребра 2-дольного графа).
Список всех порций удобрений будем представлять в виде множества вер-
шин — третьей доли.
Для математической формулировки задачи введем определения.
Определение 1. Гиперграф называется l-однородным, если все его реб-
ра Ee∈ имеют одну и ту же степень le =deg .
Определение 2. Гиперграф называется r-дольным, если его множество
вершин V разбито на доли (подмножества) sV , rs ,1= так, что выполняются
два условия : 1) всякая пара вершин из одной доли является несмежной; 2) у
всякого ребра Ee∈ каждая пара вершин evv ∈′′′, принадлежит различным
долям.
Таким образом, математическая модель задачи землепользования в
приведенной постановке базируется на 3-дольном 3-однородном гиперграфе
( )EVVVG ,,, 321= .
Вершинам первой доли },...,,...,,{ 111
2
1
11 mk vvvvV = ) приписан индекс
mk ,1= , соответствующий номерам выращиваемых культур; вершинам вто-
рой доли },...,,...,,{ 222
2
2
12 ni vvvvV = — индекс ni ,1= , соответствующий но-
мерам полей, nm ≤ ; вершинам третьей доли },...,,...,,{ 333
2
3
1
0
3 3nj vvvvV = —
индекс 3,1 nj = , соответствующий порциям удобрений. В условиях ограни-
ченного ресурса удобрений число его порций, как правило, строго меньше
числа полей, т.е. nn <3 . Однако в дальнейшем будем полагать, что вторая
2V и третья 3V доли являются равномощными ( nVV == 32 ). Этого можно
достичь путем пополнения множества 0
3V подмножеством, состоящим из
( )3nn − «пустых» порций удобрения.
Множество ребер }{eE = определяется из следующего содержательно-
го условия: если поле i может быть отведено под культуру k , и при этом
для пары i , k допустимо внести j -ю порцию удобрения, то вершины
3
3
2
2
1
1 ,, VvVvVv jik ∈∈∈ образуют ребро.
При поиске допустимого решения рассматриваемой задачи будем ис-
пользовать такие определения.
Моделирование задачи землепользования на гиперграфах
Системні дослідження та інформаційні технології, 2006, № 3 101
Определение 3. Звездой гиперграфа ( )EVG ,= называется его связная
часть ( )zz EVz ,= , в которой всякая пара ребер zEee ∈′′′, пересекается в од-
ной и той же вершине Vv ∈0 и не пересекается ни в какой другой вершине
0vv ≠ . При этом вершина 0v называется центром звезды z , а число ребер
zE — ее степенью.
Определение 4. Для заданных натуральных чисел kq , mk ,1= таких,
что
nq
m
k
k =∑
=1
, (1)
допустимым покрытием 3-дольного 3-однородного гиперграфа =G
( )EVVV ,,, 321= звездами является всякий его остовный подгиперграф
( )xEVVVx ,,, 321= , состоящий из m компонент связности, каждая из кото-
рых — звезда с центром в одной из вершин первой доли 1V . При этом звезда
с центром 1
1 Vvk ∈ имеет степень, равную числу mkqk ≤≤1, .
Допустимое покрытие гиперграфа G звездами в дальнейшем будем на-
зывать также допустимым решением. Множество всех допустимых решений
(МДР) обозначим ( ) { }xGXX == .
На рис. 1,а показан 14-вершинный 3-дольный 3-однородный гиперграф
( )EVVVG ,,, 321= с долями { }2,11 =V , { }8,7,6,5,4,32 =V , { ,12,11,10,93 =V
}14,13 и множеством ребер { }821 ,,, eeeE …= , где ( )9,3,11 =e , ( )10,5,12 =e ,
( )11,6,13 =e , ( )12,4,24 =e , ( )13,7,25 =e , ( )14,8,26 =e , ( )9,4,17 =e ,
( )13,6,28 =e .
На рис. 1,б для значений 6,3,2 21 ==== nqqm показано допустимое
покрытие звездами гиперграфа на рис. 1 ,а .
Каждому ребру ( ) Evvve jik ∈= 321 ,, гиперграфа ( )EVVVG ,,, 321= припи-
сано число ( )ew — так называемый вес ребра. В контексте содержательного
смысла моделирования этот вес представляет собой тот или иной эффект
а б
Рис. 1. 14-вершинный 3-дольный 3-однородный гиперграф и покрытие его звездами
Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица
ISSN 1681–6048 System Research & Information Technologies, 2006, № 3 102
(экономический, экологический и т.д.) от ожидаемого урожая культуры k ,
засеянной на поле i при условии, что в почву этого поля внесена j-я порция
удобрения.
Весом допустимого покрытия ( )xEVVVx ,,, 321= будем называть сумму
весов всех входящих в него ребер
( ) ( )∑
∈
=
xEe
ewxw .
На МДР ( ) { }xGXX == определена целевая функция (ЦФ) вида
MAXSUM или MINSUM
( ) { }maxmin,extr,extr)( ∈→= xwxF . (2)
Математическая постановка рассмотренной задачи землепользования
состоит в нахождении такого допустимого покрытия гиперграфа звездами
Xx ∈0 , на котором данная ЦФ принимает требуемое экстремальное значе-
ние (min или max).
О ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ЗАДАЧИ ЗЕМЛЕПОЛЬЗОВАНИЯ
НА ГИПЕРГРАФЕ
Рассматривая гиперграф ( )EVG ,= , будем использовать понятие «сочета-
ние», которое означает какое-либо подмножество ( ) EtS ⊆ , состоящее из t
попарно непересекающихся ребер, Et ≤ .
Определение 5. Для )( ln -вершинного l -однородного гиперграфа его
сочетание ( )nS , состоящее из n ребер, будем называть совершенным соче-
танием (СС).
Для n3 -вершинного 3-дольного 3-однородного гиперграфа
( )EVVVG ,,, 321= , { }tvV = , nt ,1= , nVVV === 321 (3)
какое-либо его СС условимся обозначать ( )xEVVVx ,,, 321= , EE x ⊆ .
( ) { }xGXX == — множество всех СС на гиперграфе вида (3).
Под задачей о совершенном сочетании будем понимать задачу нахож-
дения во взвешенном гиперграфе вида (3) такого СС, на котором ЦФ вида
(2) достигает требуемого экстремума.
Примечание 1. Задача о совершенном сочетании на невзвешенном ги-
перграфе описана в работе [7] в комбинаторной постановке под названием
«трехмерное сочетание». Ей присвоено обозначение «3-С», и в определен-
ных выше терминах она формулируется как задача распознавания: содер-
жится ли 3-мерное СС в заданном подмножестве Е декартова произведения
321 VVV ×× долей гиперграфа (3).
В определении 4 задача покрытия звездами (m+2n)-вершинного 3-
дольного 3-однородного гиперграфа
( )EVVVG ,,, 321= , mV =1 , nVV == 32 , nm < (4)
Моделирование задачи землепользования на гиперграфах
Системні дослідження та інформаційні технології, 2006, № 3 103
сформулирована с учетом требования (1).
Эта задача сводится к задаче о СС на гиперграфе вида (3). Алгоритм
1α , реализующий это сведение, состоит из следующих этапов.
1. С учетом (1) для каждого mk ,1= вершине 1
1 Vvk ∈ ставим в соответ-
ствие новое множество { }tk vV = , состоящее из kq вершин tv , перенумеро-
ванных индексом kk NNt ,11 += − , где ∑
=
=
k
r
rk qN
1
, т.е kkk qNN += −1 ,
00 =N .
2. В гиперграфе (4) множество ребер Е разбивается на m подмножеств
( )1
kvE , mk ,1= , каждое из которых состоит из ребер, инцидентных вершине
1
1 Vvk ∈ .
3. Для каждой вершины 1
1 Vvk ∈ , mk ,1= с учетом (1) реализуется этап
kq -кратного «клонирования», полученного на этапе 2 множества ( )1
kvE .
Суть операции клонирования состоит в том, что при фиксированном k для
каждого значения индекса kk NNt ,11 += − строится новое множество ребер
( )tvE , которое получается в результате замены в ребрах ( )∈= 321 ,, jik vvve
( )1
kvE∈ вершины 1
kv на вершину tv .
4. Построенный на базе гиперграфа (4) новый 3n-вершинный
3-дольный 3-однородный гиперграф вида (3) (будем в дальнейшем называть
его производным гиперграфом) образуется путем объединения всех полу-
ченных на этапе 3 новых множеств ребер )( tvE по всем значениям
mk ,...,2,1= и всем индексам kkk NNNt ,...,2,1 11 ++= −− (рис. 2).
Оценим соотношение мощностей множеств ребер E и E исходного
гиперграфа G вида (4) и производного от него гиперграфа G вида (3). Оче-
а б
Рис. 2. 3-дольный 3-однородный )2( nm + -вершинный гиперграф ( )EVVVG ,,, 321=
для 4,2 32 ==== VVnm (а); производный от него гиперграф ( )EVVVG ,,, 321= (б)
Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица
ISSN 1681–6048 System Research & Information Technologies, 2006, № 3 104
видно, что мощность ∑
=
=
m
k
kvE
1
1deg , где vdeg — степень вершины v . Из
алгоритма построения гиперграфа G с учетом (1) вытекают следующие со-
отношения:
∑∑
==
≤=
m
k
k
m
k
kk vqvqE
1
10
1
1 degdeg ,
где k
mk
qq
≤≤
=
1
0 max . Отсюда с учетом равенства (1) получаем верхнюю оценку
для числа ребер в производном гиперграфе G
EnEqE ≤≤ 0 . (5)
Примечание 2. Из определения этапов 1–4 представленного выше ал-
горитма 1α следует, что в процессе его работы каждый элемент гипергра-
фов G и G рассматривается конечное число раз. Отсюда с учетом оценки
(5) можем записать равенство |)(||| EOnE ≤ и сформулировать утверждение
о полиномиальной вычислительной сложности алгоритма 1α построения
гиперграфа G , производного от гиперграфа G .
Пусть для гиперграфа G вида (4) по завершении этапа 4 получен произ-
водный от него гиперграф G вида (3) и на G выделено СС x , а также
пусть с учетом определения этапов 1–4 в СС x известно разбиение множе-
ства вершин tv , nt ,1= первой доли 1V на подмножества { }tk vV = ,
kk NNt ,11 += − , kkk qNN += −1 , mk ,1= . Каждое из подмножеств kV ,
1 k m≤ ≤ представим в виде фиктивного ребра ( )11,...,, −++=
kqtttk vvve ,
11 += −kNt (на рис. 2,б фиктивные ребра ke , 2,1=k отмечены пунктиром).
Применив к этому ребру операцию стягивания [6] в одну вершину kv , полу-
чим звезду, которая с учетом (1) имеет степень kq и состоит из ребер мно-
жества ( )1
kvE . Отсюда с учетом примечания 2 вытекает, что в терминах [7]
является справедливой следующая
Лемма 1. Задача покрытия звездами 3-дольного 3-однородного гипер-
графа G полиномиально сводится к задаче о совершенном сочетании ги-
перграфа G , производного от G .
Рассмотрим вопрос о полиномиальном обратном сведении задачи о
СС к задаче покрытия гиперграфа звездами. Рассмотрим гиперграф
( )EVVVG ,,, 321= вида (4) и производный от него ( )EVVVG ,,, 321= ви-
да (3). Пусть в гиперграфе G выделено допустимое покрытие звездами
( )xEVVVx ,,, 321= . Это покрытие состоит из 1Vm = компонент связности,
каждая из которых представляет собой звезду с центром в некоторой вер-
шине из 1V . Звезду с центром в 1
1 Vvk ∈ представляем в виде подмножества
ребер ( ) EvE k ⊆1 , ( ) { }k
sk evE =1 , kqs ,1= , где параметр kq , mk ≤≤1 , прини-
Моделирование задачи землепользования на гиперграфах
Системні дослідження та інформаційні технології, 2006, № 3 105
мает значение согласно определению 2. По определению этапа 3 в произ-
водном гиперграфе G вершине 1
1 Vvk ∈ соответствует kq множеств ребер
( ) EvE t ⊂ , kk NNt ,11 += − , kkk qNN += −1 . Каждое из этих множеств по-
лучено путем «клонирования» множества ( ) EvE k ⊆1 .
Обозначим 2α алгоритм, который в гиперграфе G строит СС
( )xEVVVx ,,, 321= , соответствующее допустимому покрытию х гиперграфа
G звездами. Алгоритм 2α состоит из этапов k
2α , mk ,...,2,1= , этап k
2α — из
шагов kqs ,...,2,1= . Результатом работы этапа k
2α является выделенное в
гиперграфе G сочетание из kq ребер
{ }k
sk eS = , kqs ,1= , ESk ⊂ .
На шаге { }kqs ,...,2,1∈ в множестве ( )tvE , sNt k += −1 выделяется реб-
ро k
se , представляющее собой «клон» ребра ( )1
k
k
s vEe ∈ в гиперграфе G .
Выделенные по завершении этапа k
2α ребра k
se , kqs ,...,2,1= не пересека-
ются в силу следующих условий:
• Ребра k
se , составляющие звезду ( )1
kvE и соответствующие выделен-
ным ребрам k
se , попарно не пересекаются в вершинах долей 2V и 3V . Сле-
довательно, выделенные ребра k
se не имеют общих вершин в этих долях.
• Ребра, выделенные по завершении этапа k
2α , не пересекаются по
вершинам доли 1V в соответствии с определением шагов этого этапа.
Согласно аналогичным условиям, ребра, принадлежащие различным
сочетаниям
1kS и
2kS , 21 kk ≠ , также не пересекаются.
Таким образом, результатом работы этапа 2
kα является состоящее из
kq ребер сочетание kS . Объединение этих сочетаний ∪
m
k
kS
1=
состоит из
1
m
k
k
n q
=
=∑ ребер, образующих СС гиперграфа G . Следовательно, если G
представляет собой гиперграф, производный от 3-дольного 3-однородного
гиперграфа G , то задача о СС на G полиномиально сводится к задаче по-
крытия гиперграфа G звездами.
Из сказанного выше с учетом примечания 2 и леммы 1 вытекает спра-
ведливость следующей леммы.
Лемма 2. Задача покрытия звездами гиперграфа вида (4) и задача о со-
вершенном сочетании на гиперграфе вида (3) являются взаимно сводимыми
с полиномиальной сложностью.
Для задачи о СС на 3-дольном 3-однородном гиперграфе в работе [7]
предложено обоснование ее NP-полноты в случае, если она формулируется
Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица
ISSN 1681–6048 System Research & Information Technologies, 2006, № 3 106
как проблема распознавания. Тогда с учетом леммы 2 получаем следующую
оценку вычислительной сложности в общепринятых терминах [7].
Теорема 1. Задача распознавания покрытия 3-дольного 3-однородного
гиперграфа звездами является NP-полной, а в оптимизационной постановке
эта задача является NP-трудной.
ОБ УСЛОВИЯХ ПОЛИНОМИАЛЬНОЙ РАЗРЕШИМОСТИ ЗАДАЧИ
ЗЕМЛЕПОЛЬЗОВАНИЯ НА ГИПЕРГРАФЕ
Из теоремы 1 следует, что к настоящему времени отсутствуют полиноми-
альные алгоритмы для задач покрытия гиперграфов звездами (совершенны-
ми сочетаниями). Отсюда очевидна актуальность нахождения полиномиаль-
но разрешимых подклассов этих задач. Условия, определяющие один из
таких полиномиально разрешимых подклассов, состоят в следующем.
1. Математическая постановка задачи о покрытии гиперграфа звездами
рассматривается на множестве всех 3-дольных 3-однородных гиперграфов
( )EVVVG ,,, 321= вида (4), каждый из которых удовлетворяет условию:
если множество E содержит ребро ( )321
0 000
,, jik vvve = , то E содержит все n
ребер вида ( )321
0 ,,
00 jik vvve = , nj ,...,2,1= .
2. Для каждого ребра ( ) Evvve jik ∈= 321 ,, его вес ( )ew определяется ра-
венством вида ( ) ( ) ( )jkbikaew ,, += .
Содержательный смысл условия 2 можно проиллюстрировать в терми-
нах экономико-математической модели землепользования: внесение кон-
кретной порции j удобрения повышает урожай на процент, одинаковый для
рассматриваемой культуры и зависящий только от номера j вносимой пор-
ции.
Покажем, что при выполнении этих двух условий нахождение опти-
мального решения ( )GXx ∈0 сводится к решению двух задач о назначениях
размерности n , откуда вычислительная сложность нахождения 0x ограни-
чена сверху полиномом ( )3nO .
Рассмотрим гиперграф G , удовлетворяющий условиям 1 и 2, и постро-
им производный от него гиперграф ( )EVVVG ,,, 321= . Для гиперграфа G
построим два двудольных графа ( ) ( )( )1
21
1 ,, EVVG = и ( ) ( )( )2
31
2 ,, EVVG = ,
определяемых следующим образом.
Множество ( ) { }11 eE = содержит ребро ( )it vve ,1 = , 1Vvt ∈ , 2Vvi ∈ то-
гда и только тогда, когда гиперграф G содержит хотя бы одно ребро вида
( )jit vvve ,,= . Множество ( ) { }22 eE = содержит ребро ( )jt vve ,2 = , 1Vvt ∈ ,
3Vv j ∈ тогда и только тогда, когда гиперграф G содержит хотя бы одно
ребро вида ( )jit vvve ,,= . Пример приведен на рис. 3.
Моделирование задачи землепользования на гиперграфах
Системні дослідження та інформаційні технології, 2006, № 3 107
Примечание 3. Поскольку в исходном гиперграфе G отсутствуют изо-
лированные вершины, то из сформулированного выше условия 1 следует,
что двудольный граф ( )2G является полным.
Обозначим { }G=Γ1 множество всех 3-дольных гиперграфов, каждый
из которых удовлетворяет представленному выше условию 1; { }G=Γ1 —
множество всех 3-дольных 3-однородных гиперграфов с равномощными
долями, каждый из которых является производным от некоторого гипергра-
фа 1Γ∈G .
Пусть на графах ( )1G и ( )2G выделены соответственно совершенные
паросочетания (СПС) [6] ( )
( )( )1,, 21
1
x
EVVx = и ( )
( )( )2,, 31
2
x
EVVx = . В этих
обозначениях является справедливой следующая лемма.
Лемма 3. Если двудольные графы ( )1G и ( )2G построены для какого-
либо гиперграфа 1Γ∈G , то всякая пара выделенных на них СПС ( )1x и ( )2x
однозначно определяет собой некоторое СС x на гиперграфе G .
Доказательство. Рассмотрим какое-либо ребро ( )
00
,1
0 it vve = из мно-
жества ( )1E , входящее в СПС ( )1x . Из условия 1 и примечания 3 вытекает,
что данный гиперграф G содержит все п ребер вида ( )jit vvve ,,
00
= ,
nj ,...,2,1= . Следовательно, каким бы ни было ребро ( )
00
,2
0 jt vve = в СПС
( )2x , для пары
( ) ( )100
,1
0 xit Evve ∈= , ( ) ( )200
,2
0 xjt Evve ∈= (6)
в гиперграфе G существует ребро ( )
000
,,0 jit vvve = . Отсюда, рассматривая
пару СПС ( )
( )( )1,, 21
1
x
EVVx = , ( )
( )( )2,, 31
2
x
EVVx = , получаем, что объеди-
нение множеств их ребер ( ) ( )( )21 xx
EE ∪ образует n пар пересекающихся
ребер вида (6). Эти п пар вида (6) в гиперграфе G определяют собой п не
пересекающихся ребер, и, следовательно, образуют СС.
Рис. 3. Двудольные графы ( )1G и ( )2G , построенные соответственно для гипергра-
фа G на рис. 2,б
Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица
ISSN 1681–6048 System Research & Information Technologies, 2006, № 3 108
Лемма 3 доказана.
Пусть ( ) { }xGXX == — множество всех СС гиперграфа G ;
( )( ) ( ){ }11 xGX = и ( )( ) ( ){ }22 xGX = — множества всех СПС соответственно на
графах ( )1G и ( )2G . По аналогии с доказательством леммы 3 нетрудно пока-
зать, что является справедливой следующая лемма.
Лемма 4. В условиях леммы 3 всякое СС ( )GXx∈ однозначно опреде-
ляет собой некоторую пару СПС ( ) ( )( )11 GXx ∈ , ( ) ( )( )22 GXx ∈ .
Рассматривая декартово произведение ( )( ) ( )( )21 GXGX × , определим
множество всех пар СПС для пары графов ( )1G и ( )2G .
( ) ( )( ) ( )( ) ( )( ) ( ) ( )( ){ }212121 ,, xxGXGXGGX =×= .
Из лемм 3 и 4 следует, что является справедливой следующая лемма.
Лемма 5. Для всякого гиперграфа 1Γ∈G и соответствующей ему пары
двудольных графов ( )1G и ( )2G существует взаимно однозначное соответст-
вие между множествами ( )GX и ( ) ( )( )21 , GGX .
Рассмотрим СС ( )xEVVVx ,,, 321= и соответствующую ему пару
( )
( )( )1,, 21
1
x
EVVx = и ( )
( )( )2,, 31
2
x
EVVx = . Используя обозначения усло-
вия 2, будем говорить, что в графах ( ) ( )( )1
21
1 ,, EVVG = и ( ) =2G
( )( )2
31 ,, EVV= ребрам ( ) ( )11 , Evve it ∈= и ( ) ( )22 , Evve jt ∈= приписаны веса
соответственно ( ) ( )ikaew ,1 = и ( ) ( )jkbew ,2 = . В этих обозначениях по ана-
логии с (2) на множествах ( )GX , ( )( ) ( )( )21 , GXGX определены ЦФ.
( ) ( ) max→= ∑
∈ xEe
ewxF , (7)
( )( ) ( )
( )
max
1
1
11 →= ∑
∈
x
Ee
ewxF , (8)
( )( ) ( )
( )
max
2
2
22 →= ∑
∈
x
Ee
ewxF . (9)
Из леммы 5 и свойства 2 следует, что ЦФ (7) обладает свойством адди-
тивности [8]
( ) ( )( ) ( )( )21 xFxFxF += ,
где )1(x и )2(x — пара СПС, которая согласно леммам 3–5 определяет СС
x в рассматриваемом гиперграфе G .
Обозначим ( )1
0x и ( )2
0x оптимальные по значению ЦФ (8) и (9) СПС со-
ответственно на графах ( )1G и ( )2G ; 0x — оптимальное по ЦФ (7) СС на
Моделирование задачи землепользования на гиперграфах
Системні дослідження та інформаційні технології, 2006, № 3 109
гиперграфе G . В силу вышеуказанного свойства аддитивности для этих оп-
тимумов выполняется равенство
( )( ) ( )( ) ( )0
2
0
1
0 xFxFxF =+ . (10)
Для нахождения оптимальных СПС на двудольных графах вида ( )1G
или ( )2G существуют достаточно эффективные алгоритмы [9], вычисли-
тельная сложность которых составляет ( )3nO . Отсюда с учетом равенства
(10) и леммы 2 получаем, что является справедливой следующая теорема.
Теорема 2. Задача о покрытии звездами гиперграфов из множества 2Γ
и задача о совершенных сочетаниях на гиперграфах из множества 1Γ разре-
шимы с вычислительной сложностью ( )3nO .
Таким образом, теорема 2 определяет полиномиально разрешимый
подкласс задачи о покрытии гиперграфа звездами и задачи о совершен-
ных сочетаниях на гиперграфах, которые в общем случае являются
NP-трудными.
ЛИТЕРАТУРА
1. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов,
Р.И. Тышкевич. — М.: Наука, 1990. — 384 с.
2. Зыков А.А. Гиперграфы // Успехи математических наук. — 1972. — № 29 (6).
— С. 89–154.
3. Мелихов А.Н., Бернштейн Л.С. Гиперграфы в автоматизации проектирования
дискретных устройств. — Ростов-на-Дону: Изд-во Ростовского ун-та, 1991.
— 248 с.
4. Сергиенко И.В. Математические модели и методы решения задач дискретной
оптимизации. — Киев.: Наук. думка, 1988. — 472 с.
5. Максишко Н.К., Перепелица В.А, Заховалко Т.В. Теоретико-графовая эколого-
экономическая модель задачи землепользования // Вісн. Східноукраїнського
національного ун-ту ім. В.Даля. — 2002. — № 2 (48). — С. 92–100.
6. Зыков А.А. Основы теории графов. — М.: Наука, 1987. — 384 с.
7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. —
М.: Мир, 1982. — 416 с.
8. Математика. Большой энциклопедический словарь. 3-е изд. / Гл. ред.
Ю.В. Прохоров. — М.: Большая российская энциклопедия, 1998. — 848 с.
9. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и
сложность. — М.: Мир, 1985. — 512 с.
Поступила 30.08.2005
|
| id | nasplib_isofts_kiev_ua-123456789-42191 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-07T18:54:35Z |
| publishDate | 2006 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Заховалко, Т.В. Максишко, Н.К. Перепелица, В.А. 2013-03-12T16:11:21Z 2013-03-12T16:11:21Z 2006 Моделирование задачи землепользования на гиперграфах / Т.В. Заховалко, Н.К. Максишко, В.А. Перепелица // Систем. дослідж. та інформ. технології. — 2006. — № 3. — С. 99–109. — Бібліогр.: 9 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42191 519.8 Построена математическая модель задачи землепользования (рационального использования пахотных угодий) с применением аппарата гиперграфов. Проведено обоснование вычислительной сложности задачи, выделен ее полиномиально разрешимый подкласс и предложен соответствующий эффективный алгоритм ее решения. Побудовано математичну модель задачі землекористування (раціонального використання орних угідь) із застосуванням апарату гіперграфів. Проведено обґрунтування обчислювальної складності задачі, виділено її підклас такий, що може бути поліноміально розв’язаний і запропоновано відповідний ефективний алгоритм цього розв’язання. A mathematical model of the land use problem (rational use of arable lands) is built using hypergraph tools. The computational complexity of the problem is grounded, the polinomially solvable subclass is selected, and the proper effective algorithm of the solution is offered. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Математичні методи, моделі, проблеми і технології дослідження складних систем Моделирование задачи землепользования на гиперграфах Моделювання задачі землекористування на гіперграфах Modeling of the land use problem on hypergraphs Article published earlier |
| spellingShingle | Моделирование задачи землепользования на гиперграфах Заховалко, Т.В. Максишко, Н.К. Перепелица, В.А. Математичні методи, моделі, проблеми і технології дослідження складних систем |
| title | Моделирование задачи землепользования на гиперграфах |
| title_alt | Моделювання задачі землекористування на гіперграфах Modeling of the land use problem on hypergraphs |
| title_full | Моделирование задачи землепользования на гиперграфах |
| title_fullStr | Моделирование задачи землепользования на гиперграфах |
| title_full_unstemmed | Моделирование задачи землепользования на гиперграфах |
| title_short | Моделирование задачи землепользования на гиперграфах |
| title_sort | моделирование задачи землепользования на гиперграфах |
| topic | Математичні методи, моделі, проблеми і технології дослідження складних систем |
| topic_facet | Математичні методи, моделі, проблеми і технології дослідження складних систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/42191 |
| work_keys_str_mv | AT zahovalkotv modelirovaniezadačizemlepolʹzovaniânagipergrafah AT maksiškonk modelirovaniezadačizemlepolʹzovaniânagipergrafah AT perepelicava modelirovaniezadačizemlepolʹzovaniânagipergrafah AT zahovalkotv modelûvannâzadačízemlekoristuvannânagípergrafah AT maksiškonk modelûvannâzadačízemlekoristuvannânagípergrafah AT perepelicava modelûvannâzadačízemlekoristuvannânagípergrafah AT zahovalkotv modelingofthelanduseproblemonhypergraphs AT maksiškonk modelingofthelanduseproblemonhypergraphs AT perepelicava modelingofthelanduseproblemonhypergraphs |