Автор работы: Пользователь скрыл имя, 25 Марта 2015 в 15:41, лекция
Основные определения, представление графа в ЭВМ. Математическое представление графов. Алгоритмы обхода графов в глубину и по уровням. Алгоритмы поиска минимального остовного дерева.
Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V – это множество вершин или узлов,
E – это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе
|V| — порядком, число рёбер |E| — размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) рёбра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
V – это множество вершин или узлов,
A – это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.
Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.
Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Обозначение связей: неориентированных - (A,B), ориентированных - <A,B>. Примеры изображений графов даны на рис.1. Скобочное представление графов, представленных на Рис. 3.1: а).((A,B),(B,A)) и б).(< A,B >,< B,A >).
Рис. 3.1. Граф неориентированный (а) и ориентированный (б).
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Ориентированным путём в орграфе называют конечную последовательность вершин vi (i = 1, …, k), для которой все пары (vi,vi+1), (i = 1, …, k-1), являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:
Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v», является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов. Ребро графа называется мостом, если его удаление увеличивает число компонент.
Дополнительные характеристики графов
Граф называется:
Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
Многосвязная структура обладает следующими свойствами:
В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.
Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.
Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 - в противном случае (Рис. 3.2).
Рис. 3.2. Граф и его матрица смежности
Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица симметрична относительно главной диагонали.
Матрицы смежности используются при построении матриц путей, дающих представление о графе по длине пути: путь длиной в 1 - смежный участок, путь длиной 2 - (< A,B >,< B,C >), путь длиной в n - n смежных участков: где n - максимальная длина, равная числу узлов графа. На Рис. 3.3 даны путевые матрицы пути adj2, adj3, adj4 для графа Рис. 3.1.
Рис. 3.3. Матрицы путей
Матрицы инцидентности используются только для орграфов. В каждой строке содержится упорядоченная последовательность имен узлов, с которыми данный узел связан ориентированными (исходящими) ребрами. На Рис. 3.4 показана матрица инцидентности для графа Рис. 3.1.
Рис. 3.4. Матрица инцидентности
Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то целесообразно представлять граф связными списками; в противном случае можно применить и матричное представление.
При использовании матриц смежности их элементы представляются в памяти ЭВМ элементами массива. При этом для простого графа матрица состоит из нулей и единиц, для мультиграфа - из нулей и целых чисел, указывающих кратность соответствующих ребер, для взвешенного графа - из нулей и вещественных чисел, задающих вес каждого ребра.
Например, для простого ориентированного графа, изображенного на Рис. 3.1 массив определяется как:
array[4][4]={{0,1,0,0},{0,0,
Матрицы смежности применяются, когда в графе много связей и матрица хорошо заполнена.
Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Рассмотрим два варианты представления орграфов связными нелинейными списковыми структурами.
В первом варианте используются два типа элементов: атомарный и узел связи. На Рис. 3.5 показана схема такого представления для графа Рис. 3.1. Скобочная запись связей этого графа:
( < A,B >, < B,C >, < C,D >, < B,D >, < D,C > )
Рис. 3.5. Машинное представление графа элементами двух типов
Более рационально представлять граф с использованием списков примыкания. При этом каждый узел содержит указатель на начало связного списка, содержащего указателями на узлы, непосредственно связанными с данным узлом:
struct ListNode
{
struct Graph *pVertex;
struct ListNode *pNext;
};
struct GraphNode
{
struct Data *pData;
struct ListNode *pVertexList;
};
Если с ребрами (или дугами) графа требуется связать некоторую информацию (длину пути, например), то список структур можно модифицировать следующим образом:
struct Arc
{
struct ArcData *pData;
struct Vertex *pBeginVertex;
struct Vertex *pEndVertex;
}
struct ListNode
{
struct Arc *pArc;
struct ListNode *pNext;
};
struct Vertex
{
struct VertextData *pData;
struct ListNode *pArcList;
};
При работе с графами часто приходится выполнять какое-либо действие по одному разу с каждой из вершин графа. Например, некоторую порцию информации следует передать каждому компьютеру в сети. Подобный обход можно совершать двумя различными способами. При обходе в глубину проход по выбранному пути осуществляется настолько глубоко, насколько это возможно, а при обходе по уровням мы равномерно двигаемся вдоль всех возможных направлений
При обходе в глубину посещается первый узел, а затем происходит перемещение вдоль ребер графа до тех пор, пока не встретится тупик. Узел неориентированного графа является тупиком, если все примыкающие к нему узлы уже были посещены. В орграфе тупиком также называется узел, из которого нет выходящих ребер. После попадания в тупик необходимо передвигаться назад вдоль пройденного пути до тех пор, пока не будет обнаружена вершина, у которой есть еще не посещенный сосед, и затем двигаться в этом новом направлении. Процесс оказывается завершенным, когда произошел возврат в отправную точку, и все примыкающие к ней вершины уже были посещены.
Рекурсивный алгоритм обхода в глубину приведен ниже:
DepthFirstTraversal(G,v)
G - граф
v - текущий узел
Visit(v)
Mark(v)
for каждого ребра vw графа G do
if вершина w непомечена then
DepthFirstTraversal(G,w)
end if
end for
Этот рекурсивный алгоритм использует системный стек для отслеживания текущей вершины графа, что позволяет правильно осуществить возвращение, наткнувшись на тупик. Можно построить нерекурсивный алгоритм, воспользовавшись стеком для сохранения и удаления информации о пройденных вершинах.
При обходе по уровням после посещения первого узла посещаются все соседние с ним вершины. При втором проходе посещаются все вершины, находящиеся на расстоянии двух ребер от начальной. При каждом новом проходе обходятся все вершины, расстояние от которых до начальной на единицу больше предыдущего. Для предупреждения повторного посещения необходимо либо вести список посещенных вершин, либо хранить информацию о посещении в соответствующей структуре данных узла. Ниже приведен пример реализации алгоритма обхода по уровням:
BreadthFirstTraversal(G,v)
G граф
v текущий узел
Visit(v)
Mark(v)
Enqueue(v)
while очередь непуста do
Dequeue(x)
for каждого ребра xw в графе G do
if вершина w непомечена then
Visit(w)
Mark(w)
Enqueue(w)
end if
end for
end while
Этот алгоритм заносит в очередь корень дерева обхода по уровням, но затем немедленно удаляет его из очереди. При просмотре соседних с корнем вершин он заносит их в очередь. После посещения всех соседних с корнем вершин происходит возвращение к очереди и обращение к первой вершине оттуда. Поскольку узлы добавляются к концу очереди, ни одна из вершин, находящихся на расстоянии двух ребер от корня, не будет рассмотрена повторно, пока не будут обработаны и удалены из очереди все вершины на расстоянии одного ребра от корня.
Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного графа и некоторых его ребер, причем сумма весов ребер является минимально возможной. Такое дерево может понадобиться, например, для организации компьютерной сети.
Дейкстра и Прим предложили так называемый «жадный» алгоритм построения МОД. «Жадные» алгоритмы действуют, используя в каждый момент часть исходных данных и принимая лучшее решение на основе этой части. В рассматриваемом случае на каждом шаге имеется множество ребер, которые могут быть присоединены к уже построенной части остовного дерева, из них выбирается ребро с наименьшим весом. Вершины графа разбиваются на три класса: вершины, вошедшие в уже построенную часть дерева, вершины, окаймляющие построенную часть, и еще не рассмотренные вершины. Алгоритм начинает работу с произвольной вершины графа, которая включается в остовное дерево. Все вершины, соединенные (соседние) с данной, заносятся в кайму. Затем выполняется цикл поиска ребра с наименьшим весом, соединяющего уже построенную часть остовного дерева с каймой; это ребро вместе с новой вершиной добавляется в дерево и происходит обновление каймы таким образом, чтобы список ребер из дерева в кайму включал ребра с наименьшими весами. После того, как в дерево попадут все вершины, работа будет закончена. Словесный алгоритм приведен ниже: