Теория графов. 02 Теория графов. 2. теория графов общие понятия теории графов
 Скачать 1.41 Mb.
|
|
Паросочетания Как было сказано выше, паросочетанием называется произвольное подмножество попарно несмежных ребер двудольного графа. Пример Для графа, изображенного на рис. 2.30, паросочетанием будет, например, множество { } { } { } { } 10 4 9 2 8 1 , , , , , v v v v v v 39 Рассмотрим ) , ( X V G = – двудольный граф, 2 1 V V V U = , где ∅ = 2 1 V V I , Пусть 2 1 V V ≤ , тогда введем понятие совершенного паросочетания. Определение. Паросочетание будет совершенным, если в подмножество попарно несмежных ребер вошли все вершины множества 1 V . Пример Для графа, приведенного на рис. 2.30, совершенным паросочетанием будет, например, множество { } { } { } { } { } 10 4 8 3 9 2 6 1 , , , , , , , v v v v v v v v Рис. 2.30. Двудольный граф с совершенным паросочетанием С совершенными паросочетаниями связано много прикладных задач, например задача о составлении расписаний, задача о назначении на должность. Пусть 1 V – множество должностей, 2 V – множество претендентов, ребро { } X v v j i ∈ , , если i -ю должность может занимать j -й претендент, тогда назначение претендентов на должности есть построение совершенного паросочетания. Построить совершенное паросочетание удается не всегда (рис. 2.31). Критерий существования совершенного паросочетания сформулировал и доказал Холл в 1935 г., он известен как теорема Холла , в основе которой лежит задача о свадьбах. Пусть есть m юношей и n девушек, n m < . Каждый из юношей знаком с какими-то девушками. Спрашивается, всегда ли можно женить этих юношей на знакомых им девушках? 40 Рис. 2.31. Двудольный граф без совершенного паросочетания На языке теории графов задачу можно сформулировать так: пусть ) , ( X V G = – двудольный граф, 2 1 V V V ∪ = , где ∅ = ∩ 2 1 V V , где { } m b b b V ,... , 2 1 1 = – множество юношей, { } n g g g V ,... , 2 1 2 = – множество девушек, если i -й юноша знаком с j -й девушкой, то существует ребро { } j i g b , . Женить всех юношей на знакомых им девушках означает построить совершенное паросочетание в графе. Решение задачи о свадьбах существует тогда и только тогда, когда любые k юношей из m знакомы в совокупности не менее чем с k девушками ( ) m k ,... 2 , 1 = Замечание. Если m k = , то это означает, что любая группа k юношей числом меньше m знакома не менее чем с 1 + k девушкой и только ровно m юношей знакомы с m девушками. Тогда берем любого юношу, женим на знакомой девушке. Остается 1 − m юноша, из которых любые k знакомы не менее чем с k девушками. Теорема Холла.Построить совершенное паросочетание в графе можно тогда и только тогда, когда любые k вершин множества 1 V смежны в совокупности не менее чем с k вершинами множества 2 V . Для графа на рис. 2.31 условие теоремы Холла не выполняется: вершины 2 v и 4 v смежны только с одной вершиной 8 v . 41 Сети и потоки Сеть можно представить как систему, транспортирующую некий продукт из одной точки в другую (электроэнергия, природный газ, нефть и др.). Рассмотрим сеть как орграф, дуги которого – трубы между точками системы (вершинами графа). Положительное число, соответствующее каждой дуге графа, называется пропускной способностью. Если между двумя вершинами не существует дуги, то пропускная способность равна нулю. В примере с нефтяными сетями пропускная способность связана с количеством нефти, проходящей через трубу (дугу). Наличие петель у графа недопустимо, поскольку рассматриваемые задачи связаны только с транспортировкой продукта между различными точками. Будем считать, что если существует дуга из v i в v j , то нет дуги из v j в v i . Таким образом, рассматривается поток продукта только в одну сторону. Рассмотрим также особую вершину a, называемую источником, и особую вершину z, называемую стоком. Полустепень захода вершины a равна 0, так что в источник ничто не втекает. Полустепень исхода вершины z равна 0, так что из стока ничто не вытекает. Таким образом, продукт перевозится из a в z. Для сети вводится понятие потока: для каждой дуги имеется значение, которое является потоком через конкретную дугу. Очевидно, величина потока не может превышать пропускную способность дуги. Требуется также, чтобы поток, входящий в вершину, был равен потоку, выходящему из вершины, за исключением вершин a и z. Данное правило называется сохранением потока Определение. Орграф, в котором каждая дуга имеет положительную пропускную способность и поток, называется транспортной сетью Дуга называется насыщенной, если ее поток равен ее пропускной способности. 42 Пример На рис. 2.32 показан пример потока в сети, где первый элемент на каждой дуге – пропускная способность, а в скобках – поток. Рис. 2.32. Пример сети Определение. Разрез графа – это такая пара множеств вершин (V 1 ,V 2 ), что V= V 1 ∪V 2 , ∅ = ∩ 2 1 V V , 1 V a ∈ , 2 V z ∈ . Величиной разреза называется сумма пропускных способностей таких дуг (v i , v j ), что 1 V v i ∈ , 2 V v j ∈ Минимальный разрез – разрез с минимальной пропускной способностью. Теорема Форда–Фалкерсона.Величина максимального потока в графе равна величине пропускной способности его минимального разреза. Доказательство(достаточность). Любой поток между вершинами v i и v j меньше или равен величине любого сечения. Пусть дан некоторый поток и некоторое сечение. Величина данного потока складывается из величин продуктов, перевозимых по всем возможным путям из вершины v i в v j . Каждый такой путь обязан иметь общую дугу с данным сечением. Так как по каждой дуге сечения суммарно нельзя перевести продукта больше, чем его пропускная способность, поэтому сумма всех грузов меньше или равна сумме всех пропускных способностей дуг данного сечения. Отсюда следует, что любой поток меньше или равен величине минимального сечения, а значит и максимальный поток меньше или равен величине минимального сечения. На этой теореме основан алгоритм Форда–Фалкерсона поиска максимального потока в графе, он же является доказательством необходимости данной теоремы, то есть оно является конструктивным. 43 2.7. Некоторые алгоритмы теории графов 2.7.1. Выделение компонент сильной связности орграфа С помощью матрицы смежности найти компоненты сильной связности орграфа D. Cоставляем матрицу смежности A(D) для данного орграфа. Как было сказано выше, она состоит из нулей и единиц, номера строк – индексы вершин, из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят. Если есть дуга, исходящая из вершины v i и входящая в v j , то элемент матрицы смежности, стоящий на пересечении i-й строки и j-го столбца, равен 1, иначе – 0. Для выделения компонент сильной связности необходимо сначала найти матрицу достижимости T(D) орграфа по первой формуле утверждения 3, затем матрицу сильной связности S(D) (она должна быть симметрической) по второй формуле из того же утверждения. Алгоритм выделения компонент сильной связности 1. Присваиваем p = 1 (p – количество компонент сильной связности), ) ( 1 D S S = 2. Включаем во множество вершин V p компоненты сильной связности D p вершины, соответствующие единицам первой строки матрицы S p . В качестве матрицы A(D p ) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V p 3. Вычеркиваем из S p строки и столбцы, соответствующие вершинам из V p . Если не остается ни одной строки (и столбца), то p – количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как S p+1 , присваиваем p = p + 1 и переходим к пункту 2. 44 Пример Выделим компоненты сильной связности орграфа, изображенного на рис. 2.33. Рис. 2.33. Пример орграфа для нахождения компонент сильной связности n= 5, значит, матрица смежности 5×5 и будет выглядеть так = 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 ) (D A По формуле из утверждения 3 найдем матрицу достижимости T (D): [ ] = 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 ) ( sign 2 D A , [ ] = 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 ) ( sign 3 D A , [ ] = 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 ) ( sign 4 D A 45 Следовательно, + + + = 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 sign ) (D T = + + 1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 Таким образом, матрица S(D), также полученная из утверждения 3, будет следующей: = = 1 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 & 1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 ) (D S Присваиваем p = 1, ) ( 1 D S S = и составляем множество вершин первой компоненты сильной связности D 1 : это вершины, которым соответствуют единицы в первой строке матрицы S(D). Таким образом, первая компонента сильной связности состоит из одной вершины { } 1 1 v V = Вычеркиваем из матрицы S 1 (D) строку и столбец, соответствующие вершине v 1 , и получаем матрицу S 2 (D): = 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 ) ( 2 D S 46 Присваиваем p = 2. Множество вершин второй компоненты связности составят вершины, которым соответствуют единицы в первой строке матрицы S 2 (D), т. е. { } 4 3 2 2 , , v v v V = Составляем матрицу смежности для компоненты сильной связности 2 D исходного графа D – в ее качестве возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из V 2 : = 0 1 0 0 0 1 1 0 0 ) ( 2 D A Вычеркиваем из матрицы S 2 (D) строки и столбцы, соответствующие вершинам из V 2 , и получаем матрицу S 3 (D), которая состоит из одного элемента: ( ) 1 ) ( 3 = D S , и присваиваем p = 3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины { } 5 3 v V = Таким образом, выделены три компоненты сильной связности орграфа D (рис. 2.34). D 1 : D 2 : D 3 : Рис. 2.34. Компоненты сильной связности 2.7.2. Расстояния в орграфе Найти расстояния в орграфе D: диаметр, радиус и центры, а также с помощью алгоритма фронта волны найти минимальный путь из вершины v в w. Пусть ) , ( X V D = орграф с n ≥ 2 вершинами и v,w (v ≠ w) – заданные вершины из V. Для нахождения метрических характеристик графа необходимо составить матрицу минимальных расстояний M(D)= [m ij ]. Это квадратная матрица размерности n n × , элементы главной диагонали которой равны нулю ( 0 = ii m , i= 1,..,n). Для заполнения остальных 47 элементов составляем матрицу A(D) и переносим единицы из нее в матрицу M(D) ( ij ij a m = , если 1 = ij a ). Далее построчно заполняем матрицу следующим образом. Рассматриваем первую строку матрицы M(D), в которой есть единицы, пусть это элемент 1 = ij m . Значит, из вершины i v можно попасть в вершину j v за один шаг. Рассматриваем j-ю строку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент 1 = jk m . Тогда из вершины i v в вершину k v можно попасть за два шага. Таким образом, можно записать в матрицу M(D) 2 = ik m Следует заметить, что если в рассматриваемых строках две или более единиц, то необходимо прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу M(D) длину наикратчайшего из них. После заполнения матрицы M(D) применяются формулы подглавы 2.5 для нахождения диаметра, эксцентриситета, центров и радиуса графа. Алгоритм фронта волны 1. Помечаем вершину v индексом 0, затем помечаем вершины ∈ образу вершины v индексом 1. Обозначаем их FW 1 (v). Полагаем k= 1. 2. Если ∅ = ) (v FW k или k = n – 1 и одновременно ) (v FW w k ∉ , то вершина w не достижима из v. Работа алгоритма заканчивается. В противном случае продолжаем. 3. Если ) (υ ∉ k FW w , то переходим к пункту 4. В противном случае мы нашли минимальный путь из v в w и его длина равна k. Последовательность вершин ), ( ) ( ), ( ) ( ), ( ) ( где , 2 1 1 1 1 1 2 2 1 1 1 1 3 2 1 w D v FW w w D v FW w w D v FW w w w w w vw k k k k k k − − − − − − − − − ∩ ∈ ∩ ∈ ∩ ∈ есть этот минимальный путь. Работа завершается. |