Линейные алгоритмы для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов

Размещено на http://www.allbest.ru/

Федеральное государственное автономное образовательное учреждение высшего образования

"Национальный исследовательский университет

"Высшая школа экономики"

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению

38.03.05 Прикладная математика и информатика

Выпускная квалификационная работа

Линейные алгоритмы для решения задачи о минимальном остовном дереве в минорно-замкнутых классах графов

Линовицкая Арина Дмитриевна

Нижний Новгород, 2019

Содержание

Введение

1. Теоретическая часть

1.1 Граф, основные понятия

1.2 Способы представления графа на компьютере

1.3 Минорно-замкнутые графы

1.4 Минимальное Остовное Дерево

1.5 Мета-Алгоритм

1.6 Алгоритм Борувки

2. Практическая часть

2.1 Генерация графа

Заключение

Список литературы

Приложения

Введение

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

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

Д. Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.

Графы используются для описания сложно структурированной информации и, следуя из этого имеет большое прикладное значение. Где же мы можем столкнуться с графами? Ниже представлена лишь небольшая часть того, где они присутствуют:

· Модели глобальной или локальной сети

· Блок-схемы алгоритма

· Электрические схемы

· Генеалогическое древо

· Схемы метрополитена

· Модели связей в базе данных

· Ментальные карты

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

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

В современное время проблема поиска минимального остовного дерева имеет огромное практическое применение и встречается во многих сферах, приведем примеры небольшой их части: биоинформатика, компьютерное зрение, кроме того при проектировании различных сетей (выше мы приводили пример о соединении n городов в единую сеть с минимальными затратами), также производство печатных плат (аналогично с сетью: к примеру, мы желаем связать n контактов проводами, используя минимальные затраты). Можно отметить, что зачастую в подобных задачах может возникнуть проблема при необходимости обработки очень больших графов, под которыми мы подразумеваем такие, что их невозможно представить в оперативной памяти типичного вычислительного узла многопроцессорной вычислительной системы. В наши дни объем памяти узла может достигать в среднем от 64 до 128 ГБ, а такому объему памяти соответствуют графы очень большого порядка: около 100 миллионов вершин и нескольких миллиардов ребер.

Вопрос, связанный с поиском минимального остовного дерева, помимо перечисленного, может найти использование в отображении взаимосвязи многоаспектных, многомерных данных. С помощью дерева также можно разбивать животных на группы и классы. Наука, и в частности биология, постоянно используют многоаспектные данные для группировки объектов, растений, животных. И в данном случае минимальное остовное дерево может помочь разбить их на взаимосвязанные классы, при этом четко отслеживая близкие по характеристикам и строению группы.

Задача нахождения минимального остовного дерева взвешенного неориентированного графа является одной из самых известных алгоритмических проблем комбинаторной оптимизации. Со времени первого решения Борувки [1, с. 37-58] в 1926 г., было разработано множество все более эффективных алгоритмов (см. [8, с. 15-22] и [4, с.43-57]). Предполагая, что веса ребер взяты из произвольного упорядоченного множества (единственная операция, определенная для них, является сравнением), на данный момент наилучшая скорость принадлежит алгоритмам Chazelle [5, с. 1028-1047] и Pettie [11], которые достигают временной сложности O(m · б(m, n)), где n и m - количество вершин и ребер графа и б(m, n) - некоторая обратная б(m, n)=min{i ? 1 : A(i, 4[m, n]) > функции Аккермана. Если вес ребер - целые числа, разрядами которых можно манипулировать в постоянное время, существует MST алгоритм Fredman and Willard [3, с. 719-725], работающий за линейное время в оперативной памяти. Кроме того, существует рандомизированный алгоритм с ожидаемым линейным временем для общего случая, принадлежащий Karger и др. [6, с. 321-328].

Недавно Pettie and Ramachandran [12, с. 49-60] показали алгоритм для указательной машины с ограничением времени работы размером оптимального дерева решений MST. Поскольку сложность дерева решений является очевидной нижней границей алгоритмической временной сложности задачи, этот алгоритм оптимален до мультипликативной постоянной, и для достижения оптимальности не требуется произвольный доступ. Однако сложность дерева решений MST по-прежнему неизвестна, и нетривиальные нижние границы неизвестны, поэтому вопрос остается открытым, можно ли найти MST в линейном времени или нет.

Хотя вопрос по-прежнему не решен для общих графов, существует несколько частных случаев, когда известны алгоритмы, работающие за линейное время. Когда граф достаточно плотный, то есть имеет по крайней мере n · ребер обозначает двоичный логарифм, повторенный k раз для некоторого k, алгоритм Тарьяна O(m · в(m, n)) [13] выполняется линейно. На другом конце спектра существует несколько алгоритмов O(m + n) для плоских графов (например, Matsui [7, c. 91-94]), поэтому единственными проблемными случаями являются графы низкой плотности без специальной структуры, которой можно было бы воспользоваться.

Мы покажем два алгоритма MST, которые работают за линейное время для любого нетривиального класса графов, замкнутых на минорах графов. В частности, это включает в себя плоские графы и графы ограниченного рода. Мы основываем наши временные границы на плотности минорно замкнутых классов (см., например, Nesetril и De Mendez [9]). Это существенное улучшение по сравнению с предыдущими результатами для плоских графов, которые требуют построения плоского вложения. Без ограничения общности мы предполагаем, что граф связан и что все веса ребер различны. Кроме того, n и m всегда обозначают количество вершин и ребер рассматриваемого графа. граф алгоритмический математика

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

Проблема исследования: "Существуют ли алгоритмы поиска минимального остовного дерева в классе графов, замкнутых на минорах, которые выполняют поставленную задачу за линейное время?"

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

Объектом исследования данной работы является минимальное остовное дерево в классе графов, замкнутых на минорах.

Предмет исследования - это алгоритмы поиска минимального остовного дерева в заданном классе графов.

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

Для достижения цели, были поставлены следующие задачи:

1. Изучить научную литературу и другие источники информации по выбранной теме.

2. Проанализировать основные определения и теоремы, необходимые для понимания алгоритмов.

3. Убедиться в том, что алгоритмы работают за линейное время и провести доказательство.

4. Создать функцию генерации случайных графов.

5. Реализовать два алгоритма поиска MST в классе графов, замкнутых на минорах.

6. Рассчитать время работы реализованных алгоритмов и проследить линейность времени выполнения для двух алгоритмов.

7. На определенно заданном графе реализовать наши два алгоритма и известные алгоритмы: Прима, Краскала и Борувки, и с ростом генерируемых вершин и ребер рассмотреть и сравнить быстродействие всех алгоритмов.

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

1. Теоретическая часть

1.1 Граф, основные понятия

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

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

Графом G называется пара G (V, E), где за V принимается конечное множество вершин, а за E - набор неупорядоченных и упорядоченных пар вершин.

Рёбра в графе могут иметь направление, и отсюда они делятся на два типа: неориентированные и ориентированные.

- ребро E неориентированное.

- дуга - ориентированное ребро Е.

Рис. 1 (Неориентированный и ориентированный граф)

Аналогично ребрам, графы подразделяются на:

1) Неориентированный граф представляет собой граф, ребра которого не имеют направления (двусторонние), как представлено на рисунке 1 (левый граф).

2) Ориентированный граф (орграф), соответственно, граф ребра которого имеют некоторое направление, как представлено на рисунке 1 (правый граф).

Немаловажным понятием в теории графов является смежные вершины. Это такие две вершины, которые соединены ребром е, а данное ребро e принадлежит (иначе говоря инцидентно) каждой из них.

Отсюда вытекает следующее определение: степень вершины - количество ребер графа, которые принадлежат (или инцидентны) ей.

Если мы сложим степени всех вершин в графе, то получим удвоенное число всех его ребер, наглядный пример приведен на рисунке 2, где сумма всех степеней равна 20.

Рис. 2

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



Рис. 3

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

Кроме того, если граф состоит из единственной вершины, то его называют тривиальным.

Простой граф можно назвать полным в том случае, если любая пара его вершин соединена ребром (т.е. он содержит максимально возможное количество рёбер). В таком графе n * (n-1)/2 ребер.

Существуют также разреженные графы. Это такие графы, где общее количество ребер значительно меньше их возможного количества. На рисунке 4 представлены примеры полного и разреженного графа:

Рис. 4

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

Пример связного и не связного графа показан на рисунке 5:

Рис. 5

В нашей работе мы будем иметь дело с неориентированными взвешенными графами. Неориентированный граф можно представить, как граф G, который описывает упорядоченная пара G=(V,E), где за V принимается непустое множество вершин в нем, а за E, соответственно, множество пар неупорядоченных ребер. Ниже на рисунке 6 мы видим пример неориентированного графа с пятью вершинами и шестью ребрами:

Рис. 6

Под взвешенным графом понимается такой граф, как представлен на рисунке 7, дугам которого поставлены в соответствие веса:



Рис. 7

Два или более графов с первого взгляда могут показаться различными по своей структуре; такое ощущение возникает из-за разного их изображения. Хотя, можно отметить, что это не всегда верно. Возьмем иллюстрацию двух графов на рисунке 8:

Рис. 8

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

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

1.2 Способы представления графа на компьютере

Графы, как и большинство других математических объектов, могут быть представлены на компьютере (сохранен в его памяти). Существует несколько способов его интерпретации:

· Список смежности;

· Список ребер;

· Матрица смежности;

· Матрица инцидентности;

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



Рис. 9

a: {b, c, d, e}

b: {a}

c: {a, d}

d: {a, c, e}

e: {a, f}

f: {e}

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

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

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

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

Два последних метода (матрица смежности и матрица инцидентности) предполагают собой хранение графа в виде двумерного массива (матрицы). Причем нужно отметить, что размеры этих массивов напрямую зависят от количества вершин и/или ребер в конкретном графе. Таким образом, матрица смежности имеет размер n Ч n, где n - число вершин, а матрица инцидентности n Ч m, где соответственно n - число вершин, m - число ребер в графе.

На рисунке 10 представлен пример взвешенного неориентированного графа и его матрица инцидентности:

Рис. 10

Перечислим некоторые важные свойства матрицы инцидентности простого графа:

· Количество единиц в i-ой строке соответствует степени i-ой вершины

· Количество единиц в j-ом столбце равно двум

· Общее количество единиц в матрице равно удвоенному числу ребер графа

На рисунке 11 можно увидеть матрицу смежности, которая описывает граф, приведенный выше на рисунке 10:



Рис. 11

Теперь приведем несколько свойств матрицы смежности простого графа:

· Количество единиц в i-ой строке соответствует степени i-ой вершины

· Количество единиц в j-ой строке соответствует степени j-ой вершины

· Общее количество единиц в матрице равно удвоенному числу ребер графа

· Матрица смежности симметрична относительно главной диагонали.

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

1.3 Минорно-замкнутые графы

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

Граф H является минором графа G, если он может быть получен из исходного графа G путем последовательного удаления рёбер и вершин и стягивания рёбер.

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

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

Многие семейства графов обладают следующим свойством: любой минор графа из G также входит в исходный граф G. Тогда мы имеем дело с классом графов, который называется минорно замкнутым. Например, для любого вложения графа в фиксированную топологическую поверхность или для любого планарного графа ни удаление рёбер, ни стягивание рёбер не может увеличить род вложения. Таким образом, планарные графы и графы, вложимые в любую фиксированную поверхность, образуют минорно замкнутые семейства.

Следующим шагом разберем подробно несколько теорем и лемм, которые помогут в понимании алгоритмов и в их реализации.

Пусть C - класс графов. Определим его плотность ребер с(C) как

инфимум всех с такой, что | E(G) | ? с · | V(G) | выполняется для любого G · C.

Теорема 1 (см. Теорему 6.1 в [9]). Минорно замкнутый класс C имеет конечную плотность ребер, если C является нетривиальным классом, т. е. отличается от класса всех графов и пустого класса.

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

Лемма 1(Лемма Плотности). Пусть C - класс графа с плотностью с и G ? C - граф с N вершинами. Тогда не менее n / 2 вершин G имеют степень не более 4с.

Доказательство. Предположим обратное: пусть существует не менее n/2 вершин со степенью больше 4с. Тогда что противоречит числу ребер ? сn. (Доказательство также можно рассматривать вероятностно:

Пусть X - степень вершины G, выбранной равномерно случайным образом.

Тогда EX ? 2с, следовательно, по неравенству Маркова Pr[X > 4с] < 1/2, поэтому по крайней мере для n/2 вершин ? 4с.)

Для плоских графов граница может быть легко сжата:

Лемма 2(Лемма Плотности для плоских графов). Пусть G - плоский граф с n вершинами. Тогда не менее n / 2 вершин v имеют степень не более 8.

Доказательство. Достаточно показать, что Лемма справедлива для триангуляций (если отсутствуют какие-либо ребра, ситуация может только улучшиться), по крайней мере, с 3 вершинами. Так как G является плоским графом, . Числа d(v) := ? 3 неотрицательны и < 3n, следовательно, пользуясь тем же аргументом, что и в предыдущем доказательстве, по крайней мере для n / 2 вершин v считаем, что d(v) < 6, следовательно, ? 8.

1.4 Минимальное Остовное Дерево

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

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

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

В общем виде задачу о поиске MST можно сформулировать следующим образом: пусть существует связный, неориентированный взвешенный граф G(V, E), в котором соответственно V - это множество вершин, а E - это множество их всевозможных попарных связей (ребер). Предположим, что для каждого ребра (u, v) однозначно определено некоторое вещественное число w, которое является его весом. Проблема состоит в нахождении такого связного ациклического подграфа T G, который будет содержать все его вершины, что полученный суммарный вес его ребер будет минимален. В связи с тем, что T связен и не содержит циклов, то по определению он является деревом и называется остовным или покрывающим деревом.

Задача о нахождении MST часто встречается в подобной постановке: предположим, мы имеем n городов, которые нужно связать дорогой таким образом, чтобы была возможность переправиться из одного города в другой (как напрямую, так и через другие города). Существует возможность прокладывать дороги между определенными парами городов, и известна стоимость строительства каждой такой дороги. Суть описанной задачи заключается в том, что требуется найти, какие конкретно дороги нужно построить, чтобы общие затраты на строительство были минимальными.

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

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

1.5 Мета-Алгоритм

Наши два алгоритма являются вариациями исходного алгоритма Борувки, но вместо того, чтобы выращивать лес поддеревьев MST, соединяя их ребрами, недавно добавленными в MST, мы сохраняем каждое поддерево сжатым до одной вершины (этот подход был предложен в менее общей формулировке Тарьяном в [13]). Оба алгоритма можно считать воплощениями следующего "мета-алгоритма":

1. Начните с входного графа.

2. Найдите ребра, которые являются частью MST текущего графика.

3. Выполните процедуру стягивания вдоль этих ребер.

4. Очистите график (будет описано ниже).

5. Повторяйте шаги 2-4, пока не останется ребер.

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

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

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

Для этого мы вводим фазу очистки, которая иногда вызывается в ходе алгоритма и цель которой - упростить граф:

4.1. Сортировать все ребра графа лексикографически, объединяя параллельные ребра.

4.2. Пройдите список ребер последовательно, удалите ненужные параллельные ребра и пересчитайте степени вершин.

4.3. Удалить нулевые вершины.

Очистка занимает время O (m + n), где m и n - количество ребер и вершин до очистки, поэтому мы должны использовать эту процедуру очень осторожно.

1.6 Алгоритм Борувки

Далее рассмотрим подробнее алгоритм Борувки, на который основаны наши два алгоритма:

Алгоритм состоит из нескольких шагов:

1. На первом шаге каждая вершина графа G - это тривиальное дерево, а имеющиеся в нем ребра не принадлежат никакому дереву.

2. Для каждого дерева T найдем минимальное по весу инцидентное ему ребро и сразу добавим все такие ребра.

3. Необходимо повторять шаг 2 до тех пор, пока в графе не останется единственное дерево T.

Приведем иллюстрацию работы данного алгоритма на примере небольшого графа, который представлен в таблице 1:

Табл. 1

Иллюстрация	Компоненты связности	Описание
	{A} {B} {C} {D} {E} {F} {G}	Исходный граф G. Каждая вершина этого графа является компонентой.
	{ABDF} {CEG}	На первой итерации внешнего цикла алгоритма для каждой компоненты были добавлены минимальные ребра, инцидентные ей. Некоторые ребра были добавлены несколько раз (AD и CE). Осталось две компоненты.
	{ABCDEFG}	На последней итерации внешнего цикла алгоритма было добавлено минимальное ребро, соединяющее две оставшиеся компоненты (ребро BE). Осталась одна компонента. Минимальное остовное дерево графа G построено.

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

Приступим к детальному разбору по шагам наших алгоритмов.

Алгоритм 1

Мы следуем "мета-алгоритму", используя тот факт, что для каждой вершины самое легкое ребро, исходящее из нее, принадлежит MST (это следует из правила Тарьяна [13], примененного к разрезу, образованному ребрами, падающими на вершину). Никакие циклы не могут возникнуть, так как веса ребер различны. Кроме того, мы обрабатываем стягивания всех вершин текущего графа одновременно и очищаем граф после этого. Это дает:

1. Начните с входного графика.

2. Построить временный граф G' на том же множестве вершин. Для каждой вершины G' содержит самое легкое по весу ребро из G, выходящее из вершины .

3. Стяните граф вдоль ребер G': найдите компоненты связности G' и перенумеруйте каждую вершину G на номер компоненты, которой они принадлежат.

4. Очистить график (как определено выше).

5. Повторяйте шаги 2-4, пока не останется ребер.

Лемма 3. Для любого нетривиального замкнутого на минорах класса графов C алгоритм 1 находит MST любого графа в этом классе за время O(с(C) · n).

Доказательство. Корректность следует из мета-алгоритма. Каждый проход алгоритма занимает время O(m + n) и уменьшает n как минимум в два раза. Все графы, сгенерированные алгоритмом, являются минорами входного графа, поэтому они также принадлежат C и, согласно теореме 1, m ? n выполняется для всех из них. Поэтому общее время, затраченное алгоритмом, равно

O(n + n/2 + n/4 + . . .) = O(n).

Алгоритм 2

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

Это дает наш второй алгоритм (t-параметр, который будет определен позже):

1. Начните с входного графика.

2. Пока существует вершина с deg() ? 4t, выберите самое легкое ребро e, исходящее из вершины , и сожмите его (просто удалите все ребра, исходящие из , и добавьте их обратно в график с , перенумерованным на другой конец e). Удалите все возникающие петли и изолированные вершины. Чтобы избежать последовательного поиска, создайте очередь таких вершин низкой степени.

3. Очистить график (как определено выше).

4. Повторите шаги 2-3, пока не останется ребер.

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

Мы получаем лемму, которая доказывает, что данный алгоритм выполняет свою задачу за линейное время:

Лемма 4. Для любого нетривиального минорно замкнутого класса графов C алгоритм 2 с t ? с(C) находит MST любого графа в этом классе за линейное время равное O (tn).

Доказательство. Пусть обозначает граф, с которым мы работаем в начале шага i на k-й итерации алгоритма, пусть и - его количество вершин и ребер соответственно. Для каждого k - простой граф, который является минором входного графа, поэтому он принадлежит C и согласно теореме 1, ? , где с = с(C). Из леммы 1 следует, что по крайней мере, / 2 вершин имеют deg() ? 4с ? 4t. Из-за этого Шаг 2 выполняется по крайней мере один раз на каждой итерации, поэтому алгоритм останавливается после конечного числа итераций и, поскольку он следует мета-алгоритму, он корректен.

Все выполнения шага 2 вносят вклад в общее время работы O(tn) - каждое стягивание занимает O(t) и удаляет по крайней мере одну вершину. Чтобы завершить доказательство сложности времени, достаточно показать, что общее время, затраченное на все очистки, равно O(tn).

Давайте посмотрим на k-ю очистку: она занимает

O( + )

единиц времени. Однако мы знаем, что

? и ? ? ,

поэтому мы можем ограничить время O().

Кроме того, содержит не менее / 2 вершин deg() ? 4t (пусть D обозначает их множество), а все вершины имеют deg() > 4t. Таким образом, каждая вершина v ? D должна была либо исчезнуть, будучи объединена с другой вершиной стягиванием, либо deg() должен был увеличиться на другую вершину, которая была объединена с . Учитывая, что каждое сокращение может влиять таким образом не более чем на две вершины D, должно было быть не менее / 4 сокращений, и поскольку каждое из них удаляет не менее одной вершины,

? · .

Таким образом, все очистки занимают время

O(t) = O(tn + tn + tn + . . .) = O(tn).

Примечание 1. Для плоских графов мы можем воспользоваться Леммой 2 и улучшить производительность постоянным фактором, установив параметр t равный 2.

2. Практическая часть

2.1 Генерация графа

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

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

· Список смежности;

· Список ребер;

· Матрица смежности;

· Матрица инцидентности;

В нашем случае целесообразнее всего выбрать первый вариант - список смежности. По отношению к памяти списки смежности менее требовательны, чем матрицы смежности, для их хранения нужно O(|V|+|E|) памяти. Такой список графически можно изобразить в виде таблицы, столбцов в которой - два, а строк не больше чем вершин в графе. Для большей наглядности нашего выбора представим таблицу 2, где можно увидеть сравнение списка и матрицы смежности для разных операций:

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

За генерацию графа отвечает функция generate(int nVert, int nEdge), где мы задаем nVert - число вершин в графе и nEdge - число ребер исходного

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

Табл.2

Операция	Список смежности	Матрица смежности
Проверка на наличие ребра	O(|E|)	O(1)
Определение степени вершины	O(1)	O(|V|)
Использование памяти для разреженных графов	O(|V|+|E|)	O()
Вставка/удаление грани	O(1)	O(d)
Обход графа	O(|V|+|E|)	O()

Реализация Алгоритма 1

Приступим к реализации первого алгоритма Alg1(). (Приложение 1)

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

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

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

И все шаги повторяются до тех пор, пока у нас не останется ребер, поэтому алгоритм выполняется в цикле while (graphTemp.size() > 1).

Для того, чтобы получить остовное дерево мы вводим дополнительные вектора graphEdgeTempFrom, graphEdgeTempTo, graphEdgeFrom, graphEdgeTo, которые хранят номера вершин и соответствующих ребер, имеющих минимальный вес, которые мы на первом шаге добавляем во временный граф GraphG. И таким образом мы восстанавливаем MST и находим его стоимость. На рисунке 13 можно наглядно увидеть пример работы первого алгоритма:

Рис. 13

Реализация Алгоритма 2

Перейдем к реализации алгоритма номер 2 Alg2() (Приложение 1).

В первую очередь нам необходимо посчитать плотность графа, для выполнения условий алгоритма (float ro = m / float(graphTemp.size())). И мы создаем вектор vertList, который хранит список вершин с низкими степенями. И далее мы выполняем действия согласно алгоритму: пока существует вершина с deg (v) ? 4с, (deg-степень вершины) выбираем самое легкое ребро и стягиваем его с вершиной, из которой оно выходит. Операция стягивания connect уже была определена выше. Далее с помощью уже существующей функции очистки clear() мы чистим граф.

И аналогично алгоритму 1, все шаги повторяются до тех пор, пока у нас не останется ребер. Вектора MSTTo, MSTFROM, MSTEDGE хранят список вершин с наименьшими ребрами и соответствующими вершинами. По ним мы восстанавливаем наше минимальное остовное дерево и находим его стоимость. На рисунке 14 можно представлен пример работы второго алгоритма:

Рис. 14

Алгоритмы Прима, Краскала и Борувки. Сравнение с Алгоритмом 1 и Алгоритмом 2

Далее мы сравним наши алгоритмы с уже существующими и известными алгоритмами: Прима, Краскала и Борувки.

Напомним суть данных алгоритмов:

Алгоритм Прима.

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

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

В итоге, результатом работы данного алгоритма является минимальное остовное дерево, построенное на вершинах исходного графа.

Приведем иллюстрацию работы данного алгоритма на примере небольшого графа в таблице 3:

Табл.3

Иллюстрация	Множество выбранных вершин U	Ребро (u, v)
	{}
	{D}	(D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6
	{A,D}	(D,B) = 9 (D,E) = 15 (D,F) = 6 V (A,B) = 7
	{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11
	{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 цикл (D,E) = 15 (F,E) = 8 (F,G) = 11
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 цикл (D,E) = 15 цикл (E,C) = 5 V (E,G) = 9 (F,E) = 8 цикл (F,G) = 11
	{A,B,C,D,E,F}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (E,G) = 9 V (F,E) = 8 цикл (F,G) = 11
	{A,B,C,D,E,F,G}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл

Алгоритм Краскала.

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

Приведем иллюстрацию работы данного алгоритма на примере небольшого графа в таблице 4.

Алгоритм Борувки был описан в теоретической части работы.

Добавим реализацию данных алгоритмов в наш код (Приложение 1): AlgPrim(), AlgKruskal(), AlgBoruvka().

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

Табл. 4

Иллюстрация	Описание
	Ребра AD и CE имеют минимальную стоимость, которая равна 5. Мы произвольно выбираем из них AD.
	Далее можно заметить, что теперь наименьшую стоимость имеет ребро CE, равнe. 5. В силу того, что добавление CE не образует цикла, следовательно мы добавляем его в качестве второго ребра.
	Аналогично добавляем ребро DF, у которого стоимость равна 6.
	Следующим шагом минимальные ребра - это AB и BE с весом 7. Произвольно выбираем ребро AB. Так как уже существует путь между B и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD.
	Аналогично добавляем ребро BE, стоимость которого равна 7. Появилось несколько ребер, которые могут создать цикл: BC сформирует цикл BCE, DE - цикл DEBA, и FE - цикл FEBAD.
	Алгоритм завершается после добавления ребра EG со стоимостью 9. Таким образом остовное дерево с минимальным весом построен.

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

Ниже на рисунках 15, 16, 17 представлен пример работы программы поиска минимального остовного дерева для пяти различных алгоритмов (Алгоритм 1, Алгоритм 2, Прима, Краскала и Борувки):

Рис. 15 (Исходный сгенерированный граф)



Рис. 16 (Работа Алг.1 и Алг.2)

Рис. 17 (Работа Алг. Прима, Алг. Краскала и Алг. Борувки)

На рисунке 18 можно увидеть вывод временных тактов работы каждого алгоритма:



Рис. 18

Результаты временных вычислений при увеличении числа элементов генерируемого графа представлены в таблице 5:

Табл. 5

Число вершин, ребер (n, m)	Алг. 1	Алг. 2	Алг. Прима	Алг. Краскала	Алг. Борувки
(5, 10)	5	7	8	7	5
(15, 25)	17	21	45	18	21
(50, 80)	56	73	310	68	95
(100, 150)	113	145	1136	317	217
(200, 300)	255	231	5510	672	496
(500, 750)	548	497	-	2748	1438
(1000, 1500)	1217	941	-	8211	3179

Из результатов замеров можно сделать несколько выводов:

1. Наглядно прослеживается линейность наших алгоритмов (Алг. 1 и Алг. 2). Выше в Лемме 3 и Лемме 4 мы упоминали, что время их работы зависит от количества вершин и плотности графа. Для примера возьмем номер эксперимента 3 и 4. Число вершин равно 50 и 100 соответственно, а плотности 1,6 и 1,5. И их произведение отличается почти в 2 раза, что мы наблюдаем и в изменении временных тактов: 56->113 (для Алг.1) и 73->145 (для Алг.2).

2. Алгоритм Прима показал наихудший результат, так как он очень быстро увеличивал показатели времени работы при увеличении числа вершин и ребер, а при определенных больших графах он вовсе сломался.

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

Заключение

В ходе исследования были выполнены поставленные задачи. А именно, детально изучена научная литература многих авторов по выбранной теме, проанализированы основные определения и теоремы, необходимые для понимания алгоритмов. Проделана практическая работа на основе изученного теоретического материала. Для реализации алгоритмов мы использовали язык программирования С++ в силу его удобства. В программной части работы в первую очередь была создана функция, которая генерирует случайный граф на заданном множестве вершин. И после чего, реализованы два алгоритма поиска MST в классе графов, замкнутых на минорах и произведено практическое сравнение быстродействия наших алгоритмов с существующими: Прима, Краскала и Борувки. Таким образом, поставленная цель достигнута и наши предположения в гипотезе подтверждены. Действительно, мы представили алгоритмы для задачи поиска минимального остовного дерева, которые выполняются в детерминированное линейное время для любого нетривиального класса графов, замкнутого на минорах. Из практических замеров времени выполнения задачи мы смогли пронаблюдать линейность наших двух алгоритмов на растущем числе вершин и ребер генерируемого исходного графа. И именно благодаря линейности, при возрастании размерности графа наши реализованные алгоритмы справляются со своей задачей на порядок лучше, чем всеми известные алгоритмы Прима, Краскала и Борувки.

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

Список литературы

1. Boruvka O., O jistem problemu minimalnэm (About a Certain Minimal Problem), Prace mor. prэrodoved. spol. v Brne, III, (1926), 37-58.

2. Frederickson G. N., Data structures for on-line updating of minimum spanning trees, SIAM J. Comput. 14 (1985), 781-798.

3. Fredman M., Willard D. E., Trans-dichotomous algorithms for minimum spanning trees and shortest paths, In Proceedings of FOCS'90 (1990), 719-725.

4. Graham R. L., Hell P., On the history of the minimum spanning tree problem, Ann. Hist. Comput. 7 (1985), 43-57.

5. Chazelle B., A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, J. ACM 47 (2000), 1028-1047.

6. Karger D. R., Klein, P. N., Tarjan R. E., Linear expected-time algorithms for connectivity problems, J. ACM 42 (1995), 321-328.

7. Matsui T., The Minimum Spanning tree Problem on a Planar Graph, Discrete Appl. Math. 58 (1995), 91-94.

8. Nesetril, J., Some remarks on the history of MST-problem, Arch. Math. (Brno) 33 (1997), 15-22.

9. Nesetril, J., de Mendez, P. O., Colorings and Homomorphism of Minor Closed Classes, To appear in Pollack-Goodman Festschrift, Springer Verlag, 2002.

10. Nesetril J., Milkova E., Nesetrilova H., Otakar Boruvka on Minimum Spanning Tree Problem, Discrete Math. 233(1-3) (2001), 3-36.

11. Pettie S., Finding minimum spanning trees in O(mб(m, n)) time, Tech Report TR99-23, Univ. of Texas at Austin, 1999.

12. Pettie S., Ramachandran V., An Optimal Minimum Spanning Tree Algorithm, In Proceedings of ICALP'2000, 49-60, Springer Verlag, 2000.

13. Tarjan R. E., Data structures and network algorithms, 44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983.

14. Martin Mares, Two linear time algorithms for MST on minor closed graph classes, Archivum Mathematicum, Masaryk University,2004, No.3, P.315-320

Приложения

Приложение 1.

MyGraph.cpp

#include "pch.h"

#include "MyGraph.h"

#include <set>

#include <time.h>

#include <iostream>

using namespace std;

void MyGraph::findMins()

{

int vert = graphTemp.size();

graphG.clear();

graphGEdge.clear();

graphG.resize(vert);

graphGEdge.resize(vert);

for (int i = 0; i < vert; i++)

{

int min = 0;

for (int j = 1; j < graphTemp[i].size(); j++)

{

if (graphEdgeTemp[i][j] < graphEdgeTemp[i][min])

{

min = j;

}

}

int flag = 1;

for (int j = 0; j < graphG[i].size(); j++)

{

if (graphG[i][j] == graphTemp[i][min])

{

flag = 0;

break;

}

}

if (flag)

{

graphG[i].push_back(graphTemp[i][min]);

graphGEdge[i].push_back(graphEdgeTemp[i][min]);

MSTEDGE.push_back(graphEdgeTemp[i][min]);

MSTFROM.push_back(graphEdgeTempFrom[i][min]);

MSTTo.push_back(graphEdgeTempTo[i][min]);

}

flag = 1;

for (int j = 0; j < graphG[graphTemp[i][min]].size(); j++)

{

if (graphG[graphTemp[i][min]][j] == i)

{

flag = 0;

}

}

if (flag)

{

graphG[graphTemp[i][min]].push_back(i);

graphGEdge[graphTemp[i][min]].push_back(graphEdgeTemp[i][min]);

}

}

/*

cout " "graphG" " endl;

for (int i = 0; i < graphG.size(); i++)

{

for (int j = 0; j < graphG[i].size(); j++)

{

std::cout " i " "->" " graphG[i][j] " "=" " graphGEdge[i][j] " endl;

}

}

*/

}

void MyGraph::connect(int n1, int n2)

{

//cout " "con" " n1 " " " " n2 " endl;

for (int i = 0; i < graphTemp[n2].size(); i++)

{

graphTemp[n1].push_back(graphTemp[n2][i]);

graphEdgeTemp[n1].push_back(graphEdgeTemp[n2][i]);

graphEdgeTempFrom[n1].push_back(graphEdgeTempFrom[n2][i]);

graphEdgeTempTo[n1].push_back(graphEdgeTempTo[n2][i]);

}

graphTemp[n2].clear();

graphEdgeTemp[n2].clear();

graphEdgeTempFrom[n2].clear();

graphEdgeTempTo[n2].clear();

name[n2] = n1;

}

void MyGraph::clear()

{

for (int i = 0; i < name.size(); i++)

{

int j = i;

while (j!=name[j])

{

j = name[j];

}

name[i] = name[j];

}

/*

cout " "name" " endl;

for (int i = 0; i < name.size(); i++)

{

cout " name[i] " " ";

}

cout " endl;

*/

vector<int>name2 = name;

int k = 0;

for (int i = 0; i < name.size(); i++)

{

if (name[i] == i)

{

name2[i] = k;

for (int j = 0; j < name.size(); j++)

{

if (name[j] == name[i])

{

name2[j] = k;

}

}

k++;

}

}

/*

cout " "name2" " endl;

for (int i = 0; i < name2.size(); i++)

{

cout " name2[i] " " ";

}

cout " endl;

*/

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

graphTemp[i][j] = name2[graphTemp[i][j]];

if (name2[i] == graphTemp[i][j])

{

graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j); graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j);

graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j);

graphTemp[i].erase(graphTemp[i].begin()+j);

j--;

}

}

}

/*

cout " "NEW TEMP" " endl;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

std::cout " name2[i] " "->" " graphTemp[i][j] " "=" " graphEdgeTemp[i][j] " endl;

}

}*/

for (int i = 0; i < graphTemp.size(); i++)

{

if (graphTemp[i].size() < 1)

{

graphEdgeTemp.erase(graphEdgeTemp.begin() + i);

graphEdgeTempFrom.erase(graphEdgeTempFrom.begin() + i);

graphEdgeTempTo.erase(graphEdgeTempTo.begin() + i);

graphTemp.erase(graphTemp.begin() + i);

i--;

}

}

/*

cout " "NEW NEW TEMP" " endl;

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

std::cout " i " "->" " graphTemp[i][j] " "=" " graphEdgeTemp[i][j] " endl;

}

}

*/

for (int i = 0; i < graphTemp.size(); i++)

{

for (int j = 0; j < graphTemp[i].size(); j++)

{

int min = j;

for (int k = j + 1; k < graphTemp[i].size(); k++)

{

if (graphTemp[i][k] < graphTemp[i][min])

{

min = k;

}

}

swap(graphTemp[i][j], graphTemp[i][min]);

swap(graphEdgeTemp[i][j], graphEdgeTemp[i][min]);

swap(graphEdgeTempFrom[i][j], graphEdgeTempFrom[i][min]);

swap(graphEdgeTempTo[i][j], graphEdgeTempTo[i][min]);

}

for (int j = 1; j < graphTemp[i].size(); j++)

{

if (graphTemp[i][j] == graphTemp[i][j - 1])

{

if (graphEdgeTemp[i][j] < graphEdgeTemp[i][j - 1])

{

graphTemp[i].erase(graphTemp[i].begin() + j - 1); graphEdgeTemp[i].erase(graphEdgeTemp[i].begin() + j - 1); graphEdgeTempFrom[i].erase(graphEdgeTempFrom[i].begin() + j - 1); graphEdgeTempTo[i].erase(graphEdgeTempTo[i].begin() + j - 1);

}

else

{

graphTemp[i].erase(graphTemp[i].begin() + j);

...