Алгоритмы на графах. Представление графов. Кратчайшие пути из одной вершины

Алгоритмы на графах

Основные определения

Граф G=(V,E) включает непустое множество V, называемое множеством вершин (узлов), множество E, представляющее множество ребер графа и отображение множества ребер на множество пар элементов из множества V. Любые две вершины u и v, соединенные ребром x, называются смежными, и говорят, что ребро x инцидентно вершинам u и v. Граф, у которого каждая вершина смежна со всеми остальными вершинами, называется полным графом.

Основные определения

1

2

4

3

5

Основные определения

Ребро x, направленное от одной вершины u к другой v, называется ориентированным ребром, или дугой. Граф, содержащий только ориентированные ребра, называется ориентированным графом (орграфом). Ребро, не имеющее определенного направления, называется неориентированным ребром. Граф только с такими ребрами называется неориентированным. Граф, содержащий как ребра, так и дуги, называется смешанным графом.

Основные определения

1

2

4

3

5

Основные определения

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

Основные определения

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

Основные определения

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

Представление графов

Матрица смежности Пусть вершины перенумерованы в некотором порядке. Матрица смежности A(n*n), в которой аij=1, если вершины связаны ребром и аij=0 противном случае. Для простых неориентированных графов матрица смежности симметрична. В случае взвешенного графа полагается аij=wij, где wij – вес ребра. Представление графа с помощью матрицы смежности предпочтительно в случае плотных графов или когда нам надо иметь возможность быстро определить, имеется ли ребро, соединяющее две данные вершины.

Представление графов

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

Представление графов

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

Представление графов

Матрица инцидентности Матрица инцидентности bij размерностью n*m (n – число вершин, m – число дуг) определяется следующим образом: bij=+1, если ui является начальной вершиной дуги aj; bij=-1, если ui является конечной вершиной дуги aj; bij=0 в противном случае. Если граф неориентированный, то его матрица инцидентности определяется аналогично, за исключением того, что элемент -1 поменяется на +1.

Пути в графе

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