Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Графическое изображение

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

Графическое изображение графа

Рис. 1.16. Графическое изображение графа: а — неориентированного; б — ориентированного

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

Изоморфные графы

Рис. 1.17. Изоморфные графы

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

Большинство графов, с которыми приходится сталкиваться на практике, имеет небольшое число ребер. Граф считается насыщенным {плотным), если средняя степень его вершин пропорциональна V Разреженный граф есть граф, дополнение которого насыщено. Другими словами, граф считается насыщенным, если число его ребер Е пропорционально V2, и разреженным в противном случае.

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

Матрица смежности. Граф можно представить матрицей, если сопоставить строкам и столбцам соответствующие вершины графа, а в качестве элемента (IJ) матрицы на пересечении строки у, и столбца ^ указать число ребер (кратность), соединяющих эти вершины, а для орграфа — направленных от вершины у,- к вершине у,-. Такая матрица называется матрицей смежности [28].

Ниже показаны матрицы смежности для графа и орграфа, изображенных на рис. 1.16:

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

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

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

Любую квадратную матрицу «-го порядка можно представить орграфом с « вершинами, дуги которого соединяют смежные вершины и имеют веса, равные соответствующим элементам матрицы [28]. Симметричную матрицу можно представить неориентированным графом. Напомним, что граф с « вершинами является графом «-го порядка. Имеет место следующая теорема, касающаяся матрицы смежности У ориентированного графа [6].

Теорема 1.1. Матрица V" дает число ориентированных маршрутов длины п между любыми двумя вершинами ориентированного графа.

То же справедливо для неориентированного графа.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>