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

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

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

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

Понятие графа опирается на понятие множества. Графом можно назвать объект, состоящий из двух множеств: точек и линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается X = {x1, x2, …, xn}, |X| = n и называется множеством вершин. Множество линий, соединяющих любые пары вершин, (xi, xj) Î X называется множеством ребер или дуг и обозначается U = {u1, u2, …, um}, |U| = m.

Граф, у которого все вершины “помечены” целыми числами от 1 до n, называется помеченным. Числа 1, 2, …, n называют метками графа и обозначают вершины графа G через 1, 2, …, i, …, n или x1, x2, …, xi, …, xn, или x(1), x(2), …, x(i), …, x(n). Причем все вышеуказанные записи являются равносильными. Заметим, что для реальных задач необходима нумерация элементов. Поэтому в дальнейшем будем рассматривать помеченные графы. Аналогичным образом помечаются ребра.

Тогда графом можно считать математический объект, который обозначается G = (X ,U) и состоит из множества вершин и множества ребер или дуг, находящихся между собой в некотором отношении.

В общем случае множество линий, соединяющих любые пары вершин U, можно представить в виде U = Способы задания графов и виды графов - №1 - открытая онлайн библиотека  È Способы задания графов и виды графов - №2 - открытая онлайн библиотека  È Способы задания графов и виды графов - №3 - открытая онлайн библиотека , где Способы задания графов и виды графов - №1 - открытая онлайн библиотека ─ подмножество неориентированных линий, для которых несуществен порядок соединения вершин. Подмножество Способы задания графов и виды графов - №1 - открытая онлайн библиотека  называется подмножеством ребер. Причем каждое ребро ui Î Способы задания графов и виды графов - №1 - открытая онлайн библиотека  определяется неупорядоченной парой вершин xk, yl, которые оно соединяет. Записывается ui = (xk, yl) или ui = (yl, xk).

Способы задания графов и виды графов - №2 - открытая онлайн библиотека  ─ подмножество ориентированных линий, для которых существен порядок соединения вершин. Подмножество Способы задания графов и виды графов - №2 - открытая онлайн библиотека  называется подмножеством дуг. Причем каждая дуга ui Î Способы задания графов и виды графов - №2 - открытая онлайн библиотека  определяется упорядоченной парой (кортежем длины два) вершин xk, yl, которые ui соединяет. Записывается ui = <xk, yl>. Заметим, что ui = <xk, yl> и uj = <yl, xk> ─ это различные дуги в графе G.

Способы задания графов и виды графов - №3 - открытая онлайн библиотека  ─ подмножество линий, каждая из которых выходит и входит в одну и ту же соответствующую этой линии вершину. Называется Способы задания графов и виды графов - №3 - открытая онлайн библиотека  подмножеством петель. Каждая петля ui Î Способы задания графов и виды графов - №3 - открытая онлайн библиотека  может определяться упорядоченной или неупорядоченной парой, например вида ui = <xk, xk>, ui = (xk, xk).

Граф G = (X, U), у которого Способы задания графов и виды графов - №2 - открытая онлайн библиотека , Способы задания графов и виды графов - №1 - открытая онлайн библиотека , Способы задания графов и виды графов - №3 - открытая онлайн библиотека  ¹ Æ, называется смешанным. На рис. 15.1 показан смешанный граф G. Здесь |X| = 6, |U| = 13; U = Способы задания графов и виды графов - №1 - открытая онлайн библиотека  È Способы задания графов и виды графов - №2 - открытая онлайн библиотека  È Способы задания графов и виды графов - №3 - открытая онлайн библиотека ; Способы задания графов и виды графов - №1 - открытая онлайн библиотека  = {u3, u4, u7, u9, u10, u11}; Способы задания графов и виды графов - №2 - открытая онлайн библиотека  = {u1, u2, u8, u12, u13}; Способы задания графов и виды графов - №3 - открытая онлайн библиотека  = {u5, u6}.

Способы задания графов и виды графов - №22 - открытая онлайн библиотека

Рис. 15.1. Смешанный граф G

Граф G = (X, U), у которого U = Способы задания графов и виды графов - №2 - открытая онлайн библиотека , а Способы задания графов и виды графов - №1 - открытая онлайн библиотека  = Æ, называется ориентированным, или орграфом. Орграф будем обозначать D = (X, U) или G = {X, Способы задания графов и виды графов - №2 - открытая онлайн библиотека }.

Заметим, что подмножество петель можно рассматривать как ориентированные, так и неориентированные ребра. Обычно всегда оговаривают, когда рассматривается граф с петлями. Граф G, у которого U = Способы задания графов и виды графов - №1 - открытая онлайн библиотека , называется неориентированным графом, или неорграфом. Графы, не содержащие петель и кратных ребер, называются простыми.

Рассмотрим сначала неорграфы с петлями и без петель, которые будем называть графами. Граф G, у которого существует хотя бы одна пара вершин, соединяемых m ребрами ui Î U, называется мультиграфом, а максимальное m ─ мультичислом графа G (m Î {2, 3, …}). Ребра, соединяющие одну и ту же пару вершин, называются кратными. На рис. 15.2 показан пример мультиграфа (m = 4).

Способы задания графов и виды графов - №27 - открытая онлайн библиотека

Рис. 15.2. Мультиграф G

Если ребро uk Î U графа G = (X, U) соединяет вершины xi, xj Î X, т.е.           uk = (xi, xj), то говорят, что ребро ukинцидентно вершинам xi, xj. Верно и обратное, вершины xi, xj инцидентны ребру uk. Любые две вершины xi, xj Î X графа G называются смежными, если существует соединяющее эти вершины ребро uk Î U, т.е. uk = (xi, xj). Если два ребра uk, ui Î U инцидентны одной и той же вершине, то они также называются смежными.

Основными способами задания графа G = (X, U) являются геометрический, аналитический и матричный. Основой геометрического способа задания графа является рисунок, дающий изображение графа. Изображение графа в виде рисунка обладает наглядностью, раскрывает содержательный смысл представляемого объекта, но не формально.

Рассмотрим аналитический способ задания графа. Согласно Н. Бурбаки, граф записывается как G Ì B = X × X. К. Берж предлагает задавать граф как соответствие Г между подмножествами множества вершин. При этом граф можно задать в виде G = (X, Г), где Г Í X ´ X, Г = {Гx1, Гx2, …, Гxn}. Здесь Г ─ это отображение множества Х в множество Х. Например, пусть задан граф G = (X, Г) (рис. 15.3). Тогда |X| = 6, X = {x1, x2, …, x6}, Г = {Гx1, Гx2, …, Гx6}, Гx1 = {x2, x5, x6}, Гx2 = {x1, x3, x5, x6}, Гx3 = {x2, x4}, Гx4 = {x5, x6}, Гx5 = {x1, x2, x4}, Гx6 = {x1, x2, x4}.

Учитывая вышесказанное, граф часто рассматривают как пару G = (X, Г), образованную множеством X и отображением Г множества X в себя.

Отметим, что для однозначного задания графов достаточно использовать Гx1, Гx2, …, Гxn-1 отображений. В этом случае элементы xi, определяющие Гxi, не включают в отображение Гxi+1; в отображение Гxi+2 не включают элементы xi, xi+1 и т.д. Соответственно в последнее отображение Гxn-1 не включают элементы x1, x2, …, xn-2. Тогда рассматриваемый граф G (рис. 15.3), может быть задан следующим образом: Гx1 = {x2, x5, x6}, Гx2 = {x3, x5, x6}, Гx3 = {x4}, Гx4 = {x5, x6}, Гx5 = Æ.

Способы задания графов и виды графов - №28 - открытая онлайн библиотека

Рис. 15.3. Граф G

Такое представление графа позволяет экономить память ЭВМ и исключать избыточную информацию при представлении графа аналитическим способом.

Большинство задач информатики удобно решать при использовании матричного задания графов. Квадратная таблица R = ||ri,j||nxn называется матрицей смежности, если ее элементы образуются по правилу:

Способы задания графов и виды графов - №29 - открытая онлайн библиотека

Заметим, что для мультиграфа

Способы задания графов и виды графов - №30 - открытая онлайн библиотека

Очевидно, что для рассматриваемых неорграфов ri , j = rj , i и для задания графа можно использовать треугольную матрицу R. Для графа без петель ri , i = 0, для графа с петлями ri , i ¹ 0. Для графа G (см. рис. 15.3) треугольная матрица смежности имеет вид

  x1 x2 x3 x4 x5 x6
x1 0 1 0 0 1 1

.

x2   0 1 0 1 1
R = x3     0 1 0 0
x4       0 1 1
x5         0 0
x6           0

Строки и столбцы матрицы R соответствуют вершинам графа G. На пересечении xi строки и xj столбца ставится элемент ri , j, соответствующий числу ребер, соединяющих вершины xi и xj. Заметим, что строки и столбцы матрицы R также можно нумеровать числами натурального ряда, соответствующими индексам помеченных вершин графа. Петли в графе изображаются элементами ri , j, расположенными по главной диагонали матрицы R.

Преимущество использования матриц смежности – это простота и формальность преобразований над графами.

Основной недостаток применения матрицы смежности заключается в том, что она занимает в ЭВМ память объемом |X|2 даже тогда, когда граф содержит только |X| ребер. Устранением этого недостатка является представление графа в виде списков. Списком смежности для вершины xi является совокупность всех вершин, смежных с xi. Представление графа в виде списков смежности требует памяти ЭВМ порядка |X| + |U|. В основном таким представлением графа пользуются, когда |U| << |X|2. Для графа G (см. рис. 15.3) список смежности имеет следующий вид:

x1 x2 x5 x6 0  
x2 x1 x3 x5 x6

,

RL = x3 x2 x4 0 0
x4 x3 x5 x6 0
x5 x1 x2 x4 0
x6 x1 x2 x4 0

а для треугольной матрицы

x1 x2 x5 x6 1 2 5 6  
x2 x3 x5 x6 2 3 5 6

.

RL= x3 x4 0 0 или RL=3 4 0 0
x4 x5 x6 0 4 5 6 0
x5 0 0 0 5 0 0 0
x6 0 0 0 6 0 0 0

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

Прямоугольная таблица вида I = ||ik , l||n´m называется матрицей инцидентности, если ее элементы образуются по правилу:

Способы задания графов и виды графов - №31 - открытая онлайн библиотека

Матрица инцидентности для G (см. рис. 1.3) имеет вид

  u1 u2 u3 u4 u5 u6 u7 u8 u9  
x1 1 1 0 0 0 0 1 0 0

.

x2 1 0 1 1 0 0 0 1 0
I = x3 0 0 0 1 1 0 0 0 0
x4 0 0 0 0 1 1 0 0 1
x5 0 1 1 0 0 1 0 0 0
x6 0 0 0 0 0 0 1 1 1

Строки матрицы I соответствуют вершинам графа, столбцы – ребрам, а элемент ik , l указывает на инцидентность вершины xk и ребра ul. В каждом столбце матрицы I расположено по две единицы, так как каждое ребро соединяет ровно две вершины. При наличии в графе петель соответствующие им столбцы в матрице I будут иметь по одной единице, так как петля соединяет только одну вершину графа.

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

Известно, что число ячеек в матрице (сотах) размером m × n равно 2mn. Соты порядка n содержат n2 ячеек. Тогда число ячеек матрицы с k запретными элементами (соответствующие элементы булевой матрицы – нули) равно

Способы задания графов и виды графов - №32 - открытая онлайн библиотека .

Предполагается, что выполняются следующие условия:

· соты (матрица) имеют порядок n;

· в каждой ячейке матрицы располагается не более одного объекта (т.е. ноль или единица).

В этом случае ячейки матрицы разбиваются на два подмножества:

· ячейки, обладающие неким свойством;

· ячейки, не обладающие этим свойством.

Тогда, согласно А. Кофману, говорят, что граф (рис. 15.4)

Способы задания графов и виды графов - №33 - открытая онлайн библиотека

Рис. 15.4. Граф G

может быть реализован в виде матрицы:

Способы задания графов и виды графов - №34 - открытая онлайн библиотека ,

где закрашенным элементам матрицы соответствуют ребра графа G.

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

Кёниг и К. Берж под графом понимают разбиение теоретико-множественного произведения некоторого счетного множества на себя, на две части.

Графы иногда представляют в латинской матрице. Для графа G (рис. 15.4) такое представление имеет вид

Способы задания графов и виды графов - №35 - открытая онлайн библиотека .

Латинская матрица удобна для задания как ориентированных, так и неориентированных графов (неорграфов). Причем, в неорграфах значение элемента матрицы i, j = j, i ( в ориентированных графах наоборот, i, j ¹ j, i).

Виды графов

Определим смежностный (двойственный) граф GS = (U, V), (обозначают также U(G)) для графа G = (X, U). Вершинами GS являются ребра G, а ребрами GS - пары (ui, uj). Для построения GS по G на каждом ребре ui Î U графа G выбирают среднюю точку и считают ее вершиной ui Î U графа GS (см. рис. 1.5). Таким образом, двойственный граф GS будет иметь 12 вершин: U = {u1, u2, …, u12}

Затем пару (ui, uj) соединяют ребром vk = (ui, uj), если ребра ui, uj имеют общую вершину в G. То есть для графа GS вершина u1, например, будет иметь общие ребра с вершинами u2, u4, u5, u6, так как эти ребра в исходном графе G имели общие вершины (x1 и x2). В результате получим следующий двойственный граф GS (рис. 15.6)

Способы задания графов и виды графов - №36 - открытая онлайн библиотека

Рис. 15.5. Построение двойственного графа GS

Способы задания графов и виды графов - №37 - открытая онлайн библиотека

Рис. 15.6. Двойственный граф GS

Следует отметить, что существуют различного рода матрицы и списки, производные от R и I, которые используются при записи алгоритмов.

Граф G называется конечным, если множества его вершин и ребер ─ конечные множества. Далее будем рассматривать конечные графы, так как модели объектов, представляемые графами, состоят из конечного числа элементов.

Граф G, у которого X ¹ Æ, а U = Æ, называется нуль-графом, а его вершины ─ изолированными. Обозначается он G0. Граф G = (X, U), |X| = n называется полным, если между любой парой вершин xi, xj Î X имеется ребро uk Î U. Обозначается он Kn. Число ребер, инцидентных вершине xi Î X графа G, называется локальной степенью или просто степенью этой вершины и обозначается r(xi) или r i. Тогда число ребер графа G = (X, U), |X| = n, |U| = m,

                                            Способы задания графов и виды графов - №38 - открытая онлайн библиотека .                                           (15.1)

Заметим, что если в графе имеются петли, то каждая из них должна считаться дважды. Так как для полного графа на n вершин r(x1) = r(x2) = … = r(xn), то

                                            m = n(n - 1) / 2.                                           (15.2)

Графы с одинаковыми числами степеней называются регулярными. Регулярные графы степени 3 называются кубическими (трехвалентными). Примером кубического графа является граф Петерсона (рис. 15.7).

Способы задания графов и виды графов - №39 - открытая онлайн библиотека

Рис 15.7. Граф Петерсона

Среди регулярных графов интерес представляют так называемые платоновы графы – графы, образованные вершинами и ребрами пяти правильных многогранников – платоновых тел:

· тетраэдра (рис. 15.8, а),

· куба (рис. 15.8, б),

· октаэдра (рис. 15.9, а),

· додекаэдра (рис. 15.9, б),

· икосаэдра (рис 15.9, в).

Способы задания графов и виды графов - №40 - открытая онлайн библиотека                         Способы задания графов и виды графов - №41 - открытая онлайн библиотека

                         а                                                       б

Рис. 15.8. Тетраэдр (а), куб (б)

Способы задания графов и виды графов - №42 - открытая онлайн библиотека             Способы задания графов и виды графов - №43 - открытая онлайн библиотека

                                 а                                                  б

Рис. 15.9. Октаэдр(а),  додекаэдр (б),

Способы задания графов и виды графов - №44 - открытая онлайн библиотека

в

Рис. 15.9. (окончание) икосаэдр (в)

Число ребер регулярного графа с локальной степенью r(xi) вершины xi определяется как

                                       m = n r(xi)/2.                            (15.3)

Заметим, что в графе каждое ребро соединяет две вершины и, следовательно, число вершин нечетной степени четно.

Полный граф K1,n называется звездным. Он показан на рис 15.10.

Способы задания графов и виды графов - №45 - открытая онлайн библиотека

Рис. 15.10. Пример звездного графа

Над графами можно выполнять следующие операции: объединение (È), сложение (+) и произведение (*).

1. Объединением графов G(a) = (X(a), U(a)) и G(b) = (X(b), U(b)) называется граф G = (X, U), у которого X = (X(a) È X(b)), U = (U(a) È U(b)) (рис. 15.11).

Способы задания графов и виды графов - №46 - открытая онлайн библиотека

Рис. 15.11. Операция объединения графов

2. Суммой графов G(a) = (X(a), U(a)) и G(b) = (X(b), U(b)) называется граф G = (X, U) который определяется объединением G(a) и G(b), и каждая вершина xi Î X(a), не вошедшая в пересечение X(a) Ç X(b), соединяется со всеми вершинами X(b) \ X(a) Ç X(b) и наоборот (рис. 15.12).

Способы задания графов и виды графов - №47 - открытая онлайн библиотека

Рис. 15.12. Сумма графов

3. Произведением графов G(a) = (X(a), U(a)) и G(b) = (X(b), U(b)) называется граф G = (X, U) у которого X = X(a) × X(b), а ребра соответствуют связности подграфов (рис. 1.13).

Способы задания графов и виды графов - №48 - открытая онлайн библиотека

Рис. 15.13. Произведение графов

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G, т.е. G’ = (X’, U’), подграф G = (X, U), если X’ Í X, U’ Í U и ребра U’ соединяют только вершины X’. Удаление из графа G = (X, U) вершины xi со всеми инцидентными ей ребрами приводит к подграфу G’’ = (X’’, U’’), X’’ = X \ xi. На рис. 15.14, а, b, c показаны граф G = (X, U) и два его подграфа, G1 = (X1, U1) и G2 = (X2, U2), где |X| = 7, |U| = 10, X = {x1, x2, …, x7}, U = {u1, u2, …, u10}; |X1| = 3, |U1| = 3, X1 = {x1, x2, x4}, U1 = {u1, u7, u6}; |X2| = 5, |U2| = 6, X2 = {x2, x3, x5, x6, x7}, U2 = {u2, u3, u4, u8, u9, u10}. Заметим, что подграф G1 можно получить, удалив из G вершины x3, x5, x6, x7 с инцидентными им ребрами, а подграф G2, удалив из G вершины x1, x4 с инцидентными им ребрами.

Способы задания графов и виды графов - №49 - открытая онлайн библиотека

a

Способы задания графов и виды графов - №50 - открытая онлайн библиотека G1      Способы задания графов и виды графов - №51 - открытая онлайн библиотека G2

б                                        в

Способы задания графов и виды графов - №52 - открытая онлайн библиотека           Способы задания графов и виды графов - №53 - открытая онлайн библиотека

          г                                                д

Рис.15.14. Граф G (а) и его подграфы G 1(б) и G 2(в); суграф графа G (г); дополнение графа G (д)

Суграфом G’ = (X’, U’) графа G = (X, U) называется граф, для которого X’ = X, U’ Í U.

Граф Способы задания графов и виды графов - №54 - открытая онлайн библиотека  называется дополнением графа G до полного, если он состоит из всех ребер полного графа K, не принадлежащих G, Способы задания графов и виды графов - №54 - открытая онлайн библиотека  = K \ G. На рис. 15.14, г) показан суграф графа (см. рис. 15.14, в). На рис. 15.14, д) приведено дополнение графа G (см. рис. 15.14, в) до полного графа K7.