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

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

Считается, что теория графов зародилась в XVIII столетии в г. Кенигсберге (ныне г. Калининград), жители которого пытались решить задачу о переходе мостов города (река Прегель) по такому маршруту, в котором бы были пройдены все мосты, но каждый мост был пройден только один раз (рис. 3.1, а). Эту задачу удалось решить Эйлеру. Он показал, каким условиям должен удовлетворять граф, полученный по схеме мостов, (рис. 3.1, б), чтобы такая задача имела решение.

Рис. 3.1. Схема мостов (а) и граф маршрутов (б)

Графом называется совокупность вершин (узлов) и связанных с ними ребер (ветвей). Граф можно задать в виде G = < V, E >, где V – множество вершин; E – отношение на V (E Ì V ´ V) – множество ребер. На рис. 3.2, а показан граф G, в котором множество ребер E есть { a, b, c, d, e, f, g }, а множество вершин V = {1, 2, 3, 4, 5}.

Подграфом называют такую часть графа, которая включает в себя некоторые вершины и ребра графа, причем среди ребер могут быть только те, которые связывают вершины подграфа. На рис. 3.2, б показан подграф G' графа G.

Рис. 3.2. Граф G (а) и его подграф G' (б)

Направленный (ориентированный) граф имеет ребра, на которых указаны направления. Ребра направленного графа называют дугами. На рис. 3.3, а показан ориентированный граф.

Рис. 3.3. Ориентированный граф (а), сечения дерева графа (б)

Степенью вершины V_i графа называют число ребер, инцидентных этой вершине. Термин «инцидентность» означает отношение объектов типа «проходят через…», «соединены с…». Две вершины называют смежными, если они соединены ребром. Например, на рис. 3.3, а вершина 4 смежна с вершиной 2, так как они соединены посредством ребра с.

Граничные вершины ребра – вершины, инцидентные этому ребру.

Кратные ребра – ребра с одинаковыми граничными вершинами.

Маршрутом (путем) S называют любую последовательность ребер, в которой соседние ребра инцидентны одной и той же вершине. В графе на рис. 3.2, а последовательности (a, d, e, g) и (b, g) – маршруты, а последовательность (d, g) маршрутом не является, так как ребра d и g инцидентны разным вершинам. Если в маршруте нет повторяющихся ребер, то он называется цепью. Если цепь начинается и кончается в одной и той же вершине, то она называется циклом-контуром. Количество ребер в S называют длиной маршрута.

Если каждому ребру графа приписано какое-то число (вес), то граф называют взвешенным.

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

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

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

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

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

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

Контуром k -й хорды называют множество ребер, образующих цикл в графе, который получается при добавлении k -й хорды к дереву.

Сечением ветви дерева называют множество ребер, пересекаемых линией сечения, если:

а) среди ветвей дерева пересекается единственная;

б) линия сечения замкнутая и любое ребро может пересекаться не более одного раза.

Для графа, показанного на рис. 3.3, б, сечения ветвей его дерева записываются: a – (a, e); b – (b, d, e); c – (c, d, e).

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

Первая матрица инциденций M для неориентированного графа представляет собой матрицу, строки которой соответствуют вершинам, а столбцы – ребрам. Элемент матрицы равен единице, если вершина инцидентна ребру. В противном случае элемент матрицы принимает значение ноль.

Для ориентированного графа элемент матрицы инциденций M равен +1, если вершина, инцидентная дуге, является начальной вершиной дуги (т. е. дуга исходит из этой вершины). Элемент равен –1, когда дуга входит в вершину. Если вершина не инцидентна дуге, то элемент матрицы равен 0. Так, для графа на рис. 3.3, а матрица M имеет следующий вид:

(3.1)

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

Вторая матрица инциденций N устанавливает соответствие между ребрами графа и независимыми контурами графа. В зависимости от выбранной системы независимых контуров – дерева графа можно составить разные матрицы N. Число независимых контуров обозначают через k. Каждой строке матрицы N ставят в соответствие контур, таким образом, число строк в матрице N равно числу независимых контуров k; каждому столбцу матрицы N ставят в соответствие ребро, и число столбцов матрицы N равно числу ребер – m.

Матрица N составляется по следующим правилам. Независимые контуры нумеруют от 1до k; выбирают направления обхода контуров; начиная с первого выполняют обход контуров в соответствии с выбранными направлениями; проверяют, совпадает ли направление очередного ребра с направлением обхода контура: если да, то в соответствующем столбце матрицы N ставится +1, в противном случае –1; для ребер, не вошедших в рассматриваемый контур, в соответствующие столбцы проставляют нули.

Так, если в качестве дерева графа на рис. 3.3, а взять подграф с ребрами (a, b, c), то при добавлении хорды d образуется контур (a, d, c), а при добавлении хорды e – контур (c, e, b). Для такой системы независимых контуров матрица N имеет вид:

. (3.2)

Матрица смежности A является квадратной матрицей и для невзвешенного графа состоит из нулей и единиц: A_i,j = 1, если (i, j) Î E, и A_i,j = 0 в противном случае. Для взвешенного графа A_i,j равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Если граф ориентированный, то для каждого ребра ставится A_i,j = 1, если направление от i к j, а A_j,i = – 1 и наоборот. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали. Для графа на рис 2.14, а матрица A имеет следующий вид:

(3.3)

С помощью матриц M и A легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной недостаток этих матриц заключается в том, что они требуют, чтобы объем памяти был достаточен для хранения соответственно nm и n ² значений.

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

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

При работе с графами на компьютере удобно вершины графа сопоставлять с числами от 1 до n, где n = | V | – количество вершин графа, и рассматривать V = {1, 2, … n }. Ребра нумеруют числами от 1 до m, где m = | E |. В дальнейшем ребра будем именовать не буквами, а цифрами.

3.2. Применение теории графов
для моделирования электрических сетей

Электрические сети современных ЭЭС насчитывают сотни и даже тысячи ЛЭП и трансформаторов. Расчеты режимов сложных схем электрических сетей требуют специальных моделей представления схем и компактной записи уравнений. Такими моделями являются графы и матрицы.

Линии, трансформаторы и другие элементы электрической сети представляются в расчетах своими схемами замещения, состоящими из ветвей с сопротивлениями и проводимостями. Все шины электрических станций и подстанций являются узловыми точками сети. Количество этих узловых точек или узлов схемы сети обозначим буквой n, а количество ветвей, соединяющих эти шины, m. Если сеть не содержит замкнутых контуров, то количество узлов и ветвей различается на 1:
n = m + 1. При наличии контуров n = m + 1 – k, где k – количество независимых контуров.

Графы являются топологическими моделями схем электрических цепей.

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

Элементами ЭЭС, которые моделируются ребрами графа, являются ЛЭП, трансформаторы, реакторы, батареи конденсаторов и др. Как правило, все они представляются П-образными схемами замещения и поэтому имеют элемент связи между двумя граничными узлами – продольная ветвь, и элементы, связывающие узлы с нейтральной точкой системы N, – поперечные ветви (рис. 3.4).

Рис. 3.4. П-образная схема замещения (а) и ее граф (б)

Для ЛЭП:

, (3.4)

(3.5)

Обычно Z = (r ₀ + jx 0) l и .

Для трансформатора:

(3.6)

при k _т > 1. Если k _т = 1, то из (3.6) получается Г-образная схема замещения трансформатора.

Для реакторов и батарей конденсаторов, включенных в виде продольных элементов сети, параметры схемы замещения: Z = jX _р и
Z = jX_c. Y ₁ = Y ₂ = 0 (Y ₁ или Y ₂ может быть отлично от нуля и моделировать потери активной мощности в реакторе или батарее конденсаторов). В случае их включения в виде поперечных ветвей: Z = 0, а Y ₁ и Y ₂ представляются одной поперечной ветвью – Y шунта: и . Аналогично могут представляться своими схемами замещения электрические нагрузки.

Рассмотрим пример схемы электрической сети, состоящей из ЛЭП и трансформатора (рис. 3.5, а). Ее схема замещения есть две соединенные между собой П-образные схемы замещения – ЛЭП и трансформатора, а граф будет состоять из двух графов П-образных схем (рис. 3.5, б).

Рис. 3.5. Схема простой электрической сети (а) и ее граф (б)

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

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

Для моделирования топологии схем электрических сетей используют матричные модели, отражающие свойства графов. Это матрицы инциденций и смежности. В практических расчетах более удобной является компактная форма записи, например в виде перечисления ребер графа. Так, для графа рис. 3.7 массив имен ребер L может быть записан в следующем виде:

(3.7)

В первой строке массива L указывается номер (имя) начального узла, а во второй того же столбца – номер (имя) конечного узла. Пара номеров узлов в столбце образует имя ветви, например, для ветви b это 2 – 3.

Рис. 3.6. Схема электрической сети из восьми узлов и десяти
ветвей (а) и ее граф (б)

Рис. 3.7. Граф сети без изображения ребер, связанных
с нейтральной плоскостью

Рис. 3.8. Многослойный граф

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

3.3. Матричные формы моделей
электрических сетей и их режимов

Каждая продольная ветвь в графе электрической сети характеризуется сопротивлением Z _j = R_j + jX_j, а поперечная ветвь – проводимостью
Y _i = G_i + jB_i (j = 1, 2,…, m; i = 1, 2,…, n), которые образуют матрицы
параметров электрической сети – матрицу сопротивлений продольных ветвей и матрицу-столбец проводимостей поперечных ветвей – шунтов:

(3.8)

Здесь Z _{в jj} = Z _j, а Y_{N i} = Y _i. Недиагональные элементы матрицы Z _в обычно равны нулю, хотя в некоторых случаях учитывают взаимные сопротивления ветвей, которые могут быть отличны от нуля, например для близко расположенных ЛЭП возможно наличие взаимной индукции.

Кроме пассивных ветвей в сети существуют активные ветви, включающие источники ЭДС и тока. Эти ветви, как правило, являются поперечными и моделируют генераторы электрических станций (ЭДС) и потребителей электрической энергии (источники тока), – рис. 3.9, а.

(3.9)

Ветвь с ЭДС в действительности содержит еще и сопротивление и по сути является источником напряжения, которое зависит от нагрузки. В установившемся режиме достигается постоянство значения напряжения генераторов электростанций посредством специальных устройств регулирования и можно пренебречь влиянием сопротивлений генераторов на их напряжение. В дальнейшем будем считать эти ветви источниками ЭДС.

Принято не изображать на графе сети не только шунтирующие проводимости, но и активные поперечные ветви с ЭДС и источником тока, однако источник тока все же задают упрощенным изображением в виде стрелочки, направленной в узел (рис. 3.9, б). Это показывает, что в сеть «вливается» извне ток генерации или нагрузки (с обратным знаком). Такие токи называются токами инъекции (injection current) или задающими токами.

Рис. 3.9. Изображения поперечных ветвей

Матрицы E и J задают режим работы электрической сети и являются векторами независимых переменных. Они относятся к режимным параметрам электрической сети. Другие режимные параметры называются зависимыми переменными. К ним относятся напряжения в узлах, токи и напряжения в продольных ветвях и ряд других параметров режима:

U – матрица напряжений в узлах (узловые напряжения);

I – матрица токов ветвей;

D U – матрица напряжений в ветвях (падения напряжения на сопротивлениях ветвей);

S _в^(н) – матрица потоков мощности в начале ветвей;

S _в^(к) – матрица потоков мощности в конце ветвей;

D S _в – матрица потерь мощности в ветвях.