Теория графов

Условиями.

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

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

Одну и ту же систему объектов и связей между ними можно изобразить по-разному: различным образом изобразить точки, для соединений применять различные линии, или же кривые. Можно вообще не рисовать, а указать систему связей объектов в какой-либо форме, например в словесной. Это рассуждение показывает, что необходимо определение графа, как некого формального объекта, который можно разными способами представлять наглядно.

Говорят, что задан конечный неориентированный граф, если заданы следующие два объекта:

1. Конечное множество, элементы этого множества называются вершинами графа.

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

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

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

Говорят, что задан ориентированный граф, если указаны 2 объекта:

1. Непустое конечное множество — вершины графа.

2. Множество, составленное из упорядоченных пар вершин.

Элементы множества называют дугами и изображают в виде отрезка со стрелкой.

Степенью вершины называется число связанных с ней рёбер.

Для ориентированных графов:

Полустепень захода — число входящих дуг.

Полустепень исхода — число исходящих дуг.

При обработке графа в ЭВМ его удобно представлять в матричной форме.

Пусть дан граф. Занумеруем вершины графа числами. Рассмотрим -матрицу, элементы которой определяются по следующему правилу:, если, иначе.

Матрица называется матрицей смежности вершин графа. Для случая графа эта матрица симметрична и имеет нули на диагонали.

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

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

Диаметром графа называется, где максимум берётся по всевозможным парам вершин графа.

Определим для каждой вершины графа величину, т.е. расстояние от до самой далёкой от неё вершины графа. Минимум это величины называется радиусом графа

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

Цикловое ребро — ребро, через которое проходит хотя бы один цикл.

Перешеек — ребро, которое не входит ни в один цикл.

При удалении из связного графа циклового ребра он останется связным. При удалении из графа перешейка граф распадётся на две компоненты.

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

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

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

· Дерево — связный граф, в котором каждое ребро является перешейком.

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

Рассмотрим связный граф и будем удалять из него по одному цикловые рёбра до тех пор, пока не их не останется. В результате получится дерево такое, что:

·, т.е. каждое ребро является в то же время ребром исходного графа.

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

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

Пусть — нагруженный граф. Требуется построить остовное дерево сумма длин рёбер которого минимальна.

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

Сеть — ориентированный граф, в котором выделены две вершины, одна из которых называется началом, и не имеет входящих дуг, другая – концом и не имеет выходящих дуг.

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

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

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

Алгоритм отыскания критического пути.

1. Правильная нумерация сети.

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

Нумеруем начальную вершину сети нулём и удаляем её из сети вместе со всеми выходящими из неё дугами. Получающейся сети образуются вершины, не имеющие входящих дуг, назовём эти вершины — вершинами первого ранга, и занумеруем числами 1,2…. Далее, удалим все вершины первого ранга и выходящие из них дуги. Появившиеся вершины без входящих дуг, назовём вершинами второго ранга, и дадим им соответствующие номера. Этот процесс продолжаем до тех пор, пока не будут занумерованы все дуги сети.

Дата добавления: 2014-01-20