Метод дробления шага 4 страница

Практический смысл имеет и задача ориентации графа. Здесь имеется в виду, что получающийся орграф — сильно ­связный. Тогда обеспечивается взаимная достижимость для любой пары вершин, причем в обе стороны. Это может означать, что в некотором, например, городе можно организовать одностороннее дорожное движение (все виды транспорта двигаются в одном направлении; «встречной полосы» в принципе нет). Оказывается, однако, не любой граф поддается такой ориентации. Необходимое и достаточное условие для этого — каждое ребро должно входить хотя бы в один цикл.

Задачи второй группы решаются на помеченных графах.

Вот некоторые из таких задач:

— минимальная связка;

— кратчайший путь;

— задача почтальона;

— задача коммивояжера;

— максимальный поток в сети;

— поток с минимальной стоимостью;

— транспортная задача с минимальной стоимостью;

— транспортная задача с минимальным временем.

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

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

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

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

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

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

Общие понятия. Граф определяется как пара (двойка) множеств — множество вершин W и множество ребер L: G = (W, L).

Вершины графа изображаются точками, ребра — линиями связи любой формы (граф — объект не геометрический, а топологический).

Количество вершин графа, т.е. мощность (количество элементов множества W, — это его порядок n: |W| = n.

Любой граф может быть однозначно задан с помощью матрицы смежности MS.

Свойства матрицы смежности:

— матрица квадратная порядка

— матрица бинарная (двоичная);

— на главной диагонали MS только нули (в графе не должно быть

петель);

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

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

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

Свойства матрицы инциденций:

— в общем случае матрица прямоугольная;

— матрица бинарная (0, 1);

— в каждой строке матрицы Ml ровно 2 единицы, они указывают инцидентные вершины; в свою очередь, строки указывают ребра, инцидентные соответствующим вершинам.

Удаляя вершины (не все) и ребра из некоторого графа, получают подграф. А сам граф именуется надграфом. Если вершины не удаляются, получают остовный подграф.

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

Степень вершины графа — количество прилежащих ребер.

Если все вершины имеют одинаковую степень, граф — регулярный такой-то степени.

Теорема о сумме степеней всех вершин графа. В символической форме: ,т.е., сумма эта равна удвоенному количеству ребер.

Теорема о количестве вершин нечетной степени: количество таких вершин имеет значение четного числа.

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

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

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

Маршрут в графе — это последовательность проходимых ребер и вершин.

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

Длин а маршрут а (пути) — это количество проходимых ребер.

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

Дерево — это связный ациклический граф.

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

Теорема о количестве маршрутов заданной длины: Количество маршрутов длины к из вершины w_i. в вершину w_j. определяется значением элемента i j к-й степени матрицы смежности, т.е. .

Теорема о количестве маршрутов доказывается по индукции (полная математическая индукция). На основе степеней матрицы смежности строится матриц а связности MSW. Это квадратная, порядка n, бинарная матрица, симметричная относительно главной диагонали.

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

Если граф несвязный, он распадается на компоненты связности.В случае, если компоненты связности — деревья, получается лес. Если к тому же это остовный подграф, то— остовный лес. Отдельные свойства связных графов — их эйлеровость и гамильтоновость («-ость» считаем допустимым элементом словообразования).

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

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

Планарные графы

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

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

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

Теорем а Эйлер а для связных планарных графов: |W|—|L|+|R| = 2 т.е. количество вершин минус количество ребер плюс количество областей есть величина постоянная (константа Эйлера Е), имеющая значение 2

Теорема Эйлера справедлива и в отношении правильных выпуклых многогранников: |W|—|L|+|G| =E =2 здесь G — множество граней.

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

Теорема Куратовского утверждает: граф планарный тогда и только тогда, когда в процессе выполнения операций элементарного стягивания он не содержит подграфов вида К₅ и К_3,3.

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

Ориентированные графы (орграфы)

Можно отметить два существенных отличия орграфов от обычных графов:

— ориентация ребер, которые становятся дугами (дуга — «ребро со стрелкой»);

— наличие петель.

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

Связность орграфов бывает троякая:

— слабая;

— односторонняя:

— сильная.

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

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

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

Задачи на графах

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

Все такие задачи можно условно разделить на две группы:

— маршруты, деревья и т.п.;

— задачи с мерой.

В первой группе:

— отыскание пути (маршрута) в лабиринте;

— проверка графа на эйлеровость;

— построение остовного дерева для связного графа;

— ориентация графа;

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

Практический смысл имеет и задача ориентации графа. Здесь имеется в виду, что получающийся орграф — сильно ­связный. Тогда обеспечивается взаимная достижимость для любой пары вершин, причем в обе стороны. Это может означать, что в некотором, например, городе можно организовать одностороннее дорожное движение (все виды транспорта двигаются в одном направлении; «встречной полосы» в принципе нет). Оказывается, однако, не любой граф поддается такой ориентации. Необходимое и достаточное условие для этого — каждое ребро должно входить хотя бы в один цикл.

Задачи второй группы решаются на помеченных графах.

Вот некоторые из таких задач:

— минимальная связка;

— кратчайший путь;

— задача почтальона;

— задача коммивояжера;

— максимальный поток в сети;

— поток с минимальной стоимостью;

— транспортная задача с минимальной стоимостью;

— транспортная задача с минимальным временем.

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

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

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

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

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

32. Методы хранения графов в памяти ЭВМ.

Существуют различные способы представления графов.

1. Матрица инцидентности.

Это прямоугольная матрица размерности mхn, где n – количество вершин, а m – количество ребер. Значения элементов матрицы определяется следующим образом: если ребро x_i и вершина v_j инцидентны, то значение соответствующего элемента матрицы равно единице, в противном случае значение равно нулю. Для ориентированных графов матрица инцидентности строится по следующему принципу: значение элемента матрицы равно единице, если ребро x_i исходит из вершины v_j, равно 1, если ребро x_i заходит из вершины v_j, и равно 0 в противном случае.

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

Это квадратная матрица размерности nxn, где n – количество вершин. Если вершины v_i и v_j смежны, т.е. если существует ребро, их соединяющее, то соответствующий элемент матрицы равен единице, в противном случае он равен нулю. Правила построения данной матрицы для ориентированного графа не отличаются. Матрица смежности более компактна, чем матрица инцидентности. Следует заметить, что эта матрица также сильно разрежена, однако в случае неориентированного графа она является симметричной относительно главной диагонали, поэтому можно хранить не всю матрицу, а только половину (треугольную матрицу).

1. Список смежности (инцидентности).

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

Список смежности более эффективен по сравнению с матрицей смежности, так как исключает хранение нулевых элементов.

1. Список списков.

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

Для реализации графа в виде списка инцидентности можно использовать следующий тип:

Type List = ^S;

S = record;

inf: Byte;

next: List;

end;

тогда граф задается следующим образом:

Var Gr: array [1…n] of List;

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

Граф можно определить с помощью списка списков следующим образом:

Type List = ^TList;

TList = record;

inf: Byte;

next: List;

end;

Graph = ^T Graph;

T Graph = record;

inf: Byte;

smeg: List;

next: Graph;

end;

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

33. Методы нахождения кратчайших путей в графе.

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

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

Пусть задан граф G, каждой дуге которого поставлено в соответствие неотрицательное

число l_i,j, называемое длиной. Выделим две вершины S и t. Задача состоит в том, чтобы найти путь минимальной длины между ними. Если в графе имеются кратные дуги (соединяющие одинаковые начало и конец), достаточно оставить одну - с наименьшей длиной, а остальные отбросить. Таким образом, достаточно рассматривать задачу о кратчайшем пути для простого графа, в котором дуги

определяются упорядоченными парами вершин (v₁,v₂). Тогда естественно путь L, идущий из вершины S в вершину t, задавать в виде упорядоченного набора вершин, через которые проходит данный путь: L=(S = v_0,,v₁,v₂,..., v_n-1, v_n = t)

Метод Минти.

Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(S = v_0,,v₁,v₂,..., v_n-1, v_n = t).

Он пригоден для определения кратчайшего пути как во взвешенном, так и в невзвешенном графе. На предварительном (нулевом) этапе алгоритма:

1)Формируется массив значений так называемых модифицированных длин, которые перед началом первой итерации полагаются равными l_i,j ≥0;

2)Осуществляется отметка вершины S = v₀ числом m₁=0.

Стандартная итерация включает следующие этапы:

1.Отметка вершин сети.

Обозначим множество вершин сети, отмеченных на предыдущих итерациях

как множество М (на первой итерации М= { v₀}). Для каждой вершины v_i из множества М пишутся дуги, соединяющие ее с еще не помеченными вершинами - потомками v_j, модифицированная длина которых c_i,j =0. Найденные таким способом вершины v_j помечаются числом m_j=i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имеющих c_i,j =0, заканчиваются в одной и той же вершине v_j, значение для ее пометки i выбирается произвольно. Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь

L=(S = m₁,m₂,m₃,..., m_n-1, m_n = t), на чем алгоритм завершается. В случае, если вершины t нет среди помеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

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

Далее модифицированные длины всех дуг, которые соединяют отмеченные вершины v_i из множества М c непомеченными вершинами v_j, уменьшаются на величину

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

Образец решения задачи.

Пусть дан граф G. Определим кратчайший путь из вершины 1 в вершину 6.

10

2 2

3 8

На предварительном этапе вершина 1 отмечается числом m₁ =0, а модифицированные длины совпадают с заданными длинами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отмел невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем

и вычитаем ее из c₁₂ и c₁₃. После преобразования имеем c₁₂=0, c₁₃=l.

10

0 2

1 8

Итерация 2.

Помечаем вершину 2 m₂ =1. Дальнейшая пометка невозможна, поэтому переходим к этапу

2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Определяем

и после соответствующего преобразования имеем c₁₃=0, c₂₃=0, c₂₄=1,c₂₅=9.

1 9

0 2

0 8

Итерация 3.

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

m₃ =1. Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются

и после преобразования имеем c₂₄=0, c₂₅=8, c₃₄=5, c₃₅=3.

1

8

0 8

(2)1 5

Итерация 4.

Помечаем вершину 4 m₄ =2. Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются вершины 5,6. Определяем

и после преобразования имеем c₂₅=5, c₃₅=0, c₄₅=0, c₄₆=5.

1

5

0 2

0 5

(2)1 5

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершиныЗ, так и из вершины 4. Руководствуясь теми же соображениями, что и на итерации.З, пометим вершину 5 числом m₅=3

1

5

0 0

0 3

(2)1 5 2

Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными вершинами является вершина 6. Отсюда определяем