Итоги выполнения НИР «Оптимальные реконструкции графов» Ответственный исполнитель: Гавриков А. В. Научный руководитель: Салий В.Н.

Общая постановка задачи Пусть К – некоторый класс графов, а G – граф, не принадлежащий К.* Требуется произвести те или иные изменения в структуре графа G, чтобы полученный граф G / оказался К-графом. В качестве допустимых реконструкций данного графа обычно рассматриваются следующие: 1) отождествление некоторых вершин графа; 2) ориентация ребер неориентированного графа; 3) переориентация дуг орграфа; 4) добавление новых дуг (ребер); 5) удаление некоторых дуг (ребер). * Салий В. Н. Оптимальные реконструкции графов // В кн.: Современные проблемы дифференциальной геометрии и общей алгебры. – Саратов; Изд-во Сарат. ун-та, 2008,

Цель НИР 1. Дан произвольный орграф. Получить эйлеров орграф методом добавления, переориентации, удаления минимального числа дуг. 2. Дан произвольный орграф. Получить сильно связный орграф методом добавления минимального числа дуг, методом переориентации минимального числа дуг; из заданного сильно связного графа удалить максимальное число дуг, не нарушая сильной связности исходного орграфа. 3. Получить описание минимальных расширений цепей и циклов, имеющих вершины разного типа.

Научный задел. Публикации 1. Гавриков А.В. Оптимальная переориентация дуг орграфа, приводящая к эйлерову орграфу / В кн.: Наука и образование.- Бийск: БПГУ, 2009, С Работа победила в Открытом конкурсе на лучшую студенческую научную работу 2009 года и награждена медалью и дипломом Министерства образования и науки РФ. 2. Гавриков А. В. Оптимальная квазиэйлерова реконструкция орграфа путем удаления дуг // В кн.: Научные исследования студентов Саратовского государственного университета: Материалы итог. студ. науч. конф. – Саратов: Изд-во Сарат. ун-та, – С Гавриков А. В. Оптимальная эйлерова реконструкция орграфа путем добавления дуг // В кн.: Компьютерные науки и информационные технологии: Материалы науч. конф. ­– Саратов: Изд-во Сарат. ун-та, ­--- С Кадушкина А.С. Минимальные сильно связные реконструкции ориентированных графов / В кн.: Компьютерные науки и информационные технологии.- Саратов: СГУ, 2010, С Работа удостоена стипендии Газпрома РФ. 5. Бондаренко П.П. Минимальные расширения для цепей с вершинами двух типов / В кн.: Компьютерные науки и информационные технологии.- Саратов: СГУ, 2010, С

Научный задел. Программы для ЭВМ Получены свидетельства РОСПАТЕНТа РФ о государственной регистрации программ для ЭВМ: 1. Гавриков А.В. Оптимальные эйлеровы реконструкции ориентированных графов. Свидетельство о государственной регистрации программы для ЭВМ , зарегистрировано в Реестре программ для ЭВМ 30 сентября 2010 г. 2. Кадушкина А.С. Нахождение минимальной сильно связной реконструкции для связных ориентированных графов. Свидетельство о государственной регистрации программы для ЭВМ , зарегистрировано в Реестре программ для ЭВМ 30 сентября 2010 г. 3. Абросимов М.Б., Бондаренко П.П. Исследование минимальных вершинных и реберных 1-расширений для цепей с вершинами двух типов. Свидетельство о государственной регистрации программы для ЭВМ , зарегистрировано в Реестре программ для ЭВМ 30 сентября 2010 г.

Результаты в ходе выполнения НИР. Научные публикации. В печать сданы следующие работы: 1. Гавриков А.В. Оптимальные эйлеровы реконструкции ориентированных графов (принято к опубликованию в журнале «Известия Саратовского университета. Серия Математика. Механика. Информатика», входящем в список ВАК) 2. Кадушкина А.С. Оптимальные сильно связные реконструкции ориентированных графов (принято к опубликованию в сборнике «Научные исследования студентов Саратовского государственного университета») 3. Бондаренко П.П., Абросимов М.Б. Минимальные расширения цепей и циклов с вершинами двух типов (представлено в журнал «Прикладная дискретная математика». Рукопись также направлена на депонирование в ВИНИТИ РАН)

Результаты в ходе выполнения НИР. Программы для ЭВМ. 1. Гавриков А.В. Алгоритмы оптимальных эйлеровых реконструкций орграфов. Программа написана на языке Java2 Standard Edition. Протестирована при помощи JUnit Framework. 2. Кадушкина А. С. Оптимальные сильно связные реконструкции ориентированных графов. Программа написана на языке С#.

Цель работы Целью работы является разработка, реализация и тестирование полиномиальных алгоритмов для рассматриваемых задач. Рассматриваются следующие задачи: 1. Дан произвольный связный орграф, необходимо методом переориентации минимального количества дуг сделать его эйлеровым. Решение задачи анонсировано в [3]. 2. Дан произвольный орграф, необходимо методом добавления минимального количества дуг сделать его эйлеровым. Решение задачи анонсировано в [5]. 3. Дан произвольный орграф, необходимо методом удаления минимального количества дуг сделать его квазиэйлеровым. Решение задачи анонсировано в [4].

Основные определения Ориентированным графом (или, для краткости, орграфом) называется пара G = (V, α), где V – конечное непустое множество (вершины орграфа), а α V V отношение на множестве V. Путем в орграфе называют последовательность дуг (v 1, v 2 ), (v 2, v 3 ), …, (v r - 1, v r ), где (v i, v i+1 ) α, 1 i r – 1, и никакая дуга не встречается более одного раза. Длиной пути называется количество входящих в него дуг. Путь, в котором встречаются все дуги орграфа, называется эйлеровым. Орграф, в котором существует эйлеров путь с совпадающими начальной и конечной вершинами, называется эйлеровым. Степенью исхода вершины v назовем число d + (v) дуг орграфа G, имеющих своим началом v, т. е. d + (v ) := | α(v)|. Степенью захода вершины v назовем число d - (v) дуг орграфа G, имеющих своим концом v, т. е. d - (v ) := | α -1 (v )|. Орграф, у которого каждая компонента связности является эйлеровым орграфом, назовем квазиэйлеровым.

Транспортная сеть Транспортной сетью назовем орграф G = (V, α ) с источником s V и стоком t V, где дуги (u, v ) α имеют пропускную способность c(u, v ) и стоимость cost (u, v ). Потоком в транспортной сети назовем функцию flow: α R, удовлетворяющую следующим условиям: 1) Ограничение, связанное с пропускной способностью: flow (u, v ) c(u, v). 2) Антисимметричность: flow (u, v ) = -flow (v, u ). 3) Сохранение потока: v V flow (u, v ) = 0 для всех u V – {s, t }. Величина потока |flow| определяется как сумма v V flow (s, v ). Максимальным потоком назовем поток максимальной величины. Стоимостью потока через дугу назовем произведение потока и цены этой дуги. Стоимостью потока назовем сумму стоимостей потоков в дугах этой транспортной сети, а именно величину u,v V flow (u, v ) * cost (u, v ). Максимальной потоком минимальной стоимости назовем такой максимальный поток, стоимость которого меньше стоимости любого другого максимального потока. Единичной транспортной сетью назовем транспортную сеть, в которой пропускная способность каждой дуге каждой дуги с(u, v) составляет 1.

Оптимальная эйлерова реконструкция орграфов методом переориентации дуг Постановка задачи. Дан произвольный орграф G = (V, α). Необходимо переориентировать минимальное количество дуг так, чтобы орграф стал эйлеровым. Критерий существования решения. Связный орграф допускает эйлерову реконструкцию методом переориентации дуг тогда и только тогда, когда для любой его вершины v V число d + (v) - d - (v) четно.

Способ переориентации дуг Балансом вершины v назовем число bal (v) = (d + (v) – d - (v)) / 2. Вершину будем называть положительной, отрицательной или нулевой в зависимости от соответствующего свойства ее баланса. Возьмем произвольный путь из положительной вершиной v в отрицательную вершиной u и переориентируем все дуги этого пути. После данного действия bal(v) уменьшится на 1, bal(u) увеличиться на 1, а баланс всех промежуточных вершин останется неизменным. Опираясь на вышеизложенные рассуждения, рассмотрим следующий способ переориентации дуг орграфа: пока в орграфе существуют ненулевые вершины, будем переориентировать пути, идущие от вершин с положительным балансом к вершинам с отрицательным балансом. Назовем такой способ - переориентация по принципу путей (или, для краткости, ППП).

Теорема Дуги в способе ППП можно истолковывать как дуги в единичной транспортной сети, насыщенные максимальным потоком: δ = {(u, v) α : flow (u, v ) = 1}. При этом воспринимая s begin, t end, (u, v) ППП (u, v) δ.

Алгоритм 1. Преобразуем орграф в транспортную сеть - Придаем каждой дуге (u, v ) α цену cost (u, v ) = 1 и c(u, v ) = 1. - Добавляем к орграфу G = (V, α ) новые вершины: источник s и сток t. - Для каждой вершины v V, такой что d + (v ) > d - (v ) добавляем | bal (v ) | дуг (s, v ) c пропускной способностью c (s, v ) = 1 и cost (s, v) = 1. - Для каждой вершины v V, такой что d + (v ) < d - (v ) добавляем | bal (v ) | дуг (v, t ) c пропускной способностью c (v, t ) = 1 и cost (v, t ) = 1. 2.Находим максимальный поток минимальной стоимости между источником s и стоком t. Метод поиска описан в [5]. 3.Дуги, попавшие в поток, удаляем из исходного орграфа. Полученный орграф является квазиэйлеровым. Общее число удаленных дуг будет равно u,v V cost (u, v ) * flow (u, v ) – 2 * k.

Асимптотическая сложность алгоритма 1 Время, затраченное на выполнение пунктов 1, 3 алгоритма не превосходит O(n 2 ), где n – количество вершин в исходном орграфе. В итоге, время алгоритма равно времени поиска максимального потока минимальной стоимости. На данный момент известна реализация за O(n 4 ).

Оптимальная эйлерова реконструкция орграфов методом добавления дуг Постановка задачи Дан произвольный орграф G = (V, α). Необходимо добавить минимальное количество дуг так, чтобы орграф стал эйлеровым. Критерий существования решения. Для любого орграфа решения задачи существует.

Способ добавления дуг Балансом вершины v назовем число bal (v ) = d + (v ) – d - (v ). Вершину будем называть положительной, отрицательной или нулевой в зависимости от соответствующего свойства ее баланса. Возьмем произвольный путь из отрицательной вершины v в положительную вершину u в дополнении орграфа и добавим дуги этого пути в исходный орграф. После данного действия bal (v ) увеличится на 1, bal (u ) уменьшится на 1, а баланс всех промежуточных вершин останется неизменным. Пока в орграфе существуют ненулевые вершины, будем проделывать данные действия. Назовем такой способ - добавление по принципу путей (или, для краткости, ДПП). ДПП, в котором среди всех возможных способов добавления путей будет суммарное минимальное число дуг, назовем оптимальным добавлением по принципу путей (для краткости, ОДПП). Количество дуг в ОДПП обозначим через m. Нахождение m и добавление дуг из этого способа позволяет получить квазиэйлеров орграф. Количество путей в способе ОДПП обозначим через k.

Теорема Дуги в способе ДПП можно истолковывать как дуги в единичной транспортной сети, насыщенные максимальным потоком: δ = {(u, v) α : flow (u, v ) = 1}. При этом воспринимая s begin, t end, (u, v) ДПП (u, v) δ.

Способ добавления дуг Лемма 1. Путем некоторых действий с добавленными дугами из способа ОДПП можно все неэйлеровы компоненты связности «соединить» в одну. Компоненту, которая получена после преобразований в леммы 1, назовем базисной. Лемма 2. Путем некоторых действий с добавленными дугами из способа ОДПП можно «присоединить» как максимум m – k изначально эйлеровых компонент связности к базисной компоненте.

Алгоритм 2 1.Преобразуем исходный орграф G = (V, α ) в транспортную сеть: - Придаем каждой дуге (u, v ) α цену cost (u, v ) = 0 и c(u, v ) = 0. - К исходному орграфу добавляем две новые вершины: источник s и сток t; - Добавляем к орграфу G = (V, α ) новые вершины: источник s и сток t. - Для каждой вершины v V, такой что d + (v ) > d - (v ) добавляем | bal (v ) | дуг (v, t ) c пропускной способностью c (s, v ) = 1 и cost (s, v) = 1. - Для каждой вершины v V, такой что d + (v ) < d - (v ) добавляем | bal (v ) | дуг (s, v ) c пропускной способностью c (v, t ) = 1 и cost (v, t ) = 1. 2.Находим максимальный поток минимальной стоимости между источником s и стоком t. 3.«Соединяем» все неэйлеровы компоненты связности и еще m - k эйлеровых по рецепту леммы 8 и леммы 9. 4.Дуги, попавшие в поток, удаляем из исходного орграфа. Полученный орграф является квазиэйлеровым. Общее число удаленных дуг будет равно u,v V cost (u, v ) * flow (u, v ) – 2 * k.

Асимптотическая сложность алгоритма 2 Время, затраченное на выполнение пунктов 1, 3, 4 алгоритма не превосходит O(n 2 ), где n – количество вершин в исходном орграфе. В итоге, время алгоритма равно времени поиска максимального потока минимальной стоимости. На данный момент известна реализация за O(n 4 ).

Оптимальная эйлерова реконструкция орграфов методом удаления дуг Постановка задачи Дан произвольный орграф G = (V, α). Необходимо удалить минимальное количество дуг так, чтобы орграф стал квазиэйлеровым. Критерий существования решения. Для любого орграфа решение поставленной задачи существует.

Способ удаления дуг Балансом вершины v назовем число bal(v) = d + (v) – d - (v). Вершину будем называть положительной, отрицательной или нулевой в зависимости от соответствующего свойства ее баланса. Возьмем произвольный путь из положительной вершины v в отрицательную вершину u и удалим все дуги этого пути. После данного действия bal(v) уменьшится на 1, bal(u) увеличиться на 1, а баланс всех промежуточных вершин останется неизменным. Опираясь на вышеизложенные рассуждения, рассмотрим следующий способ удаления дуг орграфа: пока в орграфе существуют ненулевые вершины, будем удалять пути, идущие от вершин с положительным балансом к вершинам с отрицательным балансом. Назовем такой способ - удаление по принципу путей (или, для краткости, УПП).

Теорема Дуги в способе УПП можно истолковывать как дуги в единичной транспортной сети, насыщенные максимальным потоком: δ = {(u, v) α : flow (u, v ) = 1}. При этом воспринимая s begin, t end, (u, v) УПП (u, v) δ.

Алгоритм 3 1. Преобразуем орграф в транспортную сеть: - Придаем каждой дуге (u, v ) α цену cost (u, v ) = 1 и c(u, v ) = 1. - Добавляем к орграфу G = (V, α ) новые вершины: источник s и сток t. - Для каждой вершины v V, такой что d + (v ) > d - (v ) добавляем |bal (v )| дуг (s, v ) c пропускной способностью c (s, v ) = 1 и cost (s, v) = 1. - Для каждой вершины v V, такой что d + (v ) < d - (v ) добавляем | bal (v ) | дуг (v, t ) c пропускной способностью c (v, t ) = 1 и cost (v, t ) = 1. 2.Находим максимальный поток минимальной стоимости между источником s и стоком t. Метод поиска описан в [5]. 3.Дуги, попавшие в поток, удаляем из исходного орграфа. Полученный орграф является квазиэйлеровым. Общее число удаленных дуг будет равно u,v V cost (u, v ) * flow (u, v ) – 2 * k.

Асимптотическая сложность алгоритма 3 Время, затраченное на выполнение пунктов 1, 3 алгоритма не превосходит O(n 2 ), где n – количество вершин в исходном орграфе. В итоге, время алгоритма равно времени поиска максимального потока минимальной стоимости. На данный момент известна реализация за O(n 4 ). Аналогична двум предыдущим случаям.

Практическая реализация Программа реализована на языке Java2. Основные классы программы: 1. class Arch – класс для работы с дугами орграфа 2. class Graph – класс для работы с орграфами 3. class FlowType – класс, для работы с потоками 4. сlass AddingArcs ­– класс, реализующий алгоритм оптимальной эйлеровой реконструкции путем добавления дуг 5. class ReorientationArcs – класс, реализующий алгоритм оптимальной эйлеровой реконструкции путем переориентации дуг 6. class RemoveArcs – класс, реализующий алгоритм оптимальной эйлеровой реконструкции путем удаления дуг 7. class Paint extends Applet – класс, реализующий графический интерфейс 8. class Test extends TestCase – класс, производящий тестирование проекта

Интерфейс. Ввод орграфа

Интерфейс. Диаграмма орграфа

Интерфейс. Переориентация дуг

Интерфейс. Добавление дуг

Интерфейс. Удаление дуг

Итоги В результате НИР были разработаны алгоритмы оптимальных эйлеровых реконструкций орграфов методом добавления, удаления и переориентации дуг. Проведено аналитическое исследование поставленных задач, математически доказана корректность и оптимальность решения. Реализация всех трех алгоритмов написаны на языке Java. Программа протестирована на примерах. Реализован графический интерфейс.

Список литературы 1.Басакер Р., Саати Т. Конечные графы и сети: Пер. с англ. – М.: «Наука», Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. – М.: Наука. Физматлит, Гавриков А. В. Оптимальная переориентация дуг орграфа, приводящая к эйлерову орграфу // В кн.: Наука и образование: проблемы и перспективы: Материалы 11-й региональной научно-практической конференции аспирантов, студентов и учащихся (Бийск, мая 2009 г.). В 2-х частях. - Бийск: БПГУ имени В. М. Шукшина, Часть 2. С Гавриков А. В. Оптимальная квазиэйлерова реконструкция орграфа путем удаления дуг // В кн.: Научные исследования студентов Саратовского государственного университета: Материалы итог. студ. науч. конф. --- Саратов: Изд-во Сарат. ун-та, С Гавриков А. В. Оптимальная эйлерова реконструкция орграфа путем добавления дуг // В кн.: Компьютерные науки и информационные технологии: Материалы науч. конф. ­– Саратов: Изд-во Сарат. ун-та, ­--- С Салий В. Н. Оптимальные реконструкции графов // В кн.: Современные проблемы дифференциальной геометрии и общей алгебры. – Саратов; Изд-во Сарат. ун-та, 2008, Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах: Пер. с англ. – СПб.: «ДиаСофтЮП», Шилдт Г. Java 2. Наиболее полное руководство: Пер. с англ. – СПб.: «Вильямс», 2009 г.