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

Теория графов: основные определения

Теория графов – раздел математики, используемый в информатике и программировании, экономике, логистике, химии.

Что такое граф

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

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

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

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

Если вершины a и b – концы ребра (или начало и конец дуги) графа, то говорят, что вершины a и b инцидентны этому ребру (дуге), также ребро (дуга) инцидентно вершинам a и b. Если вершины a и b – концы ребра, то они (a и b) называются смежными.

Чаще всего рассматривают графы, ребра которых имеют один тип – являются ориентированными или нет.

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

Теория графов также использует понятие «петля» – ребро, выходящее и заходящее в одну и ту же вершину. Граф, в котором есть петли, называется псевдографом.

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

Каждая вершина орграфа характеризуется:

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

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

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

Вершина со степенью 0 называется изолированной.

Висячей вершиной является вершина со степенью 1.

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

Взвешенные графы – это графы, вершинам или ребрам (дугам) которых или и вершинам, и ребрам (дугам) сразу, приписываются некоторые числа. Они называются весами. На втором рисунке показан неориентированный граф, ребра которого взвешены.

Графы: изоморфизм

Понятие изоморфизма используется в математике. В частности, теория графов определяет его так: два графа U и V изоморфны, если в этих графах существует биекция между множествами их вершин: каждые 2 вершины в графе U соединены ребром в том и только том случае, если в графе V связаны ребром те же вершины (которые могут по-другому называться). На рисунке ниже показаны два изоморфных графа, в которых между вершинами, окрашенными в одинаковые цвета и в первом, и во втором графе, существует вышеописанная биекция.

Пути и циклы

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

Теория графов в программировании используется для построения граф-схем алгоритмов.

syl.ru

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

При составлении структурных матриц удобно пользоваться графом схемы. Теория графов и их применение к анализу электрических схем достаточно подробно освещены в работах[26,.31]. Поэтому для основательного изучения этого вопроса рекомендуется читателям обратиться к этим работам. Здесь же приводятся в краткой форме некоторые концепции и свойства графов, дается обзор структурных матриц, их взаимосвязь, т.е. те понятия, которые могут потребоваться при описании алгоритмов машинного анализа схем.

Граф схемы G представляет собой множество ветвей V и вершинY. Каждому элементу схемы соответствует ветвь графа. Каждому узлу соединения элементов в схеме соответствует вершина графа. Граф схемы может быть направленным иненаправленным. В направленном графе каждая ветвь имеет стрелку в том направлении, в котором принимается положительное направление тока через эту ветвь. Эта стрелка указывает также положительное направление напряжения ветви - стрелка направлена от вывода с положительным потенциалом. На рис. 3.1 изображена схема (а), ее направленный (б) и ненаправленный граф (в).

Приведем ряд определений графа, которые потребуются в дальнейшем изложении. Подграфом графа называется подмножество ветвей графа V_iÎ V. Вершина и ветвь инцидентны друг другу, если вершина есть конечная точка ветви. Последовательностью ветвей являются ветви графа или подграфа, которые упорядочены так, что каждая пара соседних ветвей v_i, v_i₊₁, являются инцидентными общей вершине. Например; а, в, f, k, c, в, е, d на рис. 3.1. Кратностьветви - число обходов ветви в последовательности. В предыдущем примере ветвь "в" является двукратной, а остальные ветви однократными. Однократная последовательность содержит только ветви с кратностью, равной единице (например, а, в, е, d, к). Замкнутая однократная последовательность - это последовательность, в которой первая и последняя ветви имеют общую вершину (например: с, d, е, j, к, f, в). В противном случае однократная последовательность является разомкнутой. Степень вершины есть число ветвей, инцидентных этой вершине. Путь есть подграф, ветви которого образуют разомкнутую однократную последовательность, степень вершин в котором не превышает 2. Контур есть подграф, ветви которого образуют замкнутую однократную последовательность, степень всех вершин в котором равна 2. Граф является связным если существует путь между двумя любыми вершинами. Если это условие не выполняется, то граф является не связным. На рис. 3.2. изображена схема и ее граф, состоящие из двух изолированных подграфов. Деревом Т связного графа G называется подграф, который содержит все вершины графа, но не содержит контуров. Количество деревьев может быть конечное множество. На рис. 3.1,г изображено одно из множества деревьев графа. Ветви, принадлежащие дереву Т, называются ветвями дерева. Ветви, не принадлежащие дереву Т, называются хордами (связями). Все хорды, соответствующие данному дереву Т, образуют подграф, называемый дополнением дерева Т_C.

Можно показать, что для связного графа с n вершинами любое дерево имеет n - 1 ветвей. Если граф является несвязным и состоит из p изолированных подграфов, то дерево несвязного графа имеет n - р ветвей. Соответственно, количество хорд графа, имеющего общее количество ветвей q, равно q – n + p. Число r = n - р называется еще рангом графа. Число q – n + p называется связностью графа. Сечением называется такое множество ветвей графа G, удаление которых понижает ранг графа на единицу. Другими словами, сечение делит связной граф на два изолированных подграфа. Например, на рис.3.1,в ветви а, в, е, к образуют сечение, т.к. их удаление делит граф на два изолированных подграфа, а ранг графа станет равным 7 - 2 = 5. Приведем еще ряд определений теории графов, широко применяемые при анализе электрических схем. Граф G является неразделимым, если каждый подграф графа G имеет, по крайней мере, две вершины, общие с его дополнением. Все остальные графы разделимы. Примером разделимого графа является несвязный граф. Связной граф является разделимым, если он содержит, по крайней мере, один подграф, имеющий только одну вершину, общую с его дополнением. Например, граф, изображенный на рис. 3.3,а. Такая вершина называется вершиной сечения по которой связной граф разделяется на два несвязных подграфа. С неразделимостью графа тесно связано понятие циклической связности.Граф циклически связный, если его любые две вершины находятся в контуре.

Дуальные графы. Граф G₂ дуален графу G₁, если r₁ = q₂ a r₂ = q₁, т.е. ранг первого графа равен числу ветвей второго графа и наоборот. Графически дуальность графов можно пояснить таким образом, когда вершина одного графа, соответствует контуру другого графа (см. рис. 3.3,6). Дуальными графы могут быть только планарные. Граф G является планарным, если он может геометрически изображен на плоскости так, чтобы не было двух ветвей, имеющих общую точку, которая не являлась бы вершиной. На рис. 3.3,в изображен непланарный граф, который соответствует трехфазной мостовой схеме.

Приведенный здесь обзор основных понятий теории линейных графов имеет большое значение при анализе электрических цепей. Он позволяет читателю сформулировать наглядную геометрическую интерпретацию основных законов цепей: к контурам применим ЗНК, к сечениям применим ЗТК. На понятии дерева базируются большинство алгоритмов формирования систем линейно-независимых уравнений Кирхгофа. Каждому дереву Т графа G соответствует своя система линейно-независимых контуров и своя система линейно-независимых сечений. Или, как принято в литературе, система главных контуров и система главных сечений. Из определения дерева следует, что каждая хорда дополнения дерева Т_С замыкает путь по ветвям дерева, который является главным контуром этой хорды по ветвям относительно выбранного дерева. Системе хорд соответствует система главных контуров. Положительное направление обхода контура совпадает с направлением хорды Количество главных контуров равно q – n + p.

Главное сечение образуется следующим образом: удаление любой ветви дерева делит дерево на две части, соответственно множества вершин на два подмножества. Главное сечение образуется этой ветвью дерева и хордами, вершины которых принадлежат разным подмножествам. Положительное направление сечения выбирается согласно направлению ветви дерева. Количество главных сечений равно n + p.

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

Матрица инциденций. Для направленного графа с n узлами и q ветвями матрицей инциденций является матрица размером n ´ q

A_a = [a_ij],

где a_ij = 1, если ветвь j инцидентна узлу i и стрелка направлена от узла i;

a_ij = -1, если ветвь j инцидентна узлу i и стрелка направлена к узлу i;

a_ij ₌ 0, если ветвь j не инцидентна узлу i. Например, для графа рис.3.1,b:

Т.к. каждая ветвь инцидентна двум вершинам, то каждый столбец структурной матрицы содержит только два ненулевых элемента (+1 и -1). Следовательно, сумма элементов в каждом столбце равна нулю. Сумма всех строк матрицы также равна нулю, т.е. строки структурной матрицы А линейно зависимы (одна из них равна сумме остальных строк с обратным знаком). Вычеркнув одну из строк матрицы А, получим сокращенную матрицу А размером (n-1)´q с линейно-независимыми строками. Эта матрица именуется далее редуцированной матрицей. инциденций. Матрицу А можно представить следующим образом:

A = [A_T | A_L] (3,8)

где субблок A_T содержит столбцы, соответствующие ветвям дерева, а субблок А_L - хордам. Из матричной алгебры известно, что для любой n´m матрицы максимальное количество линейно независимых строк и линейно независимых столбцов равны. Можно показать, что линейно независимые столбцы матрицы А соответствуют ветвям дерева, т.е. столбцы субблока линейно независимы. Рассмотрим субграф Т, состоящий из ветвей дерева. Для этого субграфа матрица А_T является редуцированной матрицей инциденций размером (n-1)´(n-1). Т.к. субблок Т связан, то n-1 строк матрицы А_T линейно независимы. Соответственно n-1 столбцов матрицы А_T линейно независимы.

Матрица контуров. Для направленного графа G с q-ветвями и n_k контурами матрицей контуров является матрица размером n_k´q

B_a = [b_ij]

где b_ij = 1, если ветвь j входит в контур i и направление ветви совпадает с направлением обхода контура; b_ij = -1; если ветвь j входит в контур i и направление ветви противоположно направлению обхода контура; b_ij = 0, если ветвь j не входит в контур i. Количество контуров может быть сравнительно большим и матрица B_a содержит линейно независимые строки. Ниже будет показано, что ранг матрицы контуров связного графа равен q-n+1.

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

B = [B_T | I] (3.9)

где: Вт субблок "контуры-ветви дерева" порядка (q-n+1)´(n-1); I - единичный субблок порядка (q-n+1)´(q-n+1). Из присутствия единичной матрицы следует, что строки матрицы В линейно независимы.

Если порядок следования столбцов матриц А и В одинаков, т.е. они взаимно соответствуют одним ветвям, то произведение строки матрицы А на транспонированную строку В равно нулю. Это исходит из определения контура как замкнутой однократной последовательности ветвей со степенью вершин равной 2. Если узел j принадлежит контуру i, то узлу j и контуру i инцидентны две общие ветви. Причем ориентация их относительно узла и контура противоположно. Тогда указанное выше произведение содержит два простых слагаемых (±1) с разным знаком. Отсюда следует ортогональность матриц А, В,

А × В' = 0 или В × А' = 0 (3.10)

где штрихом обозначены транспонированные матрицы.

Теперь можно подтвердить утверждение, что любая матрица В_а содержит

q – n + 1 линейно независимых строк. Пусть матрица В_a имеет количество строк больше q – n + 1, которую можно расчленить следующим образом

(3.11)

Тогда с учетом (3.8)

(3.12)

отсюда получим

(3.13)

или

; (3.14)

т.к. , то матрица А¢_T имеет обратную. Умножим (3.14) на , получим:

В₂_T = В₂_L×В_T_,

следовательно

т.е. строки матрицы В₂ является линейной комбинацией строк В.

Для графа рис. 3.1,6 при выбранном дереве, состоящем из ветвей b, e, d, j, k, i, матрица главных контуров имеет вид:

Здесь приняты обозначения главных контуров по обозначениям соответствующих хорд.

Матрица сечений. Для направленного графа G с q ветвями и n_C сечениями матрицей сечении является матрица размером n_C ´ q

Q_a = [q_ij],

где q_ij = 1, если ветвь j входит в сечение i и направление ветви совпадает c прнятым положительным направлением сечения; q_ij = -1, если ветвь j входит в сечение i и направление ветви противоположно положительному направлению сечения; q_ij = 0, если ветвь j не входит в i-ое сечение. Ранг матрицы сечения равен n-1, т.е. из полной матрицы сечения Q_a можно выделить субматрицу с n - 1 линейно независимыми строками, которая называется базовой матрицей сечения Q_б. Из всех базовых матриц при анализе цепей широко используется матрица главных сечений. При соответствующей расстановке строк и столбцов, матрица главных сечений может быть представлена в канонической форме

Q = [I | Q_L] (3,15)

где I - единичный субблок размером (n-1)´(n-1); Q_L- субблок "сечения- ветви хорды" размером (n-1)´(q-n+1). Наличие единичного блока означает также то, что строки матрицы Q являются линейно независимыми.

Для графа рис. 3.1,6 при выбранном дереве, состоящем из ветвей b, e, d, j, k, i, матрица главных сечений имеет вид:

Обозначения главных сечений совпадают с обозначениями соответствующих ветвей дерева.

Легко показать, что любые контур и сечение имеют количество общих ветвей равным 2m [26]. Из них m ветвей имеют одинаковую ориентацию и в контуре и в сечении, т.е. их направление либо совпадает, либо противоположно с положительным направлением сечения и контура. Другие m ветвей имеют разную ориентацию в контуре и в сечении. Если, приэтом, порядок следования столбцов матриц В и Q одинаков, то произведение строки одной матрицы на транспонированную строку другой матрицы имеет m положительных и m отрицательных слагаемых, общая сумма которых равна нулю. Отсюда следует ортогональность матриц В и Q:

B × Q¢ = 0 или Q × B¢ = 0 (3.16)

где штрихом обозначена транспонированная матрица. Из (3.9, 3.15) следует:

следовательно

B_T = -Q¢_L или Q_L = -B¢_T (3.17)

Далее примем обозначение

T = B_T = -Q_L (3.18)

Или

Покажем, что любая матрица Q содержит (n-1) линейно независимых строк. Представим Q_a

Тогда

отсюда

B¢_T + Q_L = 0, Q₂_T × B¢_T + Q₂_L = 0;

Или

Q_2L = Q_2T × Q_L

Тогда

т.е. строки матрицы Q₂ являются линейной комбинацией строк Q.

В соответствии с первым законом Кирхгофа алгебраическая сумма токов ветвей, инцидентных данной вершине равна нулю. Пусть токи ветвей образуют вектор столбец i порядка q´1. Если порядок следования столбцов матрицы А и токов ветвей в векторе совпадают, т.е. взаимно соответствуют одним и тем же ветвям, то уравнение ЗТК в обобщенной форме имеет вид [26]:

A×i = 0 (3.19)

Применительно к сечениям первый закон Кирхгофа трактуется следующим образом: сумма токов сечения равна нулю. Обобщенная форма записи ЗТК имеет вид [26]:

Q×i_v = 0 (3.20)

Второй закон Кирхгофа устанавливает, что алгебраическая сумма напряжений в каждом контуре схемы равна нулю. Пусть напряжения всех ветвей образуют вектор столбец u порядка q´1. Если порядок следования столбцов матрицы А и напряжений ветвей в векторе совпадают, т.е. взаимно соответствуют одним и тем же ветвям, то уравнение ЗНК в обобщенной форме имеет вид[26]:

B×u = 0 (3.21)

Т.к. сумма линейно независимых контуров и сечений равна q. Таким образом, ранг системы структурных уравнений (3.20, 3.21) равен q.

Множество ветвей дерева разбивается на два подмножества - ветви дерева и хорды (ветви дополнения). Соответственно этому вектор напряжений (токов) ветвей можно разбить на два подвектора - вектор напряжений (токов) ветвей дерева и вектор напряжений (токов) хорд:

u = (uD, uX)¢, i = (iD, iX)¢.

Тогда из (3.9, 3.15, 3.20, 3.21) следует:

uX = -B_T×uD (3.22)

или

uX = Q¢_L×uD = -T¢×uD (3.23)

iD = -Q_L×iX (3.24)

или

iD = B¢_T×iX = T×iX (3.25)

Из (3.23 и 3.25) следует, что напряжение всех ветвей схемы можно выразить через напряжение ветвей дерева, а токи всех ветвей через токи хорд (или контурные токи).

или u = Q¢×uD (3.26)

или i = B¢×iX (3.27)

Уравнение (3.27) является частным случаем более общего контурного преобразования[2б], описываемого следующим выражением:

I = B_a×i_K (3.28),

где В_a - некоторая матрица контуров; i_K - вектор контурных токов.

Аналогично уравнение (3.26) является частным случаем более общего преобразования, называемого преобразованием сечений, и описывается формулой:

u = Q_a×u_S (3.29)

где Q_a - некоторая матрица сечений; u_S - вектор напряжений сечений.

Переменные i_K и u_S являются координатами, определяющими состояние схемы в q-мерном векторном пространстве.

Машинный анализ электрических схем заключается в выборе фундаментального дерева, в получении и преобразовании структурных матриц, формировании на их основе расчетной системы уравнений. В [12] описана реализация алгоритма получения структурных матриц В, Q с помощью преобразования матрицы инциденции А. Сам алгоритм получения матрицы А достаточно прост. Исходной информацией для него является таблица соответствия, которая представляет собой таблицу, содержащую обозначения ветвей и инцидентных им вершим, т.е. это, по сути, та же матрица инциденций в сжатой табличной форме. Развернуть ее в матрицу не представляет труда.

Учитывая, что столбцы субблока А_T (3.8) являются линейно независимыми и они соответствуют ветвям дерева, то выделение ветвей дерева сводится к выделению в матрице А линейно независимых столбцов. Для поиска линейно независимых столбцов можно воспользоваться методам Гаусса[32]. Из (3.8, 3.9, 3.10) следует:

т.к. [A_T] ¹ 0, то (3.30)

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

Итак, матричный метод получения В и Q состоит из следующих шагов:

1) формирование матрицы инциденции А из таблицы соответствия;

2) выделение линейно независимых столбцов в матрице А;

3) обращение субблока ;

4) выполнение матричного произведения .

Хотя этот метод прост в реализации, однако он неэффективен. Это связано с необходимостью хранения промежуточных матриц А и , которые являются разреженными (слабозаполненными ненулевыми элементами) и произведение разреженных матриц . Размер матрицы А и равен (n´q) и (n´n), коэффициент заполнения А равен

Итак, полная система уравнений электрической схемы включает уравнения ветвей (3.1) и структурные уравнения (3.6, 3.7). Эта система содержит 2q скалярных уравнения. В ряде случаев полную систему уравнений целесообразно преобразовать к системе порядка q, записанной относительно совместной сиcтемы координат - контурных токов и напряжений сечений. Расположим ветви графа в таком положении, чтобы сначало следовали i-ветви, а затем е-ветви. Представим уравнения ветвей в обобщенной операторной форме:

(3.31)

где Z_i, Y_e - соответственно матрицы обобщенных сопротивлений i-ветвей и проводимостей e-ветвей; J, Е - вектор значений задающих источников в операторной форме.

В соответствии с принятым расположением ветвей структурные уравнения (3.6, 3.7) можно записать в следующей форме:

(3.32)

где В_i, B_e - соответствующие субблоки матрицы контуров;

Q_i, Q_e - соответствующие субблоки матрицы сечений.

Подставив в (3.32) уравнения ветвей (3.31) и используя контурное преобразование (3.28) и преобразование сечения (3.29) получим результирующую систему уравнений в совместной системе координат (I_К, U_S ):

(3.33)

Или в матричной форме:

(3.34)

Система (3.34) содержит q уравнений

Определив по (3.34) переменные I_к, U_s, напряжения и токи всех ветвей определяются по (3.28, 3.29).

Если графсхемы содержит только i-ветви, то уравнение (3.34) вырождается в результирующее уравнение относительно однородной системы координат (I_к) -уравнение контуров:

B×Z×B¢×I_к = -B×E (3.35)

Система (3.35) содержит n – q + 1 уравнение.

Если граф схемы содержит только е-ветви, то уравнение (3.34) вырождается в результирующее уравнение относительно однородной системы координат (U_S) - уравнение сечений

Q×Y×Q¢×U_s =-Q×J (3.36)

В частном случае, когда ветвями дерева являются только е-ветви, а хордами i-ветви, субблоки B_i, Q_e являются единичными (3.9, 3.15). Тогда система (3.34) примет вид:

(3.37)

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

Особенностью больших схем является то, что соответствующие им структурные матрица являются разреженными, т.е. слабозаполненными ненулевыми элементами. Математические операции с такими матрицами являются неэффективными из-за действий с нулевыми элементами. Кроме большого времени вычислений может возникнуть трудность с размещением их в памяти машины. Например, уже для сравнительно небольшой схемы, изображенной на рис. 3.1,а коэффициент заполнения (отношение количества ненулевых элементов к общему количеству элементов) матрицы контуров В равен 17/40. Конечно, хранить в памяти машины полные матрицы контуров и сечений нет необходимости. Достаточно хранить только субблок Т размером (q-n+1)´(n-1). Избежать трудностей можно, если в памяти машины вместо (q-n+1)´(n-1) элементов этого субблока хранить только ненулевые элементы. Одной из форм такого хранения является представление матриц контуров и сечений структурными списками. Структурные списки используются двух видов. В первом случае элементами списков являются номера ветвей с соответствующим знаком. Во втором случае элементами списков являются адреса ненулевых элементов по номеру столбца (строки) матрицы с соответствующим знаком. Например, матрица главных контуров представлена контурными списками вида:

где vX - номер ветви хорды или номер строки матрица контуров; vD- номер ветви дерева или номер столбца матрицы контуров.

Аналогично может быть представленаматрица главныхсечений.Такое представление возможно только для целочисленных матриц, элементами которых являются простые числа 0, I, -I. При таком представлении структурных матриц умножение на них заменяется последовательным сложением тех элементов вектора сомножителя, которые соответствуют номеру ветви (столбца).

studopedia.ru

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

История и применение

Глава 3. Введение в теорию графов

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о кенигсбергских мостах (1736 г.) Однако, она не находила применения в течение почти 100 лет. Интерес к теории возник благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. В 1847 г. Кирхгофом была разработана теория деревьев, которая послужила важным аналитическим средством для исследования электрических цепей. Законы Кирхгофа для напряжений и токов в цепи полностью определяются контурами и сечениями графа этой цепи и не зависят от природы используемых элементов. Поэтому тщательное изучение понятий контура, сечения и дерева графа дало толчок многим открытиям в теории цепей и, кроме того, внесло большой вклад в теорию графов.

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

Граф – математический объект, описываемый двумя множествами: G=( V, E ), где V – так называемое множество вершин, а E – множество дуг.

Элементами множества дуг являются упорядоченные пары вершин, т.е. E={ ( a, b): aÎV, bÎV }, т.о. множество Е является подмножеством декартова произведения V´V. Порядок вершин в парах может и не учитываться, тогда элементы множества Е называют ребрами, а сам граф – неориентированным графом, в противном случае – ориентированным или Орграфом. В некоторых случаях рассматриваются так называемые смешанные графы, в них множество Е состоит из элементов обоих видов: дуг и ребер.

Обозначим вершины v₁, v₂, v₃, ¼, а ребра e₁, e₂, e₃, ¼. Вершины v_i и v_j, определяющие ребро e_k, называются концевыми вершинами ребра e_k=(v_i, v_j), а в случае орграфа – началом и концом дуги e_k соответственно. Говорят также, что ребро e_k (дуга) инцидентно вершинам v_i, v_j или, что вершины v_i, v_j инцидентны ребру (дуге) e_k. Такие вершины называют смежными. Ребра называют смежными в случае, когда они имеют общую концевую вершину. Например, e_k=(v_i, v_j) и e_m=(v_i, v_l) – смежные ребра.

В множестве ребер графа допускается более, чем одно ребро с одинаковыми концевыми вершинами. Такие ребра называются параллельными или кратными. Например: e_k=(v_i, v_j) и e_m=(v_i, v_j) – кратные ребра.

Если обе концевые вершины ребра совпадают, то такое ребро называется петлей. Например: e_k=(v_i, v_i) – петля.

Граф без петель и параллельных ребер называется простым, в противном случае – мультиграфом.

Граф, не имеющий ребер, называется пустым, а не имеющий вершин (а значит и ребер) – нуль‑графом.

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

Количество вершин в графе называется порядком графа.

Степенью или валентностью вершины называется число инцидентных ей ребер. Будем обозначать степень вершины v_i – deg(v_i). Вершина нулевой степени называется изолированной. Вершина степени 1 называется висячей, а ребро, инцидентное ей, называется висячим ребром. Заметим, что петля добавляет двойку к степени вершины.

§ 3.3. Способы задания графов

Рассмотрим три способа задания графов: графический, аналитический и матричный.

1) Графический способ.

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

На рисунке 12 изображен смешанный граф с вершинами v₁, v₂,¼, v₆, ребрами e₁, e₂, e₃, e₅ и дугой e₄. Смежные вершины v₁, v₂, инциденты ребру e₁. Вершины v₁, v₃, инциденты параллельным ребрам e₂ и e₃. Вершине v₄ инциденты петля e₅ и дуга e₄, причем v₄ является началом дуги e₄, а v₅ – концом этой дуги. Степень вершины v₁ равна 3, вершины v₂ – 1, вершины v₃ – 2, вершины v₄ – 3, вершины v₅ – 1, вершины v₆ – 0. Таким образом, вершины v₂ и v₅ – висячие, а вершина v₆ – изолированная. В случае дуги e₄ точнее было бы говорить о полустепенях исхода и захода вершин v₄ и v₅, а именно: полустепень исхода вершины v₄ равна 3, вершины v₅ – 0, полустепень захода вершины v₄ равна 2, вершины v₅ – 1.

2) Аналитический способ.

Граф задают перечислением элементов множества вершин и множества ребер. Для графа, изображенного на рисунке 12, эти множества: V={v₁, v₂, v₃, v₄, v₅, v₆} и Е={e₁, e₂, e₃, e₄, e₅}, где e₁=(v₁, v₂), e₂=(v₁, v₃), e₃=(v₁, v₃), e₄=(v₄, v₅), и e₅=(v₄, v₄).

3) Матричный способ.

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

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

Таким образом, для графа на рисунке 12 матрица инциденций такова:

	e₁	e₂	e₃	e₄	e₅
	v₁
	v₂
I=	v₃
	v₄
	v₅			-1
	v₆

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

б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: . Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:

	v₁	v₂	v₃	v₄	v₅	v₆
	v₁
	v₂
S=	v₃
	v₄
	v₅
	v₆

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

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

Представление графов матрицами очень удобно при решении задач на компьютере.

studopedia.ru

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

4.1. Основные понятия и определения

Пусть дано множество V = {v₁, v₂, …, v_n} и в V определено семейство U = {u₁, u₂, …, u_m} пар элементов u_k₌ {v_i, v_j}, (k = 1, m) произвольной кратности и упорядочения. Пара {V, U} именуется: граф. Графы, как правило, обозначают прописными латинскими буквами, например, G, H. Принято также писать G(V, U) для того, чтобы определить некоторый конкретный граф G.

Элементы v₁, v₂, …,v_n называются вершинами графа, а пары u_k₌ {v_i, v_j}, (k = 1, m) — ребрами.

Определению графа можно дать следующую интерпретацию. Пусть имеем описание графа:

G(V,Е) = {{ v₁, v₂, …, v₆}, { { v₁, v₃ }, v₅, v₁, {v₃, v₄},

v₂, v₃, {v₃, v₃ }}}.

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

v₁ v₄ v₂

V₆

v₃ v₅

Рисунок 4.1

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

Для ориентированного ребра определены понятия начальной и конечной вершины. Начальная вершина записывается в начале пары вершин, определяющих дугу,а конечная — в конце. Так на рисунке 4.1 ребра v₅, v₁ и v₂, v₃ являются дугами. Они представлены упорядоченными парами вершин и, в связи с этим, обозначены так же, как обозначаются упорядоченные множества.

Ребра {v₁, v₃}, {v₃, v₄} неориентированы. Для любого неориентированного ребра полагают, что {v_i, v_j} = {v_j, v_i} так же, как и в случае неупорядоченных множеств. Ребро {v_i, v_i} называется петлей. На рисунке 4.1 имеем петлю {v₃, v₃}. Петли обычно не ориентированы.

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

Граф, у которого все ребра ориентированы, называется ориентированнымили орграфом.

На рисунке 4.1 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.

Многие теоремы и определения в теории графов могут быть отнесены как к ориентированным, так и к неориентированным графам. В таких случаях для обозначения ребер применяют круглые скобки, например, ребро {v₃, v₄} в графе рисунок 4.1 можно обозначать (v₃, v₄) либо (v₄, v₃), а ребро v₅, v₁ — соответственно как (v₅, v₁), указав при этом, что данное ребро представляет дугу. Принято также обозначение всех ребер круглыми скобками как в случае ориентированных графов, так неориентированных, если совершенно ясно о каком из типов этих графов идет речь в тексте.

Некоторые вершины графа G могут не войти в список пар. Такие вершины именуются изолированными. В рассмотренном примере это вершина v₆. Граф, у которого все вершины изолированы, именуется нуль‑графом. Множество ребер такого графа пусто.

Антиподом нуль‑графа является полный граф. Ребрами полного графа являются всевозможные пары его вершин.

Как в случае ориентированного графа, так и в случае неориентированного — говорят, что ребро инцидентно паре определяющих его вершин.

Одной и той же паре вершин можно поставить в соответствие множество инцидентных ребер. Такие ребра называются кратными. Так на рисунке 4.2 представлена пара вершин (v_i, v_j), инцидентных трем различным ребрам u₁, u₂, u₃. Одно из них направлено, а два — нет.

u₁

v_i u₂ v_j

u₃

Рисунок 4.2

Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так графы, представленные на рисунках 4.1 и 4.2 плоские. Примеры не плоских графов будут рассмотрены ниже в разделе 4.3.

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

Граф H называется частью графа G или частичным графом H  G, если множество его вершин V(H) содержится в множестве вершин V(G) графа G и все ребра H являются ребрами G. Частным, но важным типом частичных графов являются подграфы.

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

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

StudFiles.ru