Элементы теории графов 1 страница

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

· стратегии построения структуры систем энергетики* транспорта, связи, ин­формационных систем;

· выбора оптимальных режимов функционирования;

· анализа связанности отдельных подсистем и элементов;

· планирования производства и управления проектами создания, монтажа, ра­циональной эксплуатации, реконструкции;

· оптимизации маршрутов и потоков товаров и услуг.

Ряд этих задач может быть представлен в формальной постановке, и со­провождаться общими решениями на основе теории графов, которая примени­ма для любых геометрических конфигураций, состоящих из множества V{v_i} точек, называемых вершинами графа v_i Î V и множества E { e_j } линий, называе­мых ребрами e_j Î E (рис. 2.8).

Рис. 2.8.

Таким образом, граф G = (V,E)–математическая система, состоящая из двух множеств V и Е, элементы которых v_i Î V и e_j Î E называют вершинами и ребрами (элементами графа)и представляют как V Î G; E Î G.

При анализе систем с их отдельными компонентами удобно связывать вершины графа, а с парами взаимодействующих компонент – ребра. Построен­ный таким образом граф называют структурным. Пример. Граф, представлен­ный на рис. 2.8, состоит из трех компонент: A –множества вершин V = {v 1, v ₄} и ребер E = {е 5, e 4}; B –множества вершин V = {v 2, v ₃, v ₆} E = {е 1, e 2, е 3, e 6}; C – множества вершин V = {v 5}. Ребра e 1, e 3называются параллельными; ребро e 4– петлей; вершина v ₄ – висячей; v ₅ – изолированной.

Если (a, b) Î E –ребро, a a Î V и b Î V –вершины, то ребро (a, b) = e на­зывается инцидентным вершинам a и b из множества V. Вершины a и b инци­дентны ребру (a, b) = e и являются его граничными точками. Различные ребра могут быть инцидентны одной и той же паре вершин. Их называют кратными. Граф, содержащий кратные ребра, называется мультиграфом. Например, ребро е 2графа рис. 2.8 инцидентно его вершинам v ₂ и v ₃. Ребра е 1 и е 3 –кратные.

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

Если для двух графов G 1 = (V 1, E 1)и G 2 = (V 2, E 2) существует взаимно однозначное соответствие между V 1и V 2, а также между E 1и E 2,сохраняющее отношение инцидентности, то графы называются изоморфными (рис. 2.9).

Рис. 2.9. Изоморфность графов: а)– исходный, б)–изоморфный данному

Число ребер, e_j инцидентных данной вершине v_i Î V называется локальной степенью r(v_i) этой вершины. Число ребер r Î G произвольного графа опре­деляется при помощи локальных степеней его вершин выражением

.

Граф называется однородным степени n, если локальные степени во всех его вершинах равны r(v_i) = n. Граф, ребрами которого являются все возмож­ные пары сочетаний различных его вершин (каждые две различные вершины смежны), называется полным. Для полного графа локальные степени всех вер­шин также равны, а число ребер определяется как

,

где r(v_i) = n – локальная степень вершин полного графа v_G.

Подграфом G_A графа G = (V,E)называется граф, в который входит лишь часть вершин графа G,образующих множество A Í V, вместе с ребрами, со­единяющими эти вершины.

Частичным графом G_B по отношению к графу G = (V,E)называется граф, содержащий только часть ребер графа G _,образующих множество B Í E. На­пример, область, очерченная пунктиром на рис. 2.10 является подграфом G_A с вершинами A = { b,c,d,e }и ребром E = { cd }, а область, выделенная жирными ребрами, – частичным графом G_B с вершинами V = { a,b,c,d,t,f }и ребрами B = { ab,bf,fe,cd }.

Рис. 2.10. Подграф G_A и частичный граф G_B исходного графа G

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

Граф называется вырожденным или нуль-графом, когда он не имеет ре­бер G₀ = E = Æ. Обратного быть не может, то есть G₀ = V = Æ.

Маршрут, цепь, цикл. При рассмотрении сложнозамкнутых схем, к ко­торым относятся электрические сети, сети связи, информационные системы не­обходимы понятия маршрута (пути), цепи, цикла. Зафиксировав некоторую вершину графа можно, последовательно двигаясь по его смежным ребрам, при­дти в другую вершину или вернуться в исходную. Конечная последователь­ность ребер e ₁, e ₂,…, e_n графа (не обязательно различных) называется мар­шрутом длины n, если существует последовательность v ₀, v ₁,…, v_n n + 1 (не обязательно различных) вершин. Одно ребро рассматривается как маршрут единичной длины. Маршрут замкнут, если начальная v ₀ и конечная v_n вершины совпадают v ₀ = v_n, и не замкнут, если v ₀ ¹ v_n.

Пример. На рис. 2.11 последовательность ребер e ₁, e ₄, e ₄, e ₅, e ₅, e ₇ образует незамкнутый маршрут (путь) длиной 6 единиц, а e ₃, e ₂, e ₇, e ₄, e ₆–замкнутый. Если все ребра, составляющие маршрут, различны и начальная и конечная вер­шины не совпадают, он называется цепью (последовательность ребер e ₁, e ₄, e ₄, e ₅ на рис. 2.11). Если цепь замкнута, маршрут называется циклом (последова­тельность ребер e ₁, e ₄, e ₄, e ₅ на рис. 2.11).

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

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

Пример. Последовательность ребер от исходной вершины v ₀ графа рис. 2.12 составляет эйлеров цикл: C = { v ₀, v ₃, v ₁, v ₀, v ₄, v ₁, v ₂, v ₅, v ₄, v ₂, v ₀}.

Рис. 2.11. Иллюстрация понятий «маршрут (путь)», «цепь», «цикл»

Рис. 2.12. Эйлеров цикл

Для того чтобы в графе имелась эйлерова цепь, содержащая все его ребра в по одному разу (начальная и конечная вершины маршрута не совпадают), не­обходимо и достаточно, чтобы v_i и v_j были единственными вершинами нечетной степени (рис. 2.13). На любом связном графе с 2 ∙ k нечетными вершинами имеет­ся семейство из k цепей, которые в совокупности содержат все ребра графа в точности по одному разу (рис. 2.14).

Рис. 2.13. Граф, содержащий эйлерову цепь

Рис. 2.14. Граф, содержащий семейство, состоящее из 2-х эйлеровых цепей

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

При решении задач, связанных, с расчетом электрических цепей требует­ся определение числа независимых контуров (циклов). Эта задача решается пу­тем определения цикломатического числа γ (G)графа G,имеющего n вершин, m ребер и r компонент связности: γ (G) = m – n +r.

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

Начальная вершина называется корнем. Из корня выходят ребра - ветви дерева. Каждое дерево с и вершинами имеет n – 1 ребер. Если все вершины како­го-либо графа принадлежат дереву T, то дерево T покрывает граф (рис. 2.16).

Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Лес k, содержащий я вершин, имеет n – k ребер. Число различных деревьев, которые можно построить на n данных вершинах равно t_n = n^{n –} 2.

Рис. 15. Граф – дерево

Рис. 16. Дерево T = { e ₁, e ₆, e ₄, e ₅}, покрывающее граф

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

Рис. 2.17. Двудольный граф

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

Разделяющим множеством называется множество ребер связного графа, после удаления которых, он становится несвязным. Например, на рис. 2.18, б множество ребер { e ₇, e ₉, e ₅, e ₃}графа G является разделяющим и его удаление приводит к появлению двух компонент G ' и G ''исходного графа.

Разрезом называется разделяющее множество, которое не имеет собст­венного разделяющего подмножества. Например, множество { e ₇, e ₉, e ₅, e ₃} не является разрезом, так как оно содержит разделяющее подмножество { e ₇, e ₉, e ₅} (рис. 2.18,в). Это подмножество не имеет собственных разделяющих подмно­жеств и поэтому является разрезом.

Рис. 2.18. Разделяющие множества и разрезы: а)исходный граф; б)исходный граф после удаления ребер, принадлежащих разделяющему множеству; в) исходный граф после удаления ребер, принадлежащих разрезу; г) мост

В системах электроснабжения разрез – совокупность минимального коли­чества элементов, одновременный отказ которых приводит к полной потере пи­тания узла нагрузки. Это определение определяет реберную связность. Мини­мальные разрезы называются простыми. Разрез, состоящий из одного ребра e (рис. 2.18, г)), называется мостом. Если удаление ребер, принадлежащих разре­зу, делит граф на три и более компоненты, то разрез не может быть простым.

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

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

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

Дуга e (v, w) считается положительно инцидентной ее конечной вершине w, если она направлена от вершины v к w. Число дуг, положительно инцидент­ных вершине v_i называется положительной степенью v_i и обозначается δ⁺(v_i). Отрицательная степень вершины обозначается δ^–(v_i). Число дуг ориентиро­ванного графа определяется как

В однородном степени δ⁺ = δ^– = k ориентированном графе с n вершинами и r дугами число вершин .

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

Аналогично неориентированному графу в ориентированном графе вво­дятся понятия ориентированного маршрута, пути, цикла. Ориентированный цикл называется контуром.

Ориентированный граф является ориентированным деревом, если он об­разует дерево в неориентированном смысле и единственная цепь между корнем v ₀ и любой другой вершиной w является путем из v ₀ в w.

В ориентированном графе дуги разреза могут быть разделены на два множества: дуги, направленные из W ' к W, и направленные из W к W '. Удаление первого множества разрывает все пути из W ' к W, а второго – из W к W '.

Отношения на графах. Каждый ориентированный граф G определяет некоторое отношение на множестве вершин V. Это отношение записывается как v_iRv_j, что означает, что в графе G есть дуга с направлением от v_i, к v_j. Отноше­нию со свойством рефлексивности vRv соответствует петля в вершине графа. Симметричному отношению соответствует граф с неориентированными реб­рами. Например, отношение «не равно ≠» на множестве A = {1, 3, 4, 20} пред­ставлено ненаправленным графом (рис. 2.19, а), а отношение «больше >»– на­правленным (рис. 2.19, б).

Рис.2.19.

Граф, соответствующий транзитивному отношению, обладает следую­щим свойством: для каждой пары ориентированных или неориентированных ребер v_iv_j, v_jv_k имеется замыкающее ребро (дуга) v_iv_k.

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

Теоретико-множественное представление графов. Для ориентирован­ного графа G (V) задается множество вершин V и соответствие Q, которое пока­зывает их связь – отображение множества V в V. Для каждой вершины v_i графа G (V) соответствие Q определяет множество вершин G (v_j), i ≠ j, в которые мож­но непосредственно попасть из вершины v_i.

Множество G ^-1(v_i) определяет обратное отображение всех вершин, из которых можно непосредственно попасть в вершину v_j. Таким образом, ориен­тированный граф задается перечислением (списком) либо множеств G (v_j), либо G ^-1(v_i) для всех вершин графа. Такой способ более компактен и часто применя­ется в иерархических системах, а определение графа полностью совпадает с оп­ределением отношения на множестве. Пример множественного задания структуры (рис. 2.20) сводится к следующим системам множеств:

.

Рис. 2.20.

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

Матрица инциденций. Графу G с n = 6 вершинами и m = 8 ребрами (рис. 2.21) соответствует матрица, включающая n строк и m столбцов (6 × 8). Эле­мент ее определяется как

.

Рис. 2.21. Исходный граф G

Для графа, представленного на рис. 2.21, матрица инциденций имеет вид

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

Элементы матрицы инциденций направленного графа имеют значения

Если два графа имеют одинаковые матрицы инциденций, они изоморфны.

Матрица смежности вершин. Для ориентированных и неориентирован­ных графов строится квадратная матрица смежности вершин. Элемент ее на пе­ресечении i -й строки и j -го столбца равен числу ребер, инцидентных одновре­менно i -й и j -й вершинам (направленных от i к j в случае ориентированного графа). Для неориентированного графа (рис. 2.21), матрица смежности вершин симметрична относительно главной диагонали и имеет вид

.

Матрица смежности ориентированного графа дает число ориентирован­ных маршрутов длины и между любыми двумя вершинами.

В матрице смежности ребер Е строки и столбцы отвечают ребрам графа. Элемент матрицы смежности ребер а _ij = 1, если e_i и e_j различные ребра с общей граничной точкой и а _ij = 0, если они не имеют общего конца. Матрицу смежно­сти ребер графа G можно рассматривать как матрицу смежности вершин для нового графа G ', вершины которого – ребра исходного графа G, а ребра – пары e_i, e_j. Такой граф называется смежностным. Существование его объясняет двойственность между вершинами и ребрами. Для построения смежностного графа G ' на каждом ребре исходного графа G (рис. 2.22) выбирается фиксиро­ванная точка e ' например, середина ребра. Пара таких точек e ' _i, e ' _j – новых вершин графа G ' – соединяется ребром тогда, когда соответствующие ребра e_i и e_j имеют общую вершину в графе G.

Рис. 2.22. а) исходный граф G; б) смежностный граф G'

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

Например, граф рис. 2.21 имеет матрицу путей из вершины v ₂ в v ₁:

.

Аналогично составляются матрицы циклов и разрезов. Строки их соответ­ствуют перечислению ребер, принадлежащих циклу или разрезу, а элементы принимают значение 1 или 0 в зависимости от того, принадлежит ребро циклу (разрезу) или нет. Большинство задач требует анализа минимальных разрезов, поэтому порядок матрицы разрезов может быть существенно сокращен.

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

Алгоритм упорядочения вершин сводится к следующему.

1) В подмножество нулевого уровня N ₀ включаются все вершины v_i, у ко­торых G ^­1(v_i) ≠ Æ, что означает, что из этого множества вершин дуги только вы­ходят, а символ G ^-1 означает обратное отображение N ₀ = { v_i: G ^-1(v_i) = Æ}. При этом производится последовательная нумерация вершин.

2) В множество первого уровня N ₁ включаются все вершины v_i, у которых G ^­1(v_i) Ì N ₀, за исключением N ₀: N ₀ = { v_i: G ^-1(v_i) Ì N ₀}\ N ₀. Последовательная нумерация вершин продолжается дальнейшим при­своением меток i = l + 1, l + 2,... l + p.

3) В подмножество второго уровня N ₂ включаются все вершины v_i, у ко­торых

.

Реализуется дальнейшая нумерация i = l + p + 1, l + p + 2,... l + p + t.

4) В подмножество третьего уровня N ₃ включаются все вершины v_i, у ко­торых G ^­1(v_i) Ì(N ₀ È N ₁ È N ₂), за исключением N ₀ È N ₁ È N ₂:

после чего процесс нумерации вершин продолжается.

5) Данный процесс ведется до тех пор, пока не будут пронумерованы все вершины графа. Множество вершин последнего уровня определится как

,

где r – наименьшее целое число, такое, что G (N_r) = Æ, то есть, нет больше вер­шин, в которые бы отображалось N_r.

Пример. На рис. 2.23 показаны неупорядоченный и упорядоченный по уровням графы.

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

Пример. Исходный граф изображен на рис. 2.24. Матрица смежности вершин этого графа с опущенными для простоты нулями, имеет вид:

A

B

C

D

К

F

G

Н

I

J

К

L

М

N

A

B

C

D

E

F

G

Н

I

J

К

L

М

N

Далее составляем строку Λ₀, в которой подсчитываем суммы элементов в соответствующих столбцах этой матрицы

Дата добавления: 2015-04-30