Метод Дейкстры нахождения кратчайшей цепи в связном графе

курсовая работа

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

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

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

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

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

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

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

метод дейкстра связный граф

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

Например, , где

,

.

В наглядной форме этот граф представлен на рисунке ниже.

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

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

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

1) непустое конечное множество - вершины графа;

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

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

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

Будем обозначать число вершин графа буквой , а число ребер - буквой : . Это основные числовые характеристики графа.

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

Справедливы следующие утверждения:

сумма степеней всех вершин графа равна удвоенному числу ребер;

число вершин, имеющих нечетную степень, четно.

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

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

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

Граф называется подграфом графа , если и .

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

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

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

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

Число единиц в какой-либо строке матрицы смежности равно степени соответствующей вершины.

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

Если во втором графе переобозначить вершины по схеме

,

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

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

На рисунке выше изображены два изоморфных графа.

Делись добром ;)