ответы мат методы (1). По предмету математические методы

• Название: По предмету математические методы
• Дата: 07.02.2023
• Размер: 426 Kb.
• Имя файла: ответы мат методы (1).doc
• Тип: Решение; #923726
• страница: 4 из 5

20. Определение паросочетаний в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе.

Пусть Г = [А,В] – граф и S  D – некот-е множ-во ребер в нем. Множество S назыв-ся паросочетанием, если любые два ребра из него не имеют общей вершины. Множ-во из одного ребра тоже будет назыв-ся паросочетанием, как и всякое пустое множ-во. Паросочетание называется максимальным, если к нему нельзя добавить ни одного ребра так, чтобы снова получ-сь паросочет-е. Паросочетание назыв-ся наибольшим, если оно состоит из наиб-го возможного колич-ва ребер. Очевидно, каждое наибольшее паросочетание явл. максимальным; обратное неверно.

Пример:


здесь красные ребра – максим-е, но не наибол-е паросочетание, а черные ребра – наибольшее паросочетание. Графы можно представлять матрицами. Матричные представления графов использ-ся при решении прикладных задач, особенно в тех случаях, когда при моделировании предметной области применяются алгебраические доказательства. Поиск наибольшего паросочетания в графе представляет собой классическую алгоритмическую задачу. Далее будет рассматриваться пример решения такой задачи для графов частного вида – графов двудольных. Граф Г = [А,В] называется двудольным, если его множество вершин А можно представить в виде объединения двух его непустых подмножеств А₁, А₂ без общих элементов так, что любое ребро из В будет иметь один конец в А₁, а другой конец – в А₂. таким образом, нет ни одного ребра, которое соединяло бы вершины из А₁ или соединяло бы вершины из А₂. Если считать, что А₁ = {x₁,…,x_r}, А₂ = {y₁,…,y_r}, то двудольный граф можно описать не только матрицей смежностей, но и матрицей двудольного графа: эта матрица – размером rs и если обозначать ее общий элемент через m_ij. Ясно, что такая матрица описывает граф однозначно, хотя является намного меньше по объему, чем матрица смежностей графа в этом случае. Когда множество А₁ состоит из n вершин, а множество А₂ состоит из mвершин и в двудольном графе проведены все возможные ребра, то говорят, что двудольный граф Г = [А,В] является полным двудольным графом и обозначают его символом K_m,n. Далее описан алгоритм выбора наибольшего паросочетания в двудольном графе, опираясь на только что введенное понятие матрицы двудольного графа. Шаг 0. По матрице М = (m_ij),i = 1,…, p, j = 1, 2,…, pданного двудольного графа строим рабочую таблицу: она представляет собой матрицу тех же размеров, в клетку с номером (ij) поместим символ «» и назовем ее недопустимой, если в матрице двудольного графа m_ij = 0; если же m_ij = 1, то в клетку рабочей таблицы не запишем ничего и назовем такую клетку допустимой. Слева от рабочей таблицы расположим для удобства номера ее строк, а сверху над таблицей расположим номера ее столбцов. Шаг 1. Просмотрим слева направо первую строку и в первую же допустимую клетку первой строки поставим символ «1». Если в первой строке все клетки недопустимы, то перейдем ко второй строке и в первую же (при просмотре слева направо) допустимую клетку поставим «1». Если же нет допустимых клеток и во второй строке, то проставим указанным выше способом «1» в третьей строке. Если окажется, что во всей табл-е все клетки недоп-мы, то на этом все действия заканчиваются и выдается ответ: «в графе нет ребер». Если же все-таки удастся поставить первую «1», то после этого просмотрим все остал-е строки таблицы в порядке возрастания их номеров. В каждой очередной строке просматриваем ее клетки слева направо и фиксируем первую по ходу просмотра допустимую клетку такую, кот-я является незав-й по отношению к допустимым клеткам, в которых уже стоит символ «1», и проставляем в эту клетку «1», после чего переходим у тем же действиям в следующей строке. Если в строке такой клетки не окажется, то переходим к следующей строке и выполняем в ней ту же проверку. Фиксируем набор ребер в графе, соответствующих проставл-м в таблице символам «1». (Под ребром, соответствующим символу «1»в рабочей таблице, подразумевается следующее: если «1» стоит в клетке с номером (ij), то соответствующим будет ребро (x_i, y_j)). Легко заметить, что этот набор ребер – максим-е парос-е. Если в рез-те проведения всех действий по этому шагу в каждой строке рабочей таблицы окажется символ «1», то ребра из указанного только что паросочетания и составляют наибол-е паросочетание, и действия окончены. Если же в резул-те проведения первого шага остались строки без «1», то пометим их справа от таблицы символом «-». Переходим к следующему шагу. Шаг 2. Просмотрим все помеченные строки в порядке возрастания их номеров. Просмотр очередной строки состоит в следующем: в строке отыскивают допустимые клетки, и столбцы, в которых эти клетки расположены, помечаются номером просматр-й строки. При этом соблюдается принцип (): если пометка уже стоит, то на ее место вторая не ставится. Пометки, о которых только что было сказано, физически выставляются внизу, под таблицей. Если в резул-те этого шага ни один из столбцов не будет помечен, то это означает, что уже имеющ-ся паросоч-е (полеченное на Шаге 1) явл-ся искомым большим и все действия прекращ-ся. Если же среди столбцов появятся помеченные, то переходим к следующему шагу. Шаг 3. Просмотрим помеченные столбцы в порядке возрастания их номеров. Просмотр столбца состоит в следующем: в столбце отыскив-ся символ «1» и строка, в кот-й он расп-н,. Помечается номером просматр-го столбца. Физически пометки выставляются справа от таблицы, на уровне соответствующих строк. Всегда соблюдается принцип (). Если в резул-те действий по этому шагу возникнет ситуация, когда в просматриваемом столбце нет символа «1», то действия на данном шагу прерываются и надо перейти к следующему шагу – Шагу 4. если же в результате действий по этому шагу будут просмотрены все помеченные ранее столбцы и, тем самым, возникнет набор помеченных строк (они будут помечены символом «-», другие – номерами столбцов), то следует вернуться к Шагу 2 и повторить предусмотренные им действия. Если в результате этих действий по Шагу 2 не возникнет новых помеченных столбцов, то это означает, что имеющееся паросочетание является искомым и процесс останавл-ся. Если же среди помечаемых столб-в возникнут новые помеч-е столбцы, то следует повторить Шаг 3 с новым набором помеченных столбцов. Если в результате этих действий не возникнет новых помеч-х строк, то это означает,. Что имеющ-ся паросочетание явл-ся искомым. Шаг 4. Рассматр-ся столбец, имеющий пометку и не содержащий символа «1». Мы сейчас изменим набор символов «1», располож-х в рабочей таблице. В рассматр-й столбец поставим символ «1» в строку, номер кот-й равен пометке этого столбца. Затем в этой строке отыщем «старый» символ «2» и переместим его по его столбцу в строку, номер которой равен пометке при этом столбце (описанное действие всегда осуществимо). Затем в строке, куда попал последний символ «1» отыщем «старый» символ «1» и с ним проделаем то же самое. В итоге очередной перемещаемый «старый» символ «1» окажется в строке, где больше символов «1» нет. Возник новый набор символов «1», в котором уже элементов на один больше, чем в исходном наборе символов «1». По этому новому набору можно построить паросочетание так же, как это делалось в самом начале и после этого повторить все сначала. В итоге возникает из указанных выше условий прекращения действий по алгоритму и наибольшее паросочетание будет найдено.

22. Методы хранения графов в памяти ЭВМ. Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения кратчайших маршрутов.

В ЭВМ удобно представлять графы в виде матриц смежнотей: если направление ребра противоположено, то в матрицу составим (-1). Графом называется пара множеств Г=[А,В], где А – любое непустое множество, а В – множество, которое является подмножеством множества V(A). Элементы из А называются вершинами графа, а элементы из В – его ребрами. Например, А={1,2,3,4,5}, В={(1,2),(2,3),(3,4),(1,5),(1,4),(3,1)}. Неупорядоченная пара вершин – ребро, а упорядоченная пара – дуга. дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s принад-т x до заданной конечной вершины, при условии, что такой путь существует t принад-т R(s (здесь R(s)-множество, достижимое из вершины s.) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi- некоторая его вершина, то, двигаясь от s к х_i, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым ( ) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса. Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и многого другого. Кратчайший путь рассматривается при помощи математического объекта – графа. Граф задается множеством точек (вершин) и множеством линий (ребер), соединяющих все или часть этих точек. Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути: 1) алгоритм Дейкстры. Используется для нахождения оптимального маршрута между двумя вершинами. 2) алгоритм Флойда. Используется для нахождения оптимального маршрута между всеми парами вершин. 3) алгоритм Форда. Используется для нахождения оптимального маршрута между двумя вершинами. Для заданной начальной вершины s необходимо найти кратчайшие пути между s и всеми другими вершинами х_i X. Необходимо найти кратчайшие пути между всеми парами вершин. Самый распространенный пример подобных задач, это нахождение кратчайшего расстояния между двумя вершинами. В этом случае, весом дуги (х_i, х_j) будет являться расстояние между вершинами хi и хj, ну, а если такая дуга отсутствует, то ее вес полагается равным бесконечности. Существует классический алгоритм Форда поиска кратчайших путей в графе. Основан он на следующем простом факте: если имеется кратчайший путь между какими-либо двумя вершинами, то его часть между любыми двумя вершинами на нем же самом также является кратчайшем путем. Алгоритм Форда позволяет найти кратчайшие пути из какой-либо одной вершины графа во все остальные. Эту исходную вершину можно выбрать произвольно, но, сделав выбор, далее уже исходить из того, что будут описаны кратчайшие пути именно из этой вершины во все остальные. Шаг0. Занумеруем все вершины из Г=[А, В], так что А={1,2,…,p} и при этом номер «1» имеет именно та вершина, из которой будут найдены кратчайшие пути во все остальные вершины. Рассмотрим матрицу М=(m_ij), i, j=1,2, …,p, положив


Шаг1. Около первой строки матрицы М, слева от матрицы, поставим числовую пометку «0» и такую же пометку проставим над первым столбцом матрицы. Затем проставим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и суму проставим над столбцом, в котором эта клетка находится. Отразим пометки столбцов относительно главной диагонали. С каждой из помеченных строк проделаем тоже самое: просмотрим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и сумму поставим в качестве пометки над столбцом, в котором эта клетка стоит. При этом будем соблюдать принцип: «имеющуюся пометку не менять». Пометки столбцов отразим относительно главной диагонали и с помеченными строками вновь проделаем то же самое. И так далее, пока не окажутся помеченными все строки и все столбцы. Шаг2. Просмотрим строки таблицы в порядке возрастания их номеров. В каждой строке просматриваются клетки слева направо и всякий раз, когда встречается число, оно складывается с пометкой столбца, в котором найденное число расположено. Если сумма оказалась меньше, чем пометка столбца, то эта пометка столбца заменяется на упомянутую сумму. Если же сумма оказалась больше или равной пометке, то ничего не меняется. После такого просмотра всех строк новые пометки столбцов отражаются относительно главной диагонали и вся процедура повторяется. И так до тех пор пока не прекратятся какие то бы ни было изменения в пометках. Шаг3. Теперь по пометкам можно построить кратчайшие пути из первой вершины во все остальные. Фиксируем произвольную вершину k (k=2,3, …,p) и опишем кратчайший путь из первой вершины в вершину k. Во-первых длина этого кратчайшего пути равна пометке , стоящей над столбцом номер k. Во –вторых предпоследняя вершина в кратчайшем пути из первой вершины в вершину k находится так: в столбце номер k отыскиваем число, сумма которого с пометкой строки, в которой оно расположено, равна . Пусть номер строки, в которой найденное число оказалось, равен l, тогда предпоследней вершиной в кратчайшем пути из 1 в k будет вершина l, надо отыскивать как предпоследнюю в кратчайшем пути из 1 в l и так далее.
24. Ориентир-й граф и его графическая интерпретация. Локал-е степени. Матрица смежн-й. Ориентиров-е пути и связность в ориентир-м графе.

Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Графическая интерпретация графа. Пусть Г=[А,В] - некоторый граф и А={a₁,a₂,…,a_p}, B={b₁,b₂,…,b_q}. Фиксируем на плоскости произвольным образом p точек и произвольным образом дадим им в качестве имен имена вершин данного графа. В итоге на плоскости возникнут точки, обозначенные как a₁,a₂,…,a_p. Затем для каждой пары точек a_i,a_jтаких, что (a_i,a_j) є В, проведем отрезок прямой, соединяющий точки a_i, a_j. В результате таких действий возникнет некоторый рисунок, который и является геометрической интерпретацией графа. Замечание: одному и тому же графу соответствует много рисунков, которые могут быть его геометрическими интерпретациями. Если в некотором графе Г=[А,В], где А={a₁,a₂,…,a_p}, B={b₁,b₂,…,b_q} пара вершин a_i,a_jтакова, что (a_i,a_j) принадлежит В, то вершины a_i,a_j называются смежными, причем каждая из них называется инцидентной ребру (a_i,a_j), а ребро (a_i,a_j) называется инцидентным каждой из вершин a_i,a_j. Если вершина a_i и ребро b_j инцидентны, то пишут a_i є b_j. Количество ребер, инцидентных данной вершине а называется ее степенью или локальной степенью графа в вершине а; степень вершины а обозначается через d(a). Вершины со степенью 0 называются изолированными. В любом графе количество вершин нечетной степени обязательно четно. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные. Подграфом графа Г называется граф, в который входит лишь часть вершин графа Г вместе с дугами их соединяющими. Матрицей смежности M порядка n называется матрица, состоящая из чисел m_ij, равных сумме чисел ориентированных ребер, идущих из а_i в а_j (или чисел неориентированных ребер, соединяющих эти вершины). m[i,j]=1, вершина с номером i смежна с вершиной с номером j, или 0, вершина с номером i не смежна с вершиной с номером j. В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х₁ ,х₃) относится к дуге а₁. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а₆ в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.