Графы и деревья

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

Граф G = (V, Е) задается парой конечных множеств V и Е. Элементы первого множества v1, v2,..., vM называются вершинамиграфа (при графическом представ­лении им соответствуют точки). Элементы второго множества e1, e2, ..., eN называ­ют ребрами.Каждое ребро определяется парой вершин (при графическом представ­лении ребро соединяет две вершины графа). Если ребра графа определяются упоря­доченными парами вершин, то такой граф называют ориентированным – орграфом (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указы­вающую его направление). Ориентированный граф с пятью вершинами и семью ребрами изображен на рис. 3.2.

Рис. 3.2. Пример ориентированного графа

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

Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (например, ребро e7).

Граф без петель и параллель­ных ребер называется простым.

Если ребро е_к определяется вершинами v_iи v_j (будем обозначать этот факт следующим образом: е_k = (v_i, v_j), то говорят, что ребро е_к инцидентно вершинам v_i и v_j.

Граф G(E,U) называется конечным, если множество Е вершин конечно. Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколь­кими ребрами, то такой граф называется мультиграфом. Две верши­ны е_i, е_j ÎЕ называются смежными, если они соединены ребром. Чис­ло ребер, инцидентных данной вершине е_i, называется локальной степенью этой вершины р(е_i). Число ребер r графа G(E,U) определя­ется выражением

где n — количество вершин в графе.

Рассмотрим граф, изображенный на рис. 3.3.

Рис. 3.3. Ориентированный граф

Множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество ребер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. Ребро (5, 3) — является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных сте­пеней для каждой вершины:

р(1) = 3; р(2) = 2; р(3) = 3; р(4) = 2; р(5) = 2; р = (3+2+3+2+2)/2=6.

Важным в теории графов является понятие части графа G(E,U), который обозначается G'(E',U') Í G(E,U).

Множества вершин и ребер части графа являются подмножества­ми вершин и ребер исходного графа Е'ÍЕ, U' ÍU. Многие задачи на графах состоят в определении частей графа с заданными свойствами. Часть графа G'(E',U')ÍG(E,U) называется подграфом графа G(E,U), если Е'ÍЕ, а подмножество U'ÍU образовано только реб­рами, инцидентными вершинам множества Е'.

Полным графом называется граф G(E,U), у которого каждая вер­шина соединена ребрами с остальными вершинами (рис. 3.4).

Рис. 3.4. Полный граф

Обязанность графов

Маршрутом графа G называется последовательность ребер S=(u₁,u₂, ... u_n), в которой каждые два соседних ребра имеют общую вершину, т.е. u₁= (e₁, e₂); u₂= (e₂, е₃); ... u_n= (e_n, е_n+1). Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.

Две вершины е_i и е_j называются связанными, если существует мар­шрут из е_i в е_j.

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

Рис. 3.5. Компоненты связанности графа

Простой цепью, или простым путем, называется маршрут, в ко­тором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна верши­на не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следу­ющий граф имеет цикл S = (1, 2, 3, 5, 4, 1) (рис. 3.6).

Рис. 3.6. Цикл в графе

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

Задание графа

Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Анали­тическое задание состоит в задании элементов множества вершин Е={е₁, е₂, ... е_n} и множества ребер U = {u₁, u₂, ... u_m}.

Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица А размерностью n ´ n называется матрицей смежности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы а_ij= m, если вершины е_i и е_j соединены m ребрами, и а_ij=0, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов, равное количеству вершин графа.

Матрица А размерностью n ´ m называется матрицей инцидент­ности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы b_ij=1, если вершина е_i инцидентна ребру u_j и b_ij=0 в про­тивном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.

Построим матрицы смежности и инцидентности для графа, изображенного на рис. 3.7.

Рис. 3.7. Пример графа.

Матрица смежности будет состоять из пяти строк и пяти столбцов.

Матрица инцидентности будет состоять из пяти строк и шести столбцов.

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

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

Лес - это любой граф без циклов. На рис. 3.8 показаны возможные деревья с пятью вершинами.

Рис. 3.8. Примеры деревьев

Деревья бывают также ориентированные и неориентирование.

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

Если G = (X, А) - неориентированный граф с n вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф графа G, являющийся деревом (в смысле приведенного выше определения). Например, если G - граф, показанный на рисунке (а), то граф на рисунке (б) является остовом графа G, как и граф, изображенный на рисунке (в). Из сформулированных выше определений вытекает, что остов графа G можно также рассматривать как минимальный связный остовный подграф графа G, где «минимальность» понимается в том смысле, что никакое собственное подмножество ребер этого остова не образует связный остовный подграф графа G.