Основные положения. Раздел 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=Æ.

Нетрудно заметить, что данное определение графа полностью совпадает с определением отношения на множестве.

Введем некоторые понятия и определения, служащие для описания различных видов графов.

Подграфом G_A графа G=(X,Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины, например, очерченная пунктиром область А на рис.2.1. Математически подграф обозначается следующим образом:

G_A=(A,Г_A), где АÍХ, Г_АХ=(Г_Х)ÇА (2.1)

Частичным графом G_D по отношению к графу G=(X, Г) называется граф, содержащий только часть дуг графа G, т.е. определяемый условием:

G_D=(X, D), где Dx Í Г_X (2.2)

Например, пусть G=(X,Г) - карта шоссейных дорог Украины. Тогда карта шоссейных дорог Днепропетровской области представляет собой подграф, а карта главных дорог Украины - это частичный граф.

Другими важными понятиями для графа является понятие пути и контура. Дуга, соединяющая вершины a и b, и направленная от а к b обозначается u=(a,b).

Определения.

Путем в графе G называют такую последовательность дуг m=(u₁,...,u_k) , в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь m, последовательными вершинами которого являются вершины a,b,...,m, обозначается через m=(a,b,...,m).

Длиной пути m=(u₁,...,u_k) называют число l(m)=k, равное числу дуг, составляющих путь. Иногда каждой дуге u_i приписывают некоторое число l(u_i), называемое длинной дуги. Тогда длинна пути определяется как сумма длин дуг, составляющих путь

_k

l (m)=S l(u_i) (2.3)

^I=1

Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным.

Контур - это конечный путь m=(x₁,...,x_k), у которого начальная вершина х₁ обязательно совпадает с конечной х_k. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длинны, образованный дугой вида (а, а) называется петлей. Так, например, на рис. 1 (e, d, c, b) - путь, а (c, e, d, c) - контур, (d, d) - петля.

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

Вершины x и y являются смежными, если они различны и если существует дуга, идущая из x в y.

Дугу u называют инцидентной вершине х, если она заходит в эту вершину или исходит из нее.

Обозначим через х₁,...,х_n вершины графа, а через u₁,...,u_m его дуги. Введем числа:

 

ì1, если имеется дуга, соединяющая вершину i с

r_ij = í вершиной j; (2.4)

î0, если такой дуги нет.

 

Квадратная матрица R=[r_ij] порядка (nxn) называется матрицей смежности графа.

Введем числа :

 

ì +1, если u_j исходит из x_i

S_ij= í -1, если u_j заходит в x_i (2.5)

î 0, если u_j не инцидентна x_i

 

Тогда матрица S=[S_ij] порядка (nxm) называется матрицей инцидентностидля дуг графа.

Матрицы инцидентности в описанном виде применимы только к графам без петель. В случае наличия в графе петель эту матрицу следует расчленить на две полу матрицы: положительную и отрицательную.

На рис.2.2 приведен граф без петель, для которого матрицы смежности и инцидентности имеют следующий вид:

 

Матрица смежности.

i j
Ри.2.2. 4

Рис.2.2 – Граф без петель

Матрица инцидентности

i j
	-1			-1
					-1
		-1					-1
			-1			-1		-1

Обычно рассматриваемые графы конечны, т.е. конечны множества их элементов

( вершин и ребер). Поэтому конечностьэтих графов не будет специально оговариваться.

Примеры ориентированных графов:

 

 

а в с

 

d e f g к

(кратные ребра)

 

Рис.2.3 - Примеры ориентированных графов

В приведенных примерах вариант "в" представляет граф с пустым множеством ребер. Граф "е" иллюстрирует недостижимость двух вершин, а "g" – граф с петлей.

<1234567>

---

Дата добавления: 2015-10-05; просмотров: 832;

---