В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

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

Дискретная математика (Конспекты 15 лекций)

Страница 9

Г-1(V) – множество вершин, из которых можно попасть в вершину V, пройдя только по одному ребру.

Алгоритм.

1. Исходной вершине A присваиваем метку 0.

2. Любому Г(А), которые еще не имели меток, присваиваем метку М = 1.

3. Для любой V, принадлежащей Г(А) находим Г(V) и любой V, принадлежащему Г(V), если она не имела метку, даем метку 2.

4. И так далее до тех пор, пока конечная вершина не получит метку.

5. Выбираем путь по Г-1(V).

Может произойти такое, что пути из А в В нет вообще.

Тогда на некотором шаге при обратном ходе нужной вершины нет.

Вторая задача.

Если каждому ребру поставить в соответствие некоторое целое положительное число, называемое его длиной и требуется найти путь из А в В, такой, что i = minimum. (r или l – длина ребра)

Алгоритм будет следующий.

1. Метка для ребра А l1 = 0

Для Vi li = +(бесконечность) – очень большое число, большее суммы всех длин ребер всего графа.

L(Vi, Vj) – длина ребра, идущего из вершины Vi в Vj. Направление важно.

2. Для любого ребра из графа проверяем выполнение неравенства.

lj - li > L(Vi, Vj) *

Если это неравенство выполняется, то меняем метку lj на новую.

lj = li + L(Vi, Vj) и так до тех пор, пока выполняется *.

Если * нигде не выполняется, то та метка, которая будет стоять у вершины В и будет равна длине минимального пути из А в В, а сам путь строится движением назад из В в А.

Г-1(В) Существует такое ребро Vi1, для которого выполнено равенство.

lb - li1 = L(Vi1,B)

Затем Г-1(V1) Существует V2, где l(V1) - l(V2) = L(V1, V2) и т.д. пока не вернемся в вершину А.

Путь минимальной длины найден.

Остов графа минимальной длины.

Остов – дерево, содержащее все вершины графа и какие-то из его ребер.

Если каждому ребру графа поставлена в соответствие его длина, то требуется найти такой остов, сумма длин ребер которого минимальна.

Алгоритм

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

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

Остов минимальной длины найден.

Лекция 14

Парное сочетание (паросочетание) двудольных графов

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

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

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

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S.

Теорема Холла (без доказательства)

Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].

Венгерский алгоритм нахождения максимального паросочетания.

Дан двудольный граф. Все определения для графа справедливы.

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

1. Перебираем все ребра в любом порядке. Все несмежные ребра включаем в паросочетание.

Ребра, входящие в полное паросочетание, будем называть толстыми. Остальные ребра считаем тонкими.

Вершины, которые соединены толстыми ребрами – насыщенные. Остальные – ненасыщенные.

Чередующейся цепью называется цепь, в которой тонкие и толстые ребра чередуются.

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

1. Находим полное паросочетание.

2. Для этого паросочетания ищем тонкую цепь. Если ее нет, то данное паросочетание максимально и алгоритм закончен.

3. Если же она существует, то проводим перекраску ребер.

4. Толстые ребра тонкой цепи делаем тонкими, а тонкие – толстыми.

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

6. Переходим на шаг 2.

Количество ребер в новом паросочетании увеличится на 1.

Максимальное паросочетание (МПС) найдено.

Совершенное ПС – МПС обязательно.

Матрицы смежности двудольных графов.

A(M,N)

[V] = M

[W] = N

Aij = 1, если есть ребро ViWj

Если его нет, то Aij = 0.

Чтобы найти полное паросочетание, нужно найти единицы, которые находятся в разных строках и разных столбцах.

Алгоритм – тот же самый.

При поисках мы можем двигаться по строкам и на углы в 90 градусов.

Алгоритм оптимального назначения

Есть m работников и m работ.

Каждый из работников выполняет каждую работу с определенной эффективностью.

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

A = (aij) – матрица эффективности.

А(М*М)

А =

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

Дан двудольный полный граф с V = M, W = M

Даны длины ребер.

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

Алгоритм.

 

0

0

0

0

4

1

2

3

4

4

1

4

4

2

6

2

5

6

3

6

1

6

4

4

1. Всем вершинам Vi даем метку аi = max по всем элементам нужной строки.

По всем j присваиваем метку 0.

2. Ищем ребра, для которых выполняется условие

Ai + Bj = Aij

Строим граф, в который входит все вершины исходного графа и найденные ребра.

3. В построенном графе ищем максимальное паросочетание. Если найденное паросочетание совершенно, то алгоритм закончен. Если нет, то переходим дальше.

4. Из теоремы Холла существует подмножество S из V, [S] > ф(S).

Ищем это подмножество.

Для каждой вершины Vi из S метку Ai уменьшают на 1, а для wj из ф(s) метку Vj увеличивают на 1.

5. Переходим на начало шага 2 с новыми значениями меток.

Лекция 15

Потоки в транспортных сетях

Введем обозначения

1 2 3 4 5 6 7 8 [9] 10

скачать реферат скачать реферат

Новинки
Интересные новости


Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2019 textreferat.com