Графы

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

Простой граф G(V, E) есть совокупность двух множеств. Негустого множества V и множества E неупорядоченных пар различных элементов множества V. Множество V называют множеством вершин, множество E называют множеством ребер. V - не пустое множество.

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

Ориентированный граф состоит из множества вершин и множества V, E, здесь E - ориентированные ребра. Ребро или дуга представляется в виде упорядоченных пар вершин (v, w), где v - начальная вершина, w - конец дуги, v->w: говорят, что дуга ведёт от вершины v к вершине w, а вершина w смежная с вершиной v.

Пример ориентированного графа:

Вершину ориентированного графа можно использовать для представления объектов, а дуги для отношений между объектами. Путем в ориентированном грфе называется последовательность вершин V1, V2, ..., Vn, для которой существуют в дуги V1->V2, ... , Vn-1->Vn. Этот путь начинается в вершине V1 и проходя через вершины V2, Vn-1 закончивается в вершине Vn. Длина пути - это количество дуг, составляющих путь. В данном случае длина души равна n-1. Путь назвается простым, если все вершины на нем, за исключением может быть первой и последней, различны. Цикл - это простой путь длины не менее еденицы, которая начинается и заканчивается в одной и той же вершине.

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

Представления ориентированных графов.

Для представления ориентированных графов можно использовать различные структуры графов. Выбор структур данных зависит от операторов, которые будут применяться к вершинам и дугам ориентированных графов. Одним из наиболее общих представлений ориентированных графов является матрица смежности. Предположим, что множество вершин равна V={1,2,3,n}. Матрица смежности для данного ориентированного графа это матрица А={N,M}, со значением рулевого типа, где А[i,j]=true тогда и только тогда, когда существует дуга из вершины i до вершины j. Часто в матрицах смежности значение true обозначается 1, а false значением 0. Время доступа к элементам матрицы смежности зависит от размеров множества вершин и множества дуг. Основной недостаток использования матрицы смежности заключается в том, что она требует О(n^2) памяти, даже если дуг значительно меньше, чем n^2.

Вместо матрицы смежности часто используется представление посредством списком смежности. Списком смежности для вершины i называется список всех вершин смежных с вершиной i, причем определенным образом упорядоченный. Таким образом, ориентированный граф G можно представить посредством массива HEAD(заголовок), чей элемент HEAD[i] является указателем на список смежности вершины i. Представление ориентированного графа с помощью списков смежности требует для хранения объем памяти пропорциональный сумме количества вершин и количества дуг. Если количество дуг имеет порядок О(n), то и общий объем необходимой памяти имеет такой же порядок. Для вставки и удаления элементов в списке смежности необходимо иметь массив HEAD, содержащий указатель на ячейки заголовков списков смежности, но не сами смежные вершины.

Задача нахождения кратчайшего пути

Пусть имеется ориентированный граф G(V, E), у которого все дуги имеют неотрицательные метки, а одна вершина определена как источник. Задача состоит в нахождении стоимости кратчайших путей от источника ко всем другим вершинам данного графа, здесь длина пути определяется как сумма стоимости дуг, составляющих путь. Для решения поставленной задачи будем использовать "жатный" алгоритм (алгоритм Дейкстра). Алгоритм строит множества S вершин, для которых кратчайшие пути от источника уже известны.

АЛГОРИТМ ОБХОДА В ГЛУБИНУ

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

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

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

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

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

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

РИСУНОК

Начав обход в глубину в вершине 1, мы последовательно посетим вершины 2,3,4,7,5,6 и упремся в тупик. Затем нам придется вернуться назад……. Посещая вершину 8 мы снова оказываемся в тупике, возвращаемся назад до вершины 4 и обнаружим не посещенную вершину 9, посетив вершину 9 мы снова оказываемся в тупике идем назад до отправной точки. Таким образом обход в глубину завершен.

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

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

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

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

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

Порядок сложности алгоритма обхода определяется числом посещений узлов. Каждая вершина посещается в точности один раз, поэтому на графе с n вершинами происходит n посещений, соответственно сложность алгоритма составит О(n).

• Минимальное отставное дерево алгоритм минимального отавного дерева Минимальным отставным деревом связанного, взвешенного графа называется его связанный подграф состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер минимально возможная. Если исходный граф не связен то описываетмую ниже процедуру можно применять поочередно к каждой его компоненте связности. Получая тем самым минимальные отставные деревья для этих компонент. В множестве из n ребер имеется 2^n подмножетсв. Для каждого из этих подмножетсв мы должны проверить что оно задает связаный подграф охватывающий все вершины исходного и не содержит циклов. Процесс можно ускорить после того, как найдено первое отставное дерево. Никакое подмножетсво ребер полный вес которого больше чем у уже найденного лучше отставного дерева не может нам подойти поэтому нет необходимости проверять связность, отцикличность и охват всех вершин. Сложность данного алгоритма равна О(2^n).

<aside> <img src="/icons/calendar-month_purple.svg" alt="/icons/calendar-month_purple.svg" width="40px" /> 04.05.24

</aside>

• алгоритм Дейкстры—Прима В конце 1950-х годов Эдгар Дейкстра и Прим, работая и публикуя свои результаты независимо друг от друга, предложили следующий алгоритм построения МОД. Воспользуемся для поиска МОД так называемым «жадным» алгоритмом. Жадные алгоритмы действуют, используя в каждый момент лишь часть исходных данных и принимая лучшее решение на основе этой части. В нашем случае мы будем на каждом шаге рассматривать множество ребер, допускающих присоединение к уже построенной части остовного дерева, и выбирать из них ребро с наименьшим весом. Повторяя эту процедуру, мы получим остовное дерево с наименьшим весом. Вот как выглядит алгоритм: выбрать начальный узел сформировать начальную кайму, состоящую из вершин, соседних с начальным узлом while в графе есть вершины, не попавшие в дерево do выбрать ребро из дерева в кайму с наименьшим весом добавить конец ребра к дереву изменить кайму, для чего добавить в кайму вершины, соседние с новой обновить список ребер из дерева в кайму так, чтобы он состоял из ребер наименьшего веса end while

• алгоритм Крускала Алгоритм Дейкстры-Прима начинает построение МОД с конкретной вершины графа и постепенно расширяет построенную часть дерева; в отличие от него алгоритм Крускала делает упор на ребрах графа. В этом алгоритме мы начинаем с пустого дерева и добавляем к нему ребра в порядке возрастания их весов пока не получим набор ребер, объединяющий все вершины графа. Если ребра закончатся до того, как все вершины будут соединены между собой, то это означает, что исходный граф был несвязным, и полученный нами результат представляет собой объединение МОД всех его компонент связности.

При рассмотрении ребер весом = 6, 2 из 4 ребер весом 6 стоит отбросить, поскольку их добавление приведет к появлению цикла в уже построенной части mod. Присоединение ребра CF создало бы цикл содержащий вершину А. Присоединение ребра BD создало бы цикл содержащий вершины А и F.

• алгоритм поиска кратчайшего пути Результатом алгоритма поиска кратчайшего пути является последовательность ребер соединяющая заданные две вершины и имеющие наименьшую длину среди всех таких последовательностей.

• алгоритм Дейкстры Задача найти кратчайший путь от А до G.

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

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