Основные понятия теории графов

Математические основы сетевого планирования

 

 

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

Рассмотрим множество , которое будем назвать множествомвершин, и набор упорядоченных пар , называемый множеством дуг. Пара называется графом. Запись обозначает граф с именем , состоящий из множества вершин и множества дуг .

Обычно вершины графа изображаются в виде точек, а дуги в виде соединяющих эти точки стрелок (рис 1.1).

 

 

Рис. 1.1. Изображение графа

 

На рис. 1.1 изображен граф , где и .

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

Считается, что дуга выходит из вершины и входит в вершину . При этом говорят, что вершины и инцидентны дуге , а дуга инцидентна вершинам и . Например, вершины и инцидентны дуге , выходящей из и входящей в .

Вершины и дуги называют соответственно начальной и конечной вершинами этой дуги.

Дуги, которые выходят и входят в одну и ту же вершину, называются петлями. Например, дуга является петлей.

Вершины, не имеющие смежных, называются изолированными вершинами. Например, – изолированная вершина.

Очевидно, что множество дуг можно интерпретировать как бинарное отношение, а – множество, на котором это бинарное отношение строится.

Если множество дуг не является симметричным отношением, то такой граф называется ориентированным графом. Граф, изображенный на рис. 1.1, является ориентированным графом.

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

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

 

Матрица симметричного бинарного отношения симметричная.

 

Рис. 1.2. Граф, представляющий симметричное отношение

 

Для того, чтобы разгрузить рисунок при изображении неориентированного графа, принято пару противоположных дуг изображать линией без стрелок, как это изображено на рис. 1.3.

 

 

Рис. 1.3. Неориентированный граф

 

Для того, чтобы подчеркнуть, что порядок вершин в неориентированном графе не имеет значения, при обозначении пар вершин, соединенных двумя противоположными дугами, используется запись с круглыми скобками: , а сами такие пары называют ребрами.

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