3. Алгоритмы на графах
Цель практического занятия по данной теме - освоение идей основных алгоритмов на графах и приобретение навыков в реализации этих алгоритмов.
3.1. Общие положения
Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х1,...,Хn}), и множества связей в парах вершин, которые называются дугами, или ребрами ( (Хi, Хj) G ) в зависимости от наличия или отсутствия направленности связи.
Ребром называются две встречные дуги (Хi, Хj) и (Хj, Хi). На графе они изображаются одной линией без стрелки. Ребро, или дуга, концевые вершины которого совпадают, называется петлей.
Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.
Две вершины, являющиеся концевыми для некоторого ребра или некоторой дуги, называются смежными. Соответственно этот граф может быть представлен матрицей смежности либо матрицей инцидентности.
В табл. 3.1 приведена матрица смежности данного графа, где строки и столбцы - это вершины , “1” - это присутствие соответствующей дуги (направление принимается от буквы, именующей столбец, к букве, именующей строку); “0” - отсутствие соединения вершин. Присутствие “1” на главной диагонали данной таблицы означает наличие петель на графе.
Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: “1” ставится в случае если вершина vi, инцидентна ребру uj; “0” - в противном случае.
Вершина и ребро (дуга) называются инцидентными друг другу, если вершина является для этого ребра (дуги) концевой точкой.
Взвешенным называется граф, если задана функция веса lij на дугах графа: например lij - длина дуги (Хi, Хj). Чаще всего lij ≥ 0; можно задать lij в матричном виде
с,
если (Хi, Хj)
G
(с-конечное число): lij =
∞, если (Хi, Хj) G
Пример 3.1. Ha рис. 3.1 изображен граф, имеющий четыре вершимы X = {X1, X2, X3, X4} четыре дуги (X1, X3), (X2, X1), (X2, X4), (X3, X2) и два ребра (X1, X4), (X4, X3). Для вершины X1 смежными являются вершины: X2, X3 и X4, а инцидентными - дуги (X1, X3), (X2, X1) и ребро (X3, X4).
Т
аблица
3.2
G
X1
X2
X3
X4
X1
0
0
1
1
X2
1
0
0
1
X3
0
1
0
1
X4
1
0
1
0
Рис.3.1
Для ориентированного графа определяются следующие понятия:
1 . Исход вершины G(Хj) - множество вершин Xj , таких, что (Хi, Хj) G.
2. Вход вершины G-1(Хj) -множество вершин Xj, таких, что (Хj, Хi) G.
3. Степень исхода - мощность S(Xj)= | G(Хj) | множества исхода.
4. Степень входа -мощность S-1(Xj)= | G-1(Хj) | множества входа.
Для графа (рис. 3.1) рассмотрим исходы и входы вершин X1 и Х4. Имеем
G(Х1): {X3, X4}: (X4, X3), (X1, X4) G; G(Х4): {X1, X3}: (X4, X1), (X4, X3) G. G-1(Х1) = {X2, X4}: (X2, X1), (X4, X1) G; G-1(Х4) = {X1, X2, X3}: (X1, X4), (X2, X4), (X3, X4) G;
Для тех же вершин X1 и X4 степени исхода и входа соответственно равны: S(X1) = 2; S(X4) = 2; S-1(X1) = 2; S-1(X4) = 3. Для неориентированного графа степень S(Xj)= | G(Хj) | вершины Xj равна числу ребер инцидентных ей вершин.
Кроме матрицы смежности, описанной в примере 3.1, граф может быть представлен матрицей инцидентности.
П
ример
3.2. На рис.3.2 изображен граф, состоящий
из четырех вершин X1, Х2, Х3,
Х4 и пяти дуг. Рядом с изображением
графа на рисунке изображена матрица
инциденций. Таблица 3.2
G
1
2
3
4
5
X1
1
1 0
0
1
X2
0
1
1
1
0
X3
1
0
0
1
0
X4
0
0
1
0
1
Рис.3.2