Метод Дейкстры нахождения кратчайшей цепи в связном графе
1.1 Основные понятия теории графов
Если необходимо представить в наглядной форме систему каких-либо взаимосвязанных объектов, то прибегают к такому построению: на плоскости или в пространстве выбирается несколько точек и некоторые пары точек соединяются линиями.
Объект, который получается в результате указанного построения, называется графом. В качестве примеров можно указать блок-схему алгоритма, граф соединений в электрической схеме, сеть путей дорожного сообщения и так далее.
Одну и ту же систему объектов и связей между ними можно по-разному изобразить, применяя указанное выше построение: различным образом располагать точки, в качестве соединяющих их линий брать те или иные кривые и так далее. Более того, можно вообще не рисовать, а указать систему связей объектов в какой-либо иной форме, например, в словесной. Это рассуждение показывает, что необходимо определение графа, как некоторого формального объекта, который можно различными способами представать наглядно.
Говорят, что задан конечный неориентированный граф, если заданы следующие два объекта [1]:
1) конечное множество , элементы этого множества называются вершинами графа;
2) Некоторое множество неупорядоченных пар элементов из , это множество обозначается , его элементы, то есть пары вершин, называются ребрами.
метод дейкстра связный граф
Тот факт, что граф определяется парой множеств и , записывается в виде . При наглядном представлении графа вершины изображаются точками, ребра - линиями, соединяющими эти точки.
Например, , где
,
.
В наглядной форме этот граф представлен на рисунке ниже.
Наряду с введенным определением графа возможны и другие. Так, например, иногда возникает необходимость рассматривать графы, в которых одну и ту же пару вершин соединяет несколько ребер. Такие графы называют мультиграфами. Рассматривают также графы, в которых некоторые ребра могут иметь совпадающие концы. Такие ребра называют петлями. В большинстве приложений теории графов можно отбрасывать петли и заменять кратные ребра одним ребром. В дальнейшем под графом будем понимать конечный неориентированный граф без петель и кратных ребер.
Понятие ориентированного графа возникает, если ребрам графа придать направление, ориентацию, так что один из концов ребра будет началом, а другой - концом.
Говорят, что задан ориентированный граф, если указаны два объекта:
1) непустое конечное множество - вершины графа;
2) множество , составленное из упорядоченных пар вершин.
Элементы множества называют дугами. Дуга ориентированного графа изображается отрезком со стрелкой.
Пусть дан граф . О ребре этого графа говорят, что оно соединяет вершины и . Вершины, соединенные ребром, называются смежными. О ребре и вершине говорят, что они инцидентны, то же можно сказать о ребре и вершине .
Будем обозначать число вершин графа буквой , а число ребер - буквой : . Это основные числовые характеристики графа.
Число ребер, инцидентных данной вершине , называется степенью этой вершины и обозначается . Вершина, у которой степень равна нулю, называется изолированной. Вершины, имеющие степень, равную единице, называют висячими. Например, вершины и на рисунке, изображенном ранее, висячие, а вершина - изолированная.
Справедливы следующие утверждения:
сумма степеней всех вершин графа равна удвоенному числу ребер;
число вершин, имеющих нечетную степень, четно.
Для ориентированных графов вместо степени вершины вводят понятия полустепеней: полустепень захода - это количество дуг, входящих в вершину , то есть направленных стрелкой к вершине. Полустепень исхода - это количество дуг, выходящих из вершины .
Граф, не имеющий ребер , называется пустым. Все вершины пустого графа изолированные. Граф, в котором каждая пара вершин соединена ребром, называется полным. Полный -вершинный граф обозначается , для каждой его вершины имеем .
Пусть дан граф . Удаляя из графа некоторые ребра и вершины, будем получать подграфы исходного графа.
Граф называется подграфом графа , если и .
Граф называется остовным подграфом графа , если и . Остовный подграф получается, если в графе удалить часть ребер, не трогая вершин.
Не всегда удобно задавать граф в том виде, как это указано в определении. Например, при обработке графа на ЭВМ, его удобно представлять в матричной форме.
Пусть дан ориентированный граф и . Занумеруем вершины графа числами . Рассмотрим -матрицу , элементы которой определяются по следующему правилу: , если , в противном случае .
Матрица называется матрицей смежности вершин графа . Для случая графа эта матрица симметрична и имеет нули на диагонали.
Число единиц в какой-либо строке матрицы смежности равно степени соответствующей вершины.
При введении какого-либо математического понятия всегда договариваются о том, какие объекты считаются одинаковыми и какие необходимо различать. Изоморфные объекты - это такие объекты, которые в дальнейшей теории не различаются и рассматриваются как один объект. Например, графы, показанные на рисунке ниже, отличаются только обозначением вершин и способом размещения на плоскости.
Если во втором графе переобозначить вершины по схеме
,
то множества вершин и ребер в первом и во втором графах совпадут, и получится один и тот же граф.
Графы и называются изоморфными, если между множествами их вершин можно установить взаимно однозначное соответствие, такое, что любые две вершины смежны в одном из графов в том и только в том случае, когда соответствующие им вершины смежны в другом графе.
На рисунке выше изображены два изоморфных графа.