13. Матрица смежности вершин…. Матричные способы задания графов

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

Матрица смежности A = (a_ij) определяется одинаково для ориентиро­ванного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой

a_ij =

Пример 1.

Рис. 1.

Матрица смежности графа, изображенного на рис. 1, имеет вид:

A =

Матрица смежности полностью задает граф.

Матрицей инцидентности B = (b_ij) ориентированного графа называет­ся прямоугольная матрица (n ´ m), где n – число вершин, m – число ребер, у которой

b_i =

Для неориентированного графа матрица инцидентности B задается следующим образом:

b_i =

Пример 2.

Матрица инцидентности графа, изображенного на рис. 1, имеет вид:

B =

Матрица инцидентности, также, как и матрица смежности, полностью задает граф.

Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.

Основные свойства матриц смежности и инцидентности

1. Матрица смежности неориентированного графа является симметрич­ной. Для ориентированного графа это, вообще говоря, неверно.

2. Сумма элементов i - ой строки матрицы смежности неориентиро­ванного графа равна степени вершины x_i.

3. Сумма строк матрицы инцидентности ориентированного графа явля­ется нулевой строкой.

Итак, возможны следующие различные способы задания графа:

а) посредством графического изображения;

б) указанием множества вершин и множества ребер (дуг);

в) матрицей смежности;

г) матрицей инцидентности.

14. Связность, планарность графов. Формула Эйлера.

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

Ориентированный граф называется сильно связным, если для любых двух его вершин x_i и x_j существует хотя бы один путь, соединяющий x_i с x_j.

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

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

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

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

Пусть G = (X, A) неориентирован­ный граф с множеством вершин X = {x₁,...,x_n}. Квадратная матрица S = (s_ij) порядка n, у которой

s_ij =

называется матрицей связности графа G.

Для ориентированного графа квадратная матрица T = (t_ij) порядка n, у кото­рой

t_ij =

называется матрицей односторонней связности (достижимости).

Квадратная матрица S = (s_ij) порядка n, у которой

s_ij =

называется матрицей сильной связности.

Планарный граф. Формула Эйлера.

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

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

Т еорема: графы K и K не планарны. Доказательство: предположим сначала, что граф K планарен. Поскольку он содержит цикл длины пять, то изобразим этот цикл правильным пятиугольником: v – w – x – y - z - v. Для оставшихся вне этого цикла пяти рёбер два ребра (например, z – w и z - x) можно уложить внутри пятиугольника. Чтобы рёбра v – x и v – y не пересекались с уложенными внутри пятиугольника двумя рёбрами, их надо уложить снаружи пятиугольника:

Оставшееся ребро w – y нельзя уложить ни снаружи, ни внутри пятиугольника так, чтобы оно не пересекалось с уже уложенными четырьмя рёбрами. Получили противоречие.

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

Получили противоречие. Теорема доказана.

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

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

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

Операция подразбиения дуг и понятие гомеоморфизма существуют и для орграфов.

Теорема Куратовского: граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K или K . Без доказательства.

П

f3

f2

f1

лоский граф разбивает плоскость, на которой он изображён, на грани, окружённые рёбрами графа. Одна грань у графа всегда не ограничена, она называется бесконечной. Вот плоский граф с тремя гранями: f1, f2 и f3, и грань f3 – бесконечная:

З

f3

f2

f3

f2

f1

десь грань f1 имеет (ограничена) семь рёбер, грань f2 – четыре, а грань f3 – пять. Число граней в планарном графе обозначается буквой f. В качестве бесконечной грани можно взять любую грань, достаточно по- другому перерисовать граф. Например, тот же граф с тремя гранями, но слева бесконечной сделана грань f1, а справа – грань f2:

f1

Теорема Эйлера: для связного плоского графа n+f=m+2, где f, n и m – число соответственно граней, вершин и рёбер у графа. Доказательство индукцией по числу рёбер m в графе. Если m = 0, то n = 1 (граф связен) и f = 1, т.е. n + f = m + 2 для m = 0. Сделан первый шаг индукции.

Д елаем индуктивное предположение, что теорема верна для каждого графа, имеющего (m – 1) рёбер, и добавим к графу новое ребро. Тогда оно либо петля, либо соединяет две вершины из графа, либо соединяет вершину графа и новую вершину:

Пусть в графе с (m – 1) рёбрами имеется n вершин и f граней и по индуктивному преположению n + f = m – 1 + 2. Петля и ребро, соединяющее две вершины, добавили ребро и грань: n + f + 1 = m – 1 + 2 + 1, а новая висячая вершина добавила вершину и ребро: n + 1 + f = m + 1– 1 + 2. Во всех трёх случаях единица добавлялась и к левой и к правой части равенства n + f = m – 1 + 2 и оно оставалось верно. Теорема доказана.

Для не связных плоских графов теорема Эйлера имеет вид: n+f=m+p+1, где p – число компонент связности. Это следствие теоремы Эйлера. Результат получается применением теоремы Эйлера к каждой компоненте связности по отдельности. При этом бесконечная грань считается только один раз.

У дерева и у леса, например, f = 1 (одна бесконечная грань). Следствие теоремы Эйлера: для связного планарного графа с n >= 3 вершинами m <= 3 n - 6. Превращаем планарный граф в плоский. Так как каждая грань ограничена по крайней мере тремя рёбрами (минимальная длина цикла в графе равна трём), то при подсчёте числа рёбер вокруг каждой из граней получим, что 3 f <= 2 m (множитель 2 появляется оттого, что ребро ограничивает не больше двух граней).

По теореме Эйлера n + f = m + 2, отсюда 3 f = (m + 2 – n ) 3 и, подставив 3 f в неравенство, получим (m + 2 – n ) 3 <= 2 m. Окончательно:

m <= 3 n – 6 .