Матричное представление графов

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

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

Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов — это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. Графическая интерпретация различных моделей графов дана на Рис. 1.1 б. Так в виде ориентированных графов можно представить любую логическую или функционально — логическую схему. На таких графовых моделях можно, например, оценить быстродействие схемы. Блок-схема алгоритма может быть представлена вероятностным графом, который позволяет оценить временные характеристики алгоритма, затраты процессорного времени, трудоемкость и другие. Графом типа «дерево» можно отобразить практически любую структуру организации или предприятия.

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

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

1. Определение графа и основные понятия

Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками, прямоугольниками и т. д.), а связи между ними — линиями или стрелками, соединяющими элементы. При этом получаются диаграммы вроде тех, что показаны на рис. 1.1. На данных диаграммах ни способ изображения элементов, ни форма или длина линий не имеют значения — важно лишь, какие именно пары элементов соединены линиями. Однако, эту же структуру можно представить и без графического изображения, а просто перечислив пары связанных между собой элементов: (1,4), (4,5), (5,3), (3,2), (2,1), (1,3). Таким образом мы получаем два списка: список элементов и список пар элементов. Вместе они составляют то, что математически называют «графом». Граф состоит из двух множеств — множества вершин и множества ребер, причем для каждого ребра указана пара вершин, которые это ребро соединяет.

В листинге 1 приводится пример реализации данного графа (Рис. 1.1 в) на языке python с использованием библиотек NetworkX и matplotLib.

Листинг 1.

try:

import matplotlib. pyplot as plt

except:

raise

import networkx as nx

G=nx.cycle_graph (24)

pos=nx.spring_layout (G, iterations=200)

nx.draw (G, pos, node_color=range (24), node_size=800, cmap=plt.cm. Blues)

plt.show () # display

Существует также понятие ориентированный граф или орграф. Это есть граф, ребрам которого присвоено направление. Направленные ребрами именуются также дугами или просто ребрами.

То есть на Рис. 1.1 г. пара вершин (4, 5) и (5, 4) будет различаться, так как ребро, которое их соединяет, будет иметь направление.

Для ориентированных графов выделяют следующие понятия:

— ребро входит в вершину, если по нему можно двигаться в направлении к этой вершине, и выходит из вершины, если по нему можно двигаться в направлении от этой вершины;

— входящая степень вершины — это число входящих в нее ребер;

— исходящая (или выходящая) степень вершины — это число выходящих из нее ребер;

— путь из вершины A в вершину B — это последовательность ребер и промежуточных вершин, по которым можно дойти из A в B; длина пути определяется, как обычно (число ребер); простой путь — как обычно, путь, в котором вершины (и тем более, ребра) не повторяются;

— ориентированный цикл — это замкнутый простой путь в ориентированном графе;

— сильно связный ориентированный граф — это ориентированный граф, где из любой вершины в любую есть путь (для каждой пары вершин A и B есть как путь из A в B, так и путь из B в A);

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

— смежные ребра — ребра, которые имеют общую концевую вершину.

Вершины и называются концевыми вершинами (или просто концами) ребра .

По отношению к вершинам ребро e в таком случае называется инцидентным и наоборот.

Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

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

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

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

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

Сам граф по отношению к своим подграфам называется надграфом (суграфом или суперграфом). На Рис. 1.2 представлен подграф графа, приведенного выше (Рис. 1.1 г.).

алгоритм граф матрица Существует также понятие пустой граф, граф, который не имеет ребер и вершин.

Полным называется граф, в котором две вершины смежны.

2. Применение графов

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

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

Основные сферы применения теории графов:

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

— В информатике и программировании (граф-схема алгоритма);

— В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете;

— В экономике;

— В логистике;

— В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).

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

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

3. Матричное представление графов

Матрица инциденций.

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

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

Для ориентированного графа элементы матрицы задаются так:

Матрицу типа, определенную указанным образом, называют матрицей инциденций.

Пример получения матрицы инциденций. Для изображенного ниже графа (Рис. 2.1 а) матрицей инциденций будет матрица, представленная на (Рис. 2.1 б).

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

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

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

Для решения этой задачи на матрице инциденций ориентированного графа нужно идти по строке с номером до появления ненулевого элемента (+1 или -1). В случае если обнаружена +1, в соответствующем столбце надо найти строку, в которой записано число -1. Номер строки, в которой стоит это число, дает номер вершины, непосредственно достижимой из данной вершины. Если обнаружена -1, в столбце надо найти строку, в которой записана 1, и получить номер вершины, из которой непосредственно достижима данная вершина. Для получения всего «окружения» надо проделать указанный поиск для всех ненулевых элементов k-й строки. Наиболее трудоемкой процедурой является поиск ненулевого элемента в столбце. Число таких процедур поиска равно степени вершины. Будем в этом случае говорить, что сложность алгоритма анализа окружения вершины составляет (порядка).

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

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

для неориентированного графа:

для ориентированного графа:

Для изображенного ниже графа (Рис. 2.2 а) матрицей инциденций будет матрица, представленная на (Рис. 2.2 б).

Рис. 2.2 а

Матрица разрезов.

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

Матрица разрезов графа с m ребрами имеет m столбцов и столько строк, сколько в этом графе имеется разрезов. Элемент определяется следующим образом.

Если граф ориентированный,

Если граф неориентированный,

Строки матрицы называются векторами разрезов.

Цикломатическая матрица

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

Рассмотрим дугу e с концевыми вершинами к и входит в цикл C. Будем говорить, что ориентация дуги e соответствует ориентации цикла, если вершина встречается при обходе цикла C в направлении, указанном его ориентацией, раньше вершины. Цикломатическая матрица графа G с m ребрами имеет m и столько строк, сколько циклов имеется в графе G. Элемент определяется следующим образом:

Если граф ориентированный,

Если граф неориентированный,

Матрица Кирхгофа

Дан простой граф с вершинами. Тогда матрица Кирхгофа данного графа будет определяться следующим образом:

Также матрицу Кирхгофа можно определить как разность матриц где — это матрица смежности данного графа, а — матрица, на главной диагонали которой степени вершин графа, а остальные элементы — нули:

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

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

Пример матрицы Кирхгофа.

4. Специальные свойства графов

Пусть G — произвольный (n, m) — граф с k компонентами связности. Если G — не лес, то в нем (его компонентах связности) существуют циклы. Рассмотрим какой-либо цикл и удалим из него некоторое ребро. При этом количество компонент связности не увеличится. Если после этого еще останутся циклы, то рассмотрим следующий из них и снова удалим какое-либо его ребро. Продолжим этот процесс до тех пор, пока не исчезнут все циклы. Полученный в результате подграф, который, очевидно, является лесом и имеет столько же компонент связности, как и исходный граф G, называется остовом графа G.

Теорема. Число ребер графа G, которые нужно удалить для получения остова, не зависит от способа удаления и равно m-n+k.

Теорема (Кирхгоф). Число остовов в связном графе G порядка n>=2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G) графа G.

Теорема. Орграф сильно связен, если в нем существует основной циклический маршрут.

5. Решение оптимизационных задач

Алгоритм Дейкстры.

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны ((u, v)? 0 для всех (u, v)E).

Пример решения задачи. Поиск ведется на данном графе (Рис. 3.1). Веса соответствуют длине ребер.

Листинг 2.

import networkx as nx

import matplotlib. pyplot as plt

G = nx. DiGraph () #Объявляем орграф G

G.add_nodes_from (range (1, 7)) #Добавляем вершины из набора чисел (1.7)

for i in range (1,10):

G.add_edge (i, i-1) #Добавляем ребро, соединяющее вершину i с i-1

for i in range (1,10):

if (i+5<10):

G.add_edge (i, i+5, weight = i*0.5+2)#Устанавливаем веса на ребра

nx.draw (G, node_color = 'm', font_color = 'w')

plt.show ()

print (nx.dijkstra_path (G, 2, 8)) #Поиск и вывод массива вершин

# Использование функции для нахождения маршрута. Поиск начинается с вершины 2 и идет до вершины 8.

Выходные данные:

[2, 1, 6, 5, 4, 3, 8]

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

0. G — данный ориентированный граф с взвешенными ребрами. Требуется найти кратчайшие пути из вершины s во все остальные вершины графа G.

1. (Начало). Положить label(s) = 0, perm(s) = 1 и pred(s) = s. Для всех v <> s положить label(v) = ?, perm(v) = 0, pred(v) = v.

2. Пусть i = 0 и u = s. (u - последняя из вершин с неизменной меткой. Теперь — это вершина s.)

3. (Вычисление label и изменение элементов массива pred). Положить i = i + 1. Выполнить для каждой вершины, кроме вершин с неизменной меткой, следующие действия: 1) Положить M = min {label(v), label(u) + w (u, v)}. 2) Если M<label(v), то положить label(v) = M и pred(v) = u.

4. (Выделение вершин u_i.) Среди всех вершин, которые не помечены неизменной меткой, найти вершину w с наименьшей меткой. (Если таких вершин несколько, то выбор можно сделать произвольно.) Положить perm(w) = 1 и u_i = w (u_i = w, и она является последней вершиной с неизменной меткой.)

5. Если i < n — 1, то идти к шагу 3. Иначе halt. (Все кратчайшие пути найдены). Метки вершин представляют собой длины кратчайших путей. v, pred(v), pred (pred(v)), …, s есть вершины кратчайшего ориентированного s-v - пути.

Здесь label — это массив, в котором хранятся текущие метки вершин. Вершины становятся постоянно помеченными, когда они оказываются равными u_i для какого-либо i. Мы используем массив perm, чтобы указать, какие вершины постоянно помечены. Если perm(v) = 1, то v является постоянно помеченной вершиной. Отметим, что в таком случае метка v равна d (s, v). Вначале perm(s) = 1 и perm(v) = 0 для всех v<>s.

Pred - массив указателей на вершины, из которых осуществлен переход в вершины с неизменной меткой, то v, pred(v), pred (pred(v)), …, s есть вершины, составляющие кратчайший ориентированный путь из s в v.

Данный алгоритм работает также для решения задачи коммивояжера.

Задача коммивояжера

Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — странствующий торговец) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

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

Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

Непременным условием и единственным смыслом задачи коммивояжёра является поиск самого выгодного пути. Для этого необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения. Если мы не просчитали все пути в выбранном варианте решения, то мы не можем утверждать, что найденное решение самое выгодное. Что такое проверка решения? — это поиск ошибки в процессе решения или сверка полученного результата с заведомо правильным. Второй вариант временно отбрасываем, так как нет практического смысла в решении задачи, если уже есть решение (в свою очередь, использование ранее выполненного верного решения для части имеющейся задачи — способ уменьшить решение). В рамках данной работы не ставилось целью сравнение различных методов и способов решения, поэтому принимаем, что проверяющий также считает выбранный способ решения оптимальным и проверяет его на правильность. Что нужно сделать проверяющему? — повторить работу, проделанную при решении, в полном объёме для поиска ошибки на каждом этапе решения. Если будет найдена ошибка, то проверяющему будет необходимо продолжить процесс решения для поиска более выгодного маршрута. Таким образом, мы получаем, что проверка решения задачи коммивояжёра равна или больше самого решения.

Представление в виде графа.

Симметричная задача для четырёх городов.

Для возможности применения математического аппарата для решения проблемы, её следует представить в виде математической модели. Проблему коммивояжёра можно представить в виде модели на графе, то есть, используя вершины и ребра между ними. Таким образом, вершины графа соответствуют городам, а ребра (i, j) между вершинами i и j — пути сообщения между этими городами. Каждому ребру (i, j)>=0 можно сопоставить критерий выгодности маршрута, который можно понимать как, например, расстояние между городами, время или стоимость поездки. Маршрутом (также гамильтоновым маршрутом) называется маршрут на таком графе, в который входит по одному разу каждая вершина графа. Задача заключается в отыскании кратчайшего маршрута.

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

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

Пример решения задачи коммивояжера на языке python на заданном графе (Рис. 3.2).

В листинге 2 приводится скрипт для решения данной задачи.

Данный скрипт находит самый «выгодный» путь от вершины 1 до вершины 4.

Листинг 2.

import networkx as nx

import matplotlib. pyplot as plt

import numpy

G = nx. Graph ();

for i in range (1,6):

G.add_node (i)

G.add_edge (1, 2, node_color = 'm', weight = 2) # Параметр weight задает вес ребра

G.add_edge (1, 3, node_color = 'm', weight = 1)

G.add_edge (1, 4, node_color = 'm', weight = 20)

G.add_edge (1, 5, node_color = 'm', weight = 10)

G.add_edge (1, 6, node_color = 'm', weight = 15)

G.add_edge (5, 4, node_color = 'm', weight = 1)

G.add_edge (1, 6, node_color = 'm', weight = 10)

G.add_edge (6, 1, node_color = 'm', weight = 4)

G.add_edge (2, 3, node_color = 'm', weight = 10)

G.add_edge (2, 5, node_color = 'm', weight = 5)

G.add_edge (2, 6, node_color = 'm', weight = 20)

G.add_edge (3, 6, node_color = 'm', weight = 6)

G.add_edge (4, 2, node_color = 'm', weight = 15)

G.add_edge (4, 3, node_color = 'm', weight = 40)

G.add_edge (5, 6, node_color = 'm', weight = 10)

G.add_edge (3, 5, node_color = 'm', weight = 3)

nx.draw (G) #Отрисовка графа

plt.show ()

adjacency_matrix = nx. adjacency_matrix (G)

print ('Матрица стоимости')

print (adjacency_matrix) #Вывод матрицы весов

print (nx.shortest_path (G, 1, 4)) #Вывод самого короткого пути

print (nx.dijkstra_path (G, 1, 4)) #Вывод самого «выгодного» пути Выходные данные:

[1,4] - Кратчайший путь

[1,3,5,4] - Выгодный путь

Задача о назначениях.

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

В наиболее общей форме задача формулируется следующим образом:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

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

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

Задачу о назначениях можно сделать более гибкой. В вышеприведенном примере могут оказаться не три, а четыре свободных такси, но заказчика, по-прежнему, три. Можно назначить четвертую задачу, которую можно назвать «сиди тихо, ничего не делай», с ценой 0 для машины, которой она назначается. Задача может быть решена обычным методом и снова даст наилучшее решение.

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

6. Венгерский алгоритм

Венгерский алгоритм — алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время. Он был разработан и опубликован Харолдом Куном (англ.) в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари (англ.)).

Джеймс Манкрес (англ.) в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна — Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была O(n⁴), однако Эдмондс (англ.) и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения O(n³). Форд и Фалкерсон (англ.) распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни.

Постановка задачи.

Дана неотрицательная матрица размера nЧn, где элемент в i-й строке и j-ом столбце соответствует стоимости выполнения j-ого вида работ i-м работником. Нужно найти такое соответствие работ работникам, чтобы расходы на оплату труда были наименьшими. Если цель состоит в нахождении назначения с наибольшей стоимостью, то решение сводится к решению только что сформулированной задачи путём замены каждой стоимости C на разность между максимальной стоимостью и C.

Матричная интерпретация алгоритма

Для n работников и работ, дана матрица nЧn (матрица стоимости), задающая стоимость выполнения каждой работы каждым работником. Найти минимальную стоимость выполнения работ, такую что каждый работник выполняет ровно одну работу, а каждую работу выполняет ровно один работник.

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

Прежде всего запишем задачу в матричной форме:

где a, b, c, d — работники, которые должны выполнить работы 1, 2, 3, 4. Коэффициенты a1, a2, a3, a4 обозначают стоимость выполнения работником «a» работ 1, 2, 3, 4 соответственно. Аналогичный смысл имеют остальные символы. Матрица квадратная, поэтому каждый работник может выполнить только одну работу.

Шаг 1

Уменьшаем элементы построчно. Находим наименьший из элементов первой строки (а1, а2, а3, а4), и вычитаем его из всех элементов первой строки. При этом хотя бы один из элементов первой строки обнулится. То же самое выполняем и для всех остальных строк. Теперь в каждой строке матрицы есть хотя бы один ноль. Иногда нулей уже достаточно, чтобы найти назначение. Пример показан в таблице. Красные нули обозначают назначенные работы.

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

Шаг 2

Часто на первом шаге нет назначения, как, например, в следующем случае:

Задача 1 может быть эффективно (за нулевую стоимость) выполнена как работником a, так и работником c, зато задача 3 не может быть эффективно выполнена никем.

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

Шаг 3

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

Если работник d выполняет работу 2, некому выполнять работу 3, и наоборот.

В таких случаях мы выполняем процедуру, описанную ниже.

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

Отметим все строки без назначений (строка 1). Отметим все столбцы с нулями в этих строках (столбец 1). Отметим все строки с «красными» нулями в этих столбцах (строка 3). Продолжаем, пока новые строки и столбцы не перестали отмечаться.

Теперь проводим линии через все отмеченные столбцы и неотмеченные строки.

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

Шаг 4

Из непокрытых линиями элементов матрицы (в данном случае это a2', a3', a4', c2', c3', c4') найти наименьший. Вычесть его из всех не отмеченных строк и прибавить ко всем пересечениям отмеченных строк и столбцов. Так, например, если наименьший элемент из перечисленных равен а2', мы получим

Повторять процедуру (шаги 1−4) до тех пор, пока назначение не станет возможным.

Реализация на python.

В листинге 3 приводится пример реализации решения примера, описанного выше, на языке программирования python.

Листинг 3.

def improveLabels (val):

««» change the labels, and maintain minSlack.

«««

for u in S:

lu[u] -= val

for v in V:

if v in T:

lv[v] += val

else:

minSlack[v] -= val

def improveMatching (v):

««» apply the alternating path from v to the root in the tree.

«««

u = T[v]

if u in Mu:

improveMatching (Mu[u])

Mu[u] = v

Mv[v] = u

def slack (u, v): return lu[u]+lv[v] - w[u] [v]

def augment ():

««» augment the matching, possibly improving the lablels on the way.

«««

while True:

# select edge (u, v) with u in S, v not in T and min slack

((val, u), v) = min ([(minSlack[v], v) for v in V if v not in T])

assert u in S

if val>0:

improveLabels (val)

# now we are sure that (u, v) is saturated

assert slack (u, v)==0

T[v] = u # add (u, v) to the tree

if v in Mv:

u1 = Mv[v] # matched edge,

assert not u1 in S

S[u1] = True #… add endpoint to tree

for v in V: # maintain minSlack

if not v in T and minSlack[v] > slack (u1, v):

minSlack[v] = [slack (u1, v), u1]

else:

improveMatching (v) # v is a free vertex

return

def maxWeightMatching (weights):

««» given w, the weight matrix of a complete bipartite graph,

returns the mappings Mu: U->V, Mv: V->U encoding the matching

as well as the value of it.

«««

global U, V, S, T, Mu, Mv, lu, lv, minSlack, w

w = weights

n = len (w)

U = V = range (n)

lu = [max ([w[u] [v] for v in V]) for u in U] # start with trivial labels

lv = [0 for v in V]

Mu = {} # start with empty matching

Mv = {}

while len (Mu)

free = [u for u in V if u not in Mu] # choose free vertex u0

u0 = free[0]

S = {u0: True} # grow tree from u0 on

T = {}

minSlack = [[slack (u0, v), u0] for v in V]

augment ()

# val. of matching is total edge weight

val = sum (lu)+sum (lv)

return (Mu, Mv, val)

# a small example

#print maxWeightMatching ([[1,2,3,4], [2,4,6,8], [3,6,9,12], [4,8,12,16]])

# read from standard input a line with n

# then n*n lines with u, v, w[u] [v]

n = 3 #Размер матрицы

w = [[1, 2, 4], #Матрица весов

[2, 5, 3],

[6, 7, 8]]

print (maxWeightMatching (w))

Входные данные:

n = 3 #Размер матрицы

w = [[1, 2, 4], #Матрица весов

[2, 5, 3],

[6, 7, 8]]

Выходные данные:

({0: 2, 1: 1, 2: 0}, {0: 2, 1: 1, 2: 0}, 15)

Вывод

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

1. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984

2. Хаггарти Р. Дискретная математика для программистов Москва: Техносфера, 2003 г. — 320 с.

3. Википедия — свободная общедоступная мультиязычная универсальная интернет-энциклопедия, реализованная на принципах Вики. / http://wikipedia.org (Дата обращения 23.12.2013)