Как найти минимальное множество покрывающих цепей графа
Перейти к содержимому

Как найти минимальное множество покрывающих цепей графа

  • автор:

4.7. Эйлеровы циклы и цепи

Считают, что начало теории графов положила задача, предложенная Ейлером. В каких случая конечный граф мо­жно определить циклом без дополнений? Если граф G пред­ставим таким циклом, то он называется эйлеровым графом.

Теорема 4.5 Конечный граф G является эй­леровым графом тогда и только тогда, когда он связан и все степени его вершин четны.

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

Докажем достаточность. Предположим, что необходи­мые условия выполнены. Начнем строить цепь из про­из­вольной вершины a = v0 и будем продолжать ее, переходя от v0 к v1, от v1 к v2 и так далее, последовательно отмечая пройденные ребра. Очевидно, список вершин, начавшись на v0, должен на v0 и закончиться за конечное число шагов. В противном случае приходим к противоречию о связности графа либо, допуская связность, приходим к противоречию о четности степеней всех его вершин.

Если при построении цепи все ребра графа G ока­за­лись отмеченными, то эйлеров цикл построен и этот цикл является эйлеровым графом G. В противном случае на G бу­дут не отмечены некоторые ребра. В силу связности графа G неотмеченные ребра составят связный подграф G. Все сте­пени вершин, этого подграфа четны. Это обусловлено тем, что все вершины, как исходного графа, так и построенного цикла имеют четные степени. На графе G найдется хотя бы одно из неотмеченных ребер, которое инцидентно одной из вершин построенной цепи. Это обусловлено связностью гра­фа G. Обозначим эту вершину b. Повторяя процесс постро­ения цикла из вершины b на подграфе G снова возвра­щаемся в эту же вершину за конечное число шагов.

Обозначим: P(vi,vj) — некоторая цепь из vi в vj. Очеви­дно, объединяя цепи так, что P(a, b)  P(b, b)  P(b, a) мы имеем цикл P(a, a), который мощнее по множеству входя­щих в него ребер, чем P(a, a),

Если цикл P(a, a)  G, то повторим процесс увели­чения мощности цикла P(a, a), включив в него новые ребра, аналогично ранее выполненному процессу. Тогда за конеч­ное число шагов k имеем P k (a, a) = G, что и требовалось.

Ясно, что доказанная теорема определяет также и алгоритм построения эйлерового цикла на графе.

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

Говорят, что множество цепей P1, P2,…, Pn покрывает граф G, если G = P1P2 … Pn и P1P2 … Pn = .

Теорема 4.6 Пусть G — связный граф с k вер­шинами нечетной степени. Тогда минимальное по­кры­тие графа цепями имеет мощность k / 2.

Доказательство. В силу теоремы 4.4 число вершин не­четной степени четно. Следовательно, каждая из k вершин нечетной степени должна быть концом одной из покры­ва­ющих цепей графа. Отсюда с необходимостью следует, что число всех покры­вающих цепей должно быть не менее, чем k / 2. Расширим граф G до эйлерова графа, добавив k / 2 ребер, соединяющих различные пары вершин нечетной степени. Тогда на графе определен единственный эйлеров цикл. Аннулируя ребра, вместе с каждым аннулированным ребром имеем и новую цепь. Тогда число k / 2 является также и достаточным чис­лом цепей, покрывающих граф.

Для ориентированных графов можно получить ана­логичный результат. В частности, имеет место

Теорема 4.7 Для того, чтобы на ориенти­рованном графе G существовал контур, содержащий все дуги G, необходимо и достаточно, чтобы число всех входящих и выходящих дуг было одинаковым в каждой из вершин.

Такой контур называется эйлеровым контуром.

4. Покрытие графа непересекающимися по ребрам цепями

Количество таких цепей равно k/2, где k – количество вершин с нечетными степенями, оно всегда четно.

Если k = 2 , то получается эйлерова цепь.

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

Для преобразования графа в эйлеров граф можно

– продублировать все ребра (дуги) графа, или

– добавить фиктивную вершину и соединить ее ребрами с вершинами, имеющими нечетную степень; таких вершин четное число, поэтому степень введеной вершины будет четной и, следовательно, все вершины будут удовлетворять условиям Эйлера, или

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

Пример. Пусть задан графG(8,13), показанный на рис. 20.8.

Требуется покрыть граф непересекающимися по ребрам цепями.

Введем фиктивную вершину 9 и соединим ее фиктивными ребрами с вершинами 1, 2, 5, 8, имеющими нечетные степени (см. рис. 20.9).

Граф стал эйлеровым.

Первая фаза

Пусть vнач= 9,i= 1,j= 1 (i– формирователь индексов ребер основных циклов,j– формирователь индексов ребер частных циклов, возникающих при построении очередного основного цикла).

    1. Случайно выбирая в каждой попавшейся в маршруте вершине очередное ребро (среди ребер, не имеющих индекса), строим первый основной цикл с началом в вершине 9. Пусть это будет цикл 9p2b3g6j8t9. При строительстве этого цикла частных циклов не образовалось.

Рисунок 20.8

    1. Ребрам построенного основного цикла присвоим индексы, равные значению i= 1 (см. рис. 20.10).

Рисунок 20.9 Рисунок 20.10

    1. Выбираем вершину, принадлежащую построенному циклу и имеющую ребра без индексов. Пусть это будет опять вершина 9.
    2. Полагаем i=i+j= 1 + 1 = 2,j= 1.Строим второй основной цикл с началом в вершине 9.
    3. Пусть построили такой маршрут 9r1a2c4f3d1. Замечаем, что при вершине 1 образовался частный цикл 1a2c4f3d1. Ребрам этого цикла присвоим индексi+j= 2 + 1 = 3 и исключаем их из основного цикла. Переменнойjприсваиваем новое значениеj=j+ 1 =1 + 1 = 2.
    4. Продолжаем строить основной цикл от вершины 1 – 9r1e4h6i5k7m8l5 – замечаем, что образовался второй частный цикл при вершине 5 – 5k7m8l5. Его ребрам присвоим индексi+j= 2 + 2 = 4 и исключаем их из основного цикла, переменнойjприсвоим новое значениеj=j+ 1 = 2 + 1 =3.
    5. Продолжаем строить основной цикл от вершины 5. Получаем 9r1e4h6i5s9. Частных циклов больше не образовалось.
    6. Ребрам полученного основного цикла присвоим индекс, равный i= 2. Все ребра графа имеют индексы. Первая фаза закончена (см. рис. 20.11).

Рисунок 20.11 Вторая фаза 1. Строим эйлеров цикл с началом в вершине 9: 9r21a32c34f33d31e24h26i25k47m48l45s29t18j16g13b12p19 2. Удалим введенную вершину 9 и инцидентные ей ребра. Получим две покрывающие граф цепи, не имеющие общих ребер 1a32c34f33d31e24h26i25k47m48l45 и 8j16g13b12.

Найти минимальное множество покрывающих цепей графа G

Author24 — интернет-сервис помощи студентам

Найти радиус и диаметр, минимальное множество покрывающих цепей графа G
Здравствуйте :friends:. Не мог бы кто-то по графам помочь? Задание: Найти радиус и диаметр.

Найти максимальное множество вершин графа
Еще раз обращаюсь с просьбой о помощи!! Скорее всего последний раз в этом году))) Задача такова.

Найти минимальное подмножество вершин взвешенного графа
Задача о размещении бензоколонок Дан взвешенный граф. Найти такое минимальное подмножество.

645 / 310 / 34
Регистрация: 31.05.2019
Сообщений: 2,343
Ввел обозначения (если нужно)
Изображения

Эксперт по математике/физике

4166 / 3038 / 914
Регистрация: 19.11.2012
Сообщений: 6,182

ЦитатаСообщение от Sneykas Посмотреть сообщение

покрывающих цепей

Вводим дополнительную вершину, назовем ее v. Соединим v с вершинами нечетной степени (это вершины 234567). Строим эйлеров цикл, начинающийся и заканчивающийся в вершине v. После этого удаляем v вместе с ребрами. То, что останется и будет искомым множеством цепей.

645 / 310 / 34
Регистрация: 31.05.2019
Сообщений: 2,343

ЦитатаСообщение от kabenyuk Посмотреть сообщение

Строим эйлеров цикл, начинающийся и заканчивающийся в вершине v

Вот так получилось (первый рисунок)

ЦитатаСообщение от kabenyuk Посмотреть сообщение

После этого удаляем v вместе с ребрами. То, что останется и будет искомым множеством цепей.
Правильно сделал? ( 2 рисунок )
Изображения

Эксперт по математике/физике

4166 / 3038 / 914
Регистрация: 19.11.2012
Сообщений: 6,182

ЦитатаСообщение от Sneykas Посмотреть сообщение

Правильно сделал?

Нет, неправильно. В моем тексте про вершину v. Соединим (надо понимать одним ребром) v с каждой вершиной нечетной степени (это вершины 234567). То есть из v проведем 6 (шесть!) ребер. В новом графе строим эйлеров цикл. И т.д.
Попробуйте еще раз.

645 / 310 / 34
Регистрация: 31.05.2019
Сообщений: 2,343

ЦитатаСообщение от kabenyuk Посмотреть сообщение

В новом графе строим эйлеров цикл. И т.д.
Попробуйте еще раз.

Соединил точки ( 1 рисунок )

Получилось зелёным цветом ( второй рисунок ) — вышел из вершины v в точку 2->3->1->4->5->7->8->6->5 ( ну а дальше уже по веткам пошел, которые идут из вершины v к точкам )

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

Изображения

Эксперт по математике/физике

4166 / 3038 / 914
Регистрация: 19.11.2012
Сообщений: 6,182

ЦитатаСообщение от Sneykas Посмотреть сообщение

Это как? Аккуратнее, пожалуйста. Вершина v и новые ребра — полноправные участники — не обижайте их.
645 / 310 / 34
Регистрация: 31.05.2019
Сообщений: 2,343

ЦитатаСообщение от kabenyuk Посмотреть сообщение

Аккуратнее, пожалуйста. Вершина v и новые ребра — полноправные участники — не обижайте их.

Добавлено через 6 минут

ЦитатаСообщение от kabenyuk Посмотреть сообщение

В новом графе строим эйлеров цикл. И т.д.

ЦитатаСообщение от kabenyuk Посмотреть сообщение

После этого удаляем v вместе с ребрами. То, что останется и будет искомым множеством цепей.
У нас получается, что ничего не осталось

Эксперт по математике/физике

4166 / 3038 / 914
Регистрация: 19.11.2012
Сообщений: 6,182

ЦитатаСообщение от Sneykas Посмотреть сообщение

ничего не осталось
Вот и меня слова кончились.
645 / 310 / 34
Регистрация: 31.05.2019
Сообщений: 2,343

ЦитатаСообщение от kabenyuk Посмотреть сообщение

Вот и меня слова кончились.

Скажите, это хоть правильно или нет?

ЦитатаСообщение от Sneykas Посмотреть сообщение

Найти минимальное множество покрывающих цепей графа G
Ответом на вопросом получается будет, что у нас нету множества?
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Найти минимальное расстояние между вершинами 1 и N графа
Dev-C++ не компилирует программу Решил написать алгоритм 0,1-BFS void BFS(int** MasList, int**.

Найти минимальное расстояние между вершинами графа
Мне нужно найти минимальное расстояние между вершинами. Задается кол-во вершин, к примеру, 3. Потом.

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

Поиск цепей графа по матрице смежности
Граф задан матрицей смежности C размерностью nxn, необходимо написать функцию, которая возвращает.

Или воспользуйтесь поиском по форуму:

Исследование сложности задачи покрытия графа цепями с интервальными данными Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — А. М. Кочкаров, К. А. Кульчицкий, Ш. М. Курджиев, А. В. Николаев

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — А. М. Кочкаров, К. А. Кульчицкий, Ш. М. Курджиев, А. В. Николаев

О вычислительной сложности интервальных задач на графах
Интервальные задачи об остовных деревьях с топологическим критерием
Исследование многокритериальной постановки теоретико-графовой задачи сегментации на двудольном графе
Принятие решений в дискретных задачах оптимизации на графах с нечеткими весами
Задача инвестора с интервальными данными
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

RESEARCH OF COMPLEXITY OF THE PROBLEM OF THE COVERING THE GRAPH BY CIRCUITS WITH THE INTERVAL DATA

The article is devoted to research of problems with such kind of uncertainty, as interval the initial data. For research of complexity of such problems their data to 2criterion are offered to problems. NP-completeness 2criterion problems of a covering the graph is proved by circuits from what NP-completeness and consequently and intractability to a problem equivalent to it with the interval data follows.

Текст научной работы на тему «Исследование сложности задачи покрытия графа цепями с интервальными данными»

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

А.М. Кочкаров, К.А. Кульчицкий, Ш.М. Курджиев, А.В. Николаев

RESEARCH OF COMPLEXITY OF THE PROBLEM OF THE COVERING THE GRAPH BY CIRCUITS WITH THE INTERVAL DATA

A.M. Kochkarov, K.A. Kulchitskiy, S.M. Kurdzhiev, A.V. Nikolaev

The article is devoted to research of problems with such kind of uncertainty, as interval the initial data. For research of complexity of such problems their data to 2- criterion are offered to problems. NP-completeness 2- criterion problems of a covering the graph is proved by circuits from what NP-completeness and consequently and intractability to a problem equivalent to it with the interval data follows.

Статья посвящена исследованию задач с таким видом неопределенности, как интервальные исходные данны/е. Для исследования сложности таких задач предлагается сведение их к 2-критериальным задачам. До-казы/вается NP-полнота 2-критерильной задачи покрытия графа цепями, из чего вытекает NP-полнота, а следовательно и трудно-решаемость эквивалентной ей задаче с интервальными данны1ми.

1. Общая формулировка векторных задач покрытия графа цепями

Пусть задан n -вершинный граф G = (V, E), каждому ребру e е E которого приписаны N весов

Граф такого вида называется N -взвешенным. Задано также множество типов (покрывающих) цепей (МТЦ), обозначаемое через H = i

Покрытием графа G цепями заданной длины назовем такой остовный подграф х = (V, Ex ), Ex i E, у которого каждая компонента связности представляет собой некоторую h -цепь, где h е H. Число ht е H будем называть типом цепи, подразумевая при этом, что значения ht упорядочены по возрастанию. Всякое такое покрытие принято называть допустимым решением задачи о покрытии графа G цепями для заданного множества H . Множество всех допустимых решений (МДР) обозначим через X = <х). Для оценки качества допустимых решений на множестве X определена ВЦФ

F (x)=(Fi (x)F (x). Fn (х)), (1)

критерии которой имеют вид:

Fv (xextr, v = 1. N, (2)

Критерии указанной ВЦФ (1)-(2), как правило, минимизируются (максимизируются). В общем случае решением индивидуальной [1] дискретной многокритериальной задачи является нахождение того или иного множества альтернатив (МА) [2].

В теории принятия решений в качестве МА принято рассматривать паретовское

множество (ПМ) X, состоящее из всех па-рето-оптимальных решений из [3, 4] МДР

X . ПМ X е X рассматривается в качестве МА в том случае, когда для ЛПР структура

плана х е X имеет столь же существенное значение, как и значение показателей Р(х), V = 1. N.

На практике в качестве МА рассматривают полное множество альтернатив

(ПМА) Xи. Оно определятся как подмножество X0 е X, если его мощность X 0| минимальна при выполнении равенства

где Р(X*)= (VX*с X). По своему содержанию ПМА — это наиболее экономное множество представителей ПМ в критериальном пространстве. Иначе, если

для пары решений х’, х» е X, выполняется равенство Р (х») = р (х » ), то х » и х » считаются эквивалентными и выбирается из них только одно.

2. Задачи с интервальными данными

Будем считать, что термин «интервальная задача покрытия графа цепями» будет означать сформулированную выше постановку задачи о покрытии графа цепями при следующем условии: для каждого ребра е е Е точное значение веса w(e), вообще говоря, неизвестно, в силу чего оно задается в виде интервала w(e)=[w1 (е), w2 (е)]. Уточним, что под интервалом подразумевается замкнутый отрезок на вещественной прямой Я . Таким образом, в исходных данных задачи относительно веса w(e) известно лишь, что его значение не меньше ниж-

ней границы w1 (е) и не превосходит верхней границы w2 (е).

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

В общем случае интервальная экстремальная задача на графах формулируется следующим образом. Дан п -вершинный граф G = (V, Е), в котором каждому ребру е е Е приписан интервальный вес w(e), заданный в виде отрезка

Согласно определению операции сложения интервалов [5, 6] получим значение ИЦФ

где wi (х) = ^ wi (е), I = 1,2. Требуется

найти такой элемент х0 е X, на котором значение ИЦФ (3)-(4) достигает требуемого экстремума, например, минимума.

В случае интервальных весов нахождение оптимума наталкивается на проблему выбора наиболее целесообразного решения из множества несравнимых альтернатив. В связи с этим, для определения подмножества решений необходимо ввести отношения предпочтения, эквивалентности и несравнимости [2,3,4].

Определение 1. Решение х1, предпочтительней решения х2 или, другими

словами, решение х2 доминируется решением х1, если wi (х1) < wi (х2), i = 1,2, при

этом хотя бы одно неравенство должно быть строгим. Эту предпочтительность обозначим через х1 • х2.

Определение 2. Решение х1, х2 е X называется несравнимым, когда имеет место строгое вложение интервалов, т.е. выполняется: либо w(x1 w(x2), либо w(x2) ^ w(x1). Несравнимость пары х1 и х2 обозначаем через х1 » х2.

Определение 3. Решения х1, х2 е X эквивалентны, если совпадают соответствующие им интервалы w(x2) = w(x1). Обозначим эквивалентность этих решений как х1 = х2 .

Введенные на МДР X бинарные отношения предпочтения и несравнимости

порождают ПМ X ^ X .

В качестве искомого решения интервальной задачи рассматривается как ПМ X,

Примечание 1. Введение указанных бинарных отношений порядка •, » и ° на МДР X диктуется содержательной постановкой задачи. При этом отношения порядка, представленные в определениях 1-3, порождают ПМ меньшей мощности, нежели отношения порядка, предлагаемые в работах [7, 8].

Решение интервальных задач является многоэтапным процессом. Вначале определяется состав критериев, порождаемых ИЦФ вида (3)-(4), после чего находится множество векторно-несравнимых альтернатив [9] X. На заключительном этапе с помощью процедур теории выбора и принятия

решений [2, 9] из X выбирается искомый «компромиссный оптимум» х0.

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

тимум» х0 приходится выбирать из множества несравнимых альтернатив X . Наличие в таком множестве хотя бы пары несравнимых по значению ИЦФ (3)-(4) решений означает, что исходной интервальной задаче присуща неопределенность функции цели.

3. Сведение интервальной задачи о цепях к 2-критеральной задаче

Сформулированная выше интервальная задача сводится к задаче многокритериальной оптимизации с тем же множеством допустимых решений X и векторной целевой функцией ВЦФ вида

F (х) = (Fj (х), F2 (х)), (5)

F (х) = ^ wj (х) ® min , (6)

d (е)= w2 (е)- w1 (е). (8)

Определение 4. Решение х е X называется ПО для задачи с ВЦФ (5)-(7), если не

существует х е X

v\ ‘ ^ ‘, при этом хотя бы одно неравенство является строгим.

При исследовании задачи с ВЦФ (5)-(8) будем учитывать справедливость следующих утверждений.

Лемма 1. Пусть на множестве допустимых решений X = задачи векторной оптимизации с минимизируемыми критериями ВЦФ (5)-(7) порождает ПМ X, а ВЦФ

где С — некоторая константа, порождает ПМ Xc. Тогда справедливо равенство

Лемма 2. ПМ задачи векторной оптимизации на п -вершинном графе G = (V, Е) с минимизируемыми критериями вида (4) и вида (6)-(7) совпадают, если

для каждого решения х е X мощность множества ребер \EX \ = const.

Теорема 1. ПМ задач с ИЦФ (3)-(4) и ВЦФ(5)-(8) совпадают.

Доказательство. Поскольку определение ПО задач с ИЦФ (3)-(4) и с ВЦФ (5)-(8) эквивалентны, то ПМ указанных задач совпадают. Далее, согласно лемме 2, получаем, что ПМ задач с критериями (6)-(8) и (3)-(4) также совпадают. Отсюда следует утверждение теоремы.

Таким образом, согласно теоремы 1, при исследовании ПМ интервальной задачи можно использовать утверждения, полученные относительно 2-критериальной задачи с весовыми критериями вида (6)-(8).

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

К настоящему времени отсутствуют достаточно эффективные методы решения следующей проблемы распознавания. Для данного n -вершинного графа G и заданного МТЦ H е требуется установить, является ли пустым МДР X = X(G) соответствующей задачи покрытия графа цепями. Для того, чтобы убедиться в том, что эта проблема трудна, достаточно рассмотреть такие случаи, когда H = Hх = и H = H 2 = . В случае H = H1 получаем NP -полную задачу, эквивалентную известной задаче о 3-сочетаниях, а в случае H = H2 получаем NP -полную задачу распознавания свойства гамильтоновости графа [1]. Вместе с этим случай H = H 0 = определяет собой полиномиально разрешимую задачу о совершенном паросочетании [3, 11].

В дополнение к сформулированным выше утверждениям заметим, что в общем случае отсутствуют точные формулы вычисления максимальной мощности ПМА, ПМ и МДР. Эти формулы известны лишь в частных случаях, когда множество H состоит из единственного элемента h1 = 2 или

Ь = п : в случае ^ = 2 максимальная мощность множества совершенных паросочета-ний имеет, как указано выше, вид:

Ь = п , максимальная мощность множества гамильтоновых цепей равна: |Х| = ^ (п —1)|.

Причем указанные максимальные мощности относятся к ПМ и ПМА [2, 3].

Arn = n(n — 1). (n — r +1) =

В дальнейшем рассматриваем только случай, когда п кратно г , используя обозначения

Введем формулу количества |Х|

всех допустимых покрытий полного п -вершинного графа h -цепями. Считаем, что вершины V е V данного графа G = (V, Е) перенумерованы индексами 1,2. п. Это позволит представить каждую цепь h в G в виде последовательности Ь = /2. 1п ]. При этом говорим, что цепь Ь покрывает вершины 11,12. 1п.

Если некоторое покрытие х = (V, Ех ) е X представлять в виде мно-

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

жества, состоящего из h -цепей, количество которых равно q, то минимальный элемент какой-либо цепи называем индексом этой цепи.

Для обоснования точной формулы вычисления мощности МДР X определим

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

Утверждение 1. Если для двух покрытий х1з х2 е X не совпадают соответствующие им последовательности индексов цепей, то покрытия х1 , х2 являются различными.

В дальнейшем для перечисления допустимых покрытий из X используем следующий принцип представления цепей (ППЦ). Первой цепью всегда называем ту цепь, которая содержит элемент /1 = 1; второй называем всегда такую цепь, которая содержит минимальный элемент из подмножества всех вершин, не покрытых первой цепью. С помощью этого ППЦ определяется третья, четвертая и т.д. цепи, рассматриваемого покрытия X.

Согласно представленного ППЦ при выборе первой цепи фиксируем первую вершину /1 = 1; остальные вершины, покрываемые этой цепью, с учетом их перестановок в цепях, можем выбрать числом способов, равным Л’—1 . При выборе второй цепи

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

числом способов ЛП—^ к.

номер в подмножестве п — кк вершин, которые остались непокрытыми уже выбранными к цепями. Тогда остальные (к — 1) вершин (к +1) -ой цепи (с учетом их перестановок) можем выбрать числом способов

ЛкП-\— кк. Таким образом, при выполнении условия (11), первые q — 1 цепей можем выбрать числом способов, равным

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

В формуле (13) множитель 1/2 появляется в силу того, что цепи вида [1,2. к — 1,к] и [к,к —1. 2,1] представляют собой одну и ту же цепь.

Таким образом, с учетом (10)-(13), количество X всех допустимых покрытий полного п -вершинного графа к -цепями вычисляется с помощью следующей формулы:

Введем обозначения: Mn = (g) -множество всех n -вершинных графов; 11N (H )= maxi X (G, H ) — максимальная

мощность МДР задачи покрытия n -вершинных графов цепями из МТЦ H; 1 n (h) — максимальная мощность МДР задач

покрытия n -вершинных графов h -вершинными цепями. В дальнейшем воспользуемся тем, что при пополнении множества E данного графа G = (V, E) новыми

ребрами мощность МДР |X(G, H) может

только увеличиться. Отсюда с учетом (14) вытекает, что для вычисления значения 1n (H ) достаточно получить формулу мощ-

ности МДР для случая, когда G является полным графом. Справедлива

Теорема 2. Для всяких п > 2 и h > 2 таких, что п кратно h, максимальная

мощность МДР ¡1 п (h) = П[ п , , где

Примечание 2. Теорема 2 обобщает известную теорему вычисления количества совершенных паросочетаний в n -вершинном графе с четным числом вершин: в полном графе с четным числом вершин П = 2q количество всех паросочетаний

равно -. В случае h = П, q = 1 из

теоремы 2 получаем формулу вычисления количества всех гамильтоновых цепей в

полном n -вершинном графе: ¡1 n (h) = n!

Для фиксированного МТЦ

F (x)=(F (x), F2 (x). Fn (x)), (15) состоящей из критериев вида MINSUM

Fv (x )= 2 Wv (e)® min, (16)

Здесь термин «N -взвешенный граф» означает, что каждому ребру е е Е, приписаны N -весов wv (е) > 0, V = 1, N. Под решением задач X (Н) подразумевается нахождение и представление в явном виде ПМА.

Иными словами, проблема состоит в построении достаточно эффективного алгоритма, гарантирующего нахождение таких решений. Остановимся на проблеме оценки вычислительной сложности нахождения ПМА для тех или иных задач X (Н) и условимся, что в случае, если Н является одноэлементным множеством, т.е., состоит из единственного элемента h е, то вместо обозначения X (Н) используем обозначение X (к ).

Обозначим через ~п (к, N) и (^ ^ (~п (к) и (h)) максимальные мощности ПМ и ПМА для N -критериальной задачи X (к) с ВЦФ (13)-(15) (интервальной задачи X (к)) на N -взвешенных графах. Для вычисления ~п (к, N) и (^ N) докажем ряд вспомогательных утверждений, для чего сформулируем необходимые определения.

Рассматривая N -критериальную задачу X (Н), называем ее полной, если для п -вершинного графа G = (V, Е), можно указать такие веса wv (е), V = 1, N для всех

его ребер е е Е , при которых выполняются равенства

Из определения ПМ X и ПМА X0 вытекает, что является справедливой следующая

Лемма 3. Для всякой индивидуальной задачи X(Н) с ВЦФ (15)-(17) выполняется равенство мощностей X0| = .

Для какой-либо задачи X (Н) с ВЦФ (15)-(17) рассмотрим некоторую задачу, у которой новая (расширенная) ВЦФ определяет на прежнем МДР X другие множества альтернатив МА. Возникает вопрос о том, как соотносятся «старые» и «новые» МА. С учетом того, что добавление новых критериев не изменяет значение «старых» критериев

(16)-(17) на всех элементах х е X, справедлива

Лемма 4. При любом N > 2 для всякой индивидуальной задачи с ВЦФ (15)-(17) добавление новых критериев к этой ВЦФ

либо оставит ПМ X и ПМА X0 неизменными, либо пополнит их новыми альтернативами.

Рассмотрим случай 1-элементных МТЦ. Для этого случая справедлива

Теорема 3. Всякая задача

7(к),к е является полной, если ее ВЦФ (15) содержит не менее двух критериев вида МШиМ (16).

Теоремы 2 и 3 позволяют представить формулу вычисления максимальных мощностей ПМ и ПМА для многокритериальной задачи 7 (к). Непосредственно из теорем 2 и 3 вытекает, что, с учетом обозначения (11) является справедливой следующая

Теорема 4. Если задача 7 (к) содержит не менее двух критериев вида МШБиМ, то для всякой тройки N > 2, п > 2, к > 2, п кратно к , максимальная мощность ПМ и ПМА вычисляется по формуле:

Примечание 3. Теоремы 3 и 4 доказаны для общего случая взвешивания ребер графов G е Мп. Однако, представленное выше сведение с ИЦФ (3)-(4) к 2-критериальной задаче с ВЦФ (5)-(8) представляет такое значение весов w1 (е), w2 (е) ребер исходного интервально взвешенного графа, для которых, по необходимости, выполняются неравенства

Теорема 5. Интервальные задачи 7 (Н) с ЦФ вида (3)-(4) являются полными.

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.

2. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных

задач. — М.: Наука, 1982. — 256 с.

3. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. — 1994. — Т. 6. -Вып. 1. — С. 3-33.

4. Кини Р.Л., Райфа X Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981. — 420 с.

5. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. — M.: Мир, 1987. -542 с.

6. Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального анализа. — Новосибирск: Наука, Сибирское отделение, 1986. -590 с.

7. Демченко А.И. Синтез транспортных сетей в условиях неопределенности исходной информации // Труды семинара по интервальной математике. — 1990. — C. 10-16.

8. Claudio D.M., Franciosi B. T. Domain Approach to Interval Mathematics. // International conference on Interval and Stochastic Methods in Science and Engineering (Interval-92). — 1992 № 2. — P. 13-17.

9. Ларичев О.И. Наука и искусство принятия решения. -М.: Наука, 1979. — 200 с.

10. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. — 323 с.

11. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985. — 512 с.

Кочкаров Ахмат Магомедович, доктор физико-математических наук, профессор, заведующий кафедрой математики Карачаево-Черкесской государственной технологической академии. Сфера научных интересов — теория графов, фрактальные графы.

Кульчицкий Константин Алексеевич, аспирант. Сфера научных интересов — теория графов и ее приложения.

Курджиев Шакман Магомедович, ассистент кафедры математики Карачаево-Черкесской государственной технологической академии. Сфера научных интересов — теория графов и ее приложения.

Николаев Александр Викторович, аспирант. Сфера научных интересов — теория графов и ее приложения.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *