Основные положения. Раздел 2. Основы теории графов
Раздел 2. Основы теории графов
Основные положения
Теорию графов начали разрабатывать для решения некоторых задач о геометрических конфигурациях, состоящих из точек и линий.
Определение графа можно дать как совокупности двух множеств V(точек) и E(линий, дуг), между элементами которых определено отношение инцидентности, причем каждый элемент е Î E инцидентен равно двум элементам v’,v” Î V. Элементы множества V называются вершинамиграфа G , элементы множества Е – его ребрами. Вершины и ребра графа G называют еще его элементами и вместо е Î Е и v ÎV пишут e Î G и v Î G.
В некоторых графах инцидентные ребру вершины неравноправны, они должны, например, рассматриваться в определенном порядке. Тогда каждому из ребер можно приписать направление от первой из инцидентных вершин ко второй. Направленные ребра часто называют дугами, а содержащий их граф – ориентированным. В противном случае
( инцидентные ребру вершины равноправны) граф будем называть неориентированным. Для ориентированного графа
Начало конец
1 2
Дуга: выходит входит
Наглядное представление о графе можно получить, если представить себе некоторое множество точек плоскости Х, называемых вершинами, и множество направленных отрезков U, соединяющих все или некоторые из вершин и называемых дугами. Математически граф G можно определить как пару множеств Х и U. G=(X,U) (1)
На рисунке изображен граф, вершинами которого являются точки a, b, c, d, e, g, h, а дугами - отрезки (a,a), (c,b), (c,d), (c,e), (d,c), (d,d), (e,d), (g,h).
|
Так, для графа, изображенного на рис.2.1 отображение определяется следующим образом:
Гa=a; Гb=Æ; Гc={b,d,e}; Гd={c,d}; Гe=d; Гg=h; Гh=Æ.
Нетрудно заметить, что данное определение графа полностью совпадает с определением отношения на множестве.
Введем некоторые понятия и определения, служащие для описания различных видов графов.
Подграфом GA графа G=(X,Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины, например, очерченная пунктиром область А на рис.2.1. Математически подграф обозначается следующим образом:
GA=(A,ГA), где АÍХ, ГАХ=(ГХ)ÇА (2.1)
Частичным графом GD по отношению к графу G=(X, Г) называется граф, содержащий только часть дуг графа G, т.е. определяемый условием:
GD=(X, D), где Dx Í ГX (2.2)
Например, пусть G=(X,Г) - карта шоссейных дорог Украины. Тогда карта шоссейных дорог Днепропетровской области представляет собой подграф, а карта главных дорог Украины - это частичный граф.
Другими важными понятиями для графа является понятие пути и контура. Дуга, соединяющая вершины a и b, и направленная от а к b обозначается u=(a,b).
Определения.
Путем в графе G называют такую последовательность дуг m=(u1,...,uk) , в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь m, последовательными вершинами которого являются вершины a,b,...,m, обозначается через m=(a,b,...,m).
Длиной пути m=(u1,...,uk) называют число l(m)=k, равное числу дуг, составляющих путь. Иногда каждой дуге ui приписывают некоторое число l(ui), называемое длинной дуги. Тогда длинна пути определяется как сумма длин дуг, составляющих путь
k
l (m)=S l(ui) (2.3)
I=1
Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным.
Контур - это конечный путь m=(x1,...,xk), у которого начальная вершина х1 обязательно совпадает с конечной хk. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длинны, образованный дугой вида (а, а) называется петлей. Так, например, на рис. 1 (e, d, c, b) - путь, а (c, e, d, c) - контур, (d, d) - петля.
Иногда графы удобно представлять в виде некоторых матриц, в честности в виде матриц смежности и инцидентности. Предварительно дадим два определения.
Вершины x и y являются смежными, если они различны и если существует дуга, идущая из x в y.
Дугу u называют инцидентной вершине х, если она заходит в эту вершину или исходит из нее.
Обозначим через х1,...,хn вершины графа, а через u1,...,um его дуги. Введем числа:
ì1, если имеется дуга, соединяющая вершину i с
rij = í вершиной j; (2.4)
î0, если такой дуги нет.
Квадратная матрица R=[rij] порядка (nxn) называется матрицей смежности графа.
Введем числа :
ì +1, если uj исходит из xi
Sij= í -1, если uj заходит в xi (2.5)
î 0, если uj не инцидентна xi
Тогда матрица S=[Sij] порядка (nxm) называется матрицей инцидентностидля дуг графа.
Матрицы инцидентности в описанном виде применимы только к графам без петель. В случае наличия в графе петель эту матрицу следует расчленить на две полу матрицы: положительную и отрицательную.
На рис.2.2 приведен граф без петель, для которого матрицы смежности и инцидентности имеют следующий вид:
Матрица смежности.
i j | |||||||
| |||||||
|
Матрица инцидентности
i j | ||||||||
-1 | -1 | |||||||
-1 | ||||||||
-1 | -1 | |||||||
-1 | -1 | -1 |
Обычно рассматриваемые графы конечны, т.е. конечны множества их элементов
( вершин и ребер). Поэтому конечностьэтих графов не будет специально оговариваться.
Примеры ориентированных графов:
а в с
d e f g к
(кратные ребра)
Рис.2.3 - Примеры ориентированных графов
В приведенных примерах вариант "в" представляет граф с пустым множеством ребер. Граф "е" иллюстрирует недостижимость двух вершин, а "g" – граф с петлей.
Дата добавления: 2015-10-05; просмотров: 832;