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

«Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги - потоки сырья, материалов и продукции между ними, заключаются

в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков [7, 12].

Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги - потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями [6, 9, 17].

Управление проектами . С точки зрения теории графов проект - совокупность операций и зависимостей между ними (сетевой график - см. ниже). Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ) [7, 10]. В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) - в виде ребер или дуг.

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

Завершив краткое описание прикладных областей, вернемся к введению основных понятий.

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

Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам.

Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Граф, для которого из (i,j) е V следует (j, i) е V называется симметрическим. Если из (i, j) е V следует, что (j, i) "е V, то соответствующий граф называется антисимметрическим.

Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь - последовательность смежных вершин. Замкнутая цепь называется циклом. По аналогии с простым и элементарным путем, можно определить соответственно простые и элементарные цепь и цикл. Любой элементарный цикл является простым, обратное утверждение в общем случае неверно.

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Известно [7], что: 4

связность графа не может быть больше, чем [2m /n], где [х] - целая часть числа х; существуют графы с n вершинами и m ребрами, имеющие связность [2m / n]; в сильно связном графе через любые две вершины проходит контур.

Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом.

В неориентированном графе степенью вершины i называется число di инцидентных ей ребер. Очевидно, di ?n - 1, i е X. Граф, степени всех вершин которого равны n - 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Вершина, для которой не существует инцидентных ей ребер (di = 0) называется изолированной. Вершина, для которой сущест-вует только одно инцидентное ей ребро (di = 1) называется висячей.

Известно [7], что: ^ dt = 2 m (данное выражение называется

iGX

«леммой о рукопожатиях» - поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно (при условии, что каждая рука учитывается столько раз, в скольких рукопожатиях она участвовала)); в любом графе число вершин нечетной степени четно.

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны (теорема Эйлера). Обозначим nk - число вершин, имеющих степень к, к = 0, 1, 2,...

к: nk >0

Для ориентированных графов для каждой вершины можно ввести два числа - полустепень исхода d~+ (число выходящих из

нее вершин) и полустепень захода di (число входящих в нее

вершин). В дальнейшем, если не оговорено особо, будем рассматривать графы без петель, то есть без дуг, у которых начальная и конечная вершины совпадают. Известно [7, 15], что:

^ dT = ^ di+ = m; для эйлерова графа имеет место: d+ = d~,

iGX iGX

i = 1,n ; эйлеров граф является объединением контуров, попарно не имеющих общих ребер.

Определим матрицу смежности графа как квадратную матрицу n X n, элемент aij- которой равен единице, если (i, j) е V, и нулю, если (i, j) V, i, j е X. Для неориентированного графа матрица смежности всегда симметрическая.

Определим матрицу инциденций для ребер графа как прямоугольную матрицу n X m, элемент rij- которой равен единице, если

вершина i инцидентна ребру j, и нулю в противном случае, i = 1,n ,

j = 1,m . Аналогично определяется матрица инциденций для дуг графа - как прямоугольная матрицу m X n, элемент rij- которой равен плюс единице, если дуга Uj исходит из вершины i, минус единице, если дуга Uj заходит в вершину i, и нулю в остальных

случаях, i = 1,n, j = 1,m

Деревом называется связный граф без простых циклов, имеющий не менее двух вершин (дерево можно также понимать как связный граф, не содержащий связного частичного графа, состоящего из всех его вершин). Для дерева m = n - 1, а число висячих

вершин равно n1 = 2 + ^ (i — 2) ni . Легко показать, что в дереве

i >2

любые две вершины связаны единственной цепью.

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

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

имеющих степень k, qi - степень i-ой грани. Можно показать, что

p

имеет место ^ qi = 2 m, ^ k pk = 2 m, n + p = m + 2 - формула i=1 k: pk >0

Эйлера [7, 15]. Данные выражения являются необходимыми условиями существования плоских графов с заданными наборами чисел {n} и {pi}.

Любому связному плоскому графу G можно поставить в соответствие двойственный ему связный плоский граф G , определяемый следующим образом: каждой грани графа G соответствует вершина графа G , каждому ребру V графа G, являющемуся граничным для граней z1 и z2, соответствует ребро V графа G , соединяющее соответствующие граням zi и z2 вершины. Понятие двойственного графа тесно связано с понятием двойственности в линейном программировании [7].