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

25.08.2014 19:01 Александр
Печать

Прежде чем определить понятие конечного графа в наиболее общей форме, представим себе на плоскости (или в вещественном аффинном пространстве произвольной размерности k) не­которое конечное множество V точек и конечный набор Х линий, соединяющих некоторые пары точек из V. Указанной геометри­ческой конфигурацией описывается, например, схема автомо­бильных дорог, связывающих города некоторой области (рисунок 3).


Рисунок 3 – Пример схемы автодорог

 

Для многих задач оказывается несущественным, соединены ли точки конфигурации отрезками прямых или криволинейными дугами (например, при решении задачи о нахождении маршру­та движения по дорогам, связывающего два заданных города и проходящего через минимальное число дорог). Важно лишь то, что каждая линия соединяет какие-либо две из заданного набора точек. При рассмотрении подобных задач достаточно ограничиться исследованием совокупности двух конечных множеств V, X, где V- непустое множество, X- некоторый набор пар элементов из V вида (v, w). Введенная пара множеств (V, X) допускает также многочисленные другие интерпретации и является предметом детального изучения в математике. Эле­менты множества V будем называть вершинами, а элементы набора X- ребрами. В общем случае в наборе Х могут встре­чаться пары с одинаковыми элементами вида (v, v), а также одинаковые пары. Ребра вида (v, v) назы­ваются петлями. Одинаковые пары в Х назы­ваются кратными (или параллельными) ребрами. Количество одинаковых пар (v, w) в Х называется кратностью ребра (v, w). Про множество V и набор Х будем говорить, что они определяют граф с кратными ребрами   и   петлями (или   псевдограф) G=(V, X).

Псевдограф без петель называется графом с кратными ребрами (или мультиграфом), если в наборе Х ни одна пара не встречается более одного раза то мультиграф G = (V, X) называется графом. Если пары в наборе Х являются упорядоченными, то граф называется ориентированным (кратко-орграфом). Ребра орграфа называются дугами. Если пары в наборе Х являются неупорядоченными, то граф называется неориентированным графом (или просто графом). Ребра в неориентированном графе (в отличие от дуг в орграфе) будем обозначать {v, w}. Неориентированные графы будем обозначать буквой G или G с индексами (например, G0, G1,...), а орграфы-буквой D или D с индексами (например, D0, D1,...). Кроме того, договоримся обозначать вершины буквами v, u, w (без индексов или с индексами), а ребра и дуги-буквами x, у, z (без индексов или с индексами).

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

 

Пример 1. Пусть V={v1, v2, v3, v4}, X={x1=(v1, v2), x2=(v1, v2), x3=(v2, v2), x4=(v2, v3)}. Тогда D=(V, X) – ориентированный псевдограф, изображение которого приведено на рисунке 4.

Рисунок 4 - Ориентированный псевдограф

 

Пример 2. Пусть V={ v1, v2, v3, v4, v5}, X={ x1={v1, v2}, x2={v2, v3}, x3={v2, v4}, x4={v3, v4}}. Тогда G=(V, X) - неориентированный граф (или просто граф), изображение которого дано на рисунке 5.

Рисунок 5 - Неориентированный граф

Приведем ряд понятий и определений для ориентированных и неориентированных графов. Там, где это не оговорено особо, те же понятия и определения переносятся без изменений на ориентированные и неориентированные псевдографы.

Смежность, инцидентность, степени

Если x={v, w}-ребро графа, то вершины v, w называются концами ребра х; в этом случае также говорят, что ребро соединяет вершины v, w.

Если х=(v, w)-дуга орграфа, то вершина v называется началом, а вершина w-концом дуги х; в этом случае также говорят, что дуга х исходит из вершины v и заходит в вершину w.

Если вершина v является концом (началом или концом) ребра (дуги) х, то говорят, что v и х инцидентны.

Вершины v, w графа G=(V, X) называются смежными, если {v, w} X. Два ребра называются смежными, если они име­ют общую вершину.

Степенью вершины v графа G называется число (v) ребер графа G, инцидентных вершине v. Вершина графа, имеющая степень 0, называется изолированной, а степень 1 - висячей.

Замечание 1. В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине v, в (v) равен 2 (тогда как вклад любого дру­гого ребра, инцидентного вершине v, равен 1).

Полу степенью исхода (захода) вершины v орграфа D называется число (v) ( (v)) дуг орграфа D, исходящих из вер­шины v (заходящих в вершину v).

Замечание 2. В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в (v), так и в (v).

Пример 3.

1. В графе G (см. пример 2) концами ребра х1 являются вершины v1, v2; вершина v2 инцидентна ребрам х1, х2, х3; степень вершины v2 равна 3, т. е. (v2)=3; вершины v1, v2 смежные, ребра х1, х2 смежные; вершина v1 висячая; вершина v5 изолированная.

2. В ориентированном псевдографе (см. пример 1) дуга х1 исходит из вершины v1 и заходит в вершину v2 вершина v2 инцидентна дугам х1, х2, х3, х4; (v)=2, (v)=3.

Количество вершин и ребер в графе G обозначим соответст­венно через n(G) и m(G), а количество вершин и дуг в орграфе D - через n(D) и m(D).

Утверждение 1. Для любого псевдографа G выполняется равенство .

Это равенство является очевидным следствием того, что вклад каждого ребра в сумму из его левой части равен 2.

Приведем также соответствующее утверждение для орграфа.

Утверждение 2. Для любого ориентированного псевдографа D выполняется равенство . Его доказательство очевидно.

Маршруты, пути

Введем понятие маршрута для графа G=(V, X) (и соответст­венно понятие пути для орграфа D = (V, X)). Последователь­ность v1х1v2х2v3... хkvk+1, где k 1, vi V, (i=1,..., k+1, xj X, j=1,..., k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,..., k ребро (дуга) xj имеет вид {vj, vj+1} ((vj, vj+1)), называется маршрутом, соединяющим вершины v1, vk+1 (путем из v1 в vk+1). При этом v1 называется начальной, vk+1конечной вершинами маршрута (пути), а остальные вершины – внутренними. Одна и та же вершина может одновременно оказаться началь­ной, конечной и внутренней. Последовательность вершин в мар­шруте определяет на ребрах, входящих в маршрут, ориентацию. Заметим в этой связи, что ориентацию некоторого ребра х={v,w} всегда можно указать при записи его как пары вер­шин. Например, запись {v, w} указывает на то, что ребро х ориентировано от вершины v к вершине w.

Пример 4.

1. Последовательность v1x2v2x3v4x4v3-маршрут, соединяю­щий вершины v1, v3 в графе G (см. пример 2).

2. Последовательность v1x2v2x3v2x4v3-путь из v1 в v3 в ориентированном псевдографе D (см. пример 1).

Замечание 3. Последовательность v1х1v2х2v3... хkvk+1 можно однозначно восстановить по последовательности х1...хk, а следовательно, вместо нее можно использовать более короткую запись х1...хk. Отметим далее, что в случае, когда в последовательности v1х1v2х2v3... хkvk+1 х1,…,хk имеют кратности, равные 1, ее можно однозначно восстановить по по­следовательности вершин v1...vk+1, а следовательно, вместо нее также можно использовать более короткую запись v1...vk+1. В общем случае вместо последователь­ности v1х1v2х2v3... хkvk+1 можно использовать сокращенную последователь­ность, в которой опущены все xi кратности 1.

Пример 5.

1. Последовательности х1х3х4, v1v2v4v3-сокращенные записи маршрута, приведенного в примере 4, п. 1.

2. Последовательности х2х3х4, v1x2v2v2v3-сокращенные записи пути, приведенного в примере 4, п. 2.

Пусть х1х2…хk-маршрут в графе G (см. замечание 3) и для некоторой последовательности номеров i1,...,ir, где r 1, 1 i1<i2<...<ir k, xi1,xi2...xir снова является маршрутом в графе G. Тогда xi1,xi2...xir называется подмаршрутом маршрут та x1x2...xk. При этом будем говорить, что маршрут xi1,xi2...xir выделен из маршрута x1x2...xk. Аналогично определяется подпуть, выделенный из пути орграфа. Число ребер (дуг) в маршруте (пути) называется длина маршрута (пути).

Маршрут (путь) v1х1v2х2v3... хkvk+1 называется замкнутым, если его начальная вершина совпадает с конечной, т. е. если v1=vk+1.

Замечание 4. Далее всюду при подсчете числа вхождение вершин в замкнутый маршрут (путь) начальную и конечную вершины будем считать за одно вхождение этой вершины маршрут (путь).

Замечание 5. При замкнутом маршруте (пути) x1x2...xk обычно считается, что последовательности x1x2...xk, x2x3...xkx1,..., xkx1x2...xk-1-различные записи одного и того же маршрута (пути).  Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется цепью. Цепь, в которой все вер­шины попарно различны, называется простой цепью.

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

Пример 6. Рассмотрим граф G из примера 2. Тогда:

1) v1x1v2x3v4x4v3-маршрут длины 3, соединяющий v1, v3; это простая цепь, так как все ребра и вершины попарно различны;

2) v2x2v3x4v4x3v2-замкнутый маршрут длины 3; это простой цикл, так как все ребра и вершины попарно различны;

3) v1x1v2x2v3x4v4x3v2-маршрут длины 4, соединяющий вершины v1, v2; это цепь, которая не является простой, так как вершина v2 встречается дважды;

4) v1x1v2x2v3x2v2-маршрут длины 3, соединяющий вершины v1, v2 и не являющийся цепью, так как ребро x2={v2, v3} встре­чается дважды.

Пример 7. Рассмотрим ориентированный псевдограф D из примера 1. Тогда:

1) v1x1v2x4v3-путь длины 2 из v1 в v3; это простая цепь так, как все дуги и вершины попарно различны;

2) v2x3v2-простой контур длины 1;

3) v1x2v2x3v2x4v3-цепь из v1 в v3 длины 3, которая не яв­ляется простой.

Нетрудно показать, что в псевдографах, мультиграфах и графах минимальная длина простого цикла равна соответствен­но 1, 2 и 3 (каковы минимальные длины простых контуров в ориентированных псевдографах, мультиграфах и графах?).

Утверждение 3. В псевдографе G (в ориентированном псев­дографе D) из всякого цикла (замкнутого пути) можно выде­лить простой цикл (простой контур).

Доказательство будем проводить для G (для D доказатель­ство аналогично) индукцией по k-количеству ребер в цикле. При k=1 всякий цикл является простым. Пусть при некотором k 2 доказываемое утверждение справедливо для любого цикла длины k-1. Покажем его справедливость для произвольного цикла =v1x1...vkxkv1 длины k. Рассмотрим любые два номера i, j, где 1 i<j k, такие, что vi=vj. Если таких номеров нет, то цикл является простым (по определению). Если же ука­занные номера нашлись, то рассматриваем цикл vixi...vj-ixj-ivj длины j-i k-1, а из него в силу индуктивного предположе­ния можно выделить простой цикл.

Утверждение 4. Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конеч­ной вершинами.

Доказательство будем проводить для маршрута (для пути доказательство аналогично) индукцией по k-количеству ре­бер в маршруте. При k=1 всякий маршрут является простой цепью. Пусть при некотором k 2 доказываемое утверждение справедливо для любого маршрута длины k-1. Покажем его справедливость для произвольного маршрута =vixiv2...xkvk+i, где v1 vk+1, длины k. Рассмотрим два номера i, j, где 1 i<j k+1 такие, что vi=vj. Если таких номеров нет, то марш­рут n является простой цепью. Если же указанные номера на­шлись, то рассматриваем подмаршрут =v1x1v2...xi-lvixjvj+1...xkvk+1 (т. е. предполагаем, что i 1, j k+1; случаи, когда i=l или j=k+1, рассмотрите самостоятельно) длины k-1, а из него в силу индуктивного предположения можно выделить простую цепь, соединяющую вершины v1, vk+1.

Введем понятие композиции путей  (маршрутов). Пусть 1=v1x1v2...xk-1vk, 2=vkxkvk+1...xl-1vl-пути в орграфе D, где k 2, l k+1.

Назовем путь 1 2= v1x1v2...xk-1vkxkvk+1...xl-1vl (очевидно, что 1 2 - путь в D) композицией путей 1, 2. Ана­логично определяется композиция маршрутов.


Матричное задание графов. Матрицы смежности, инцидентности

Пусть D=(V, X) -орграф, где V={v1,..., vn}, X={x1,...,xm}.

 

Матрицей смежности орграфа D называется квадратная матрица A(D) = [аij] порядка n, у которой

Матрицей инцидентности (или матрицей инциденций) оргра­фа D называется (n m) -матрица B(D) =[bij], у которой

Введем также матрицы смежности и инцидентности для не­ориентированных графов. Пусть G=(V, X)–граф, где V={v1,..., vn}, X={x1,...,xm}.

 

Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Матрицей инцидентности графа G называется (n m) – матри­ца B(G)=[bij], у которой

Пример 8. Для орграфа D, изображенного на рисунке 6, матрица А(D) приводится в таблице 4а, а матрица B(D) – в таблице 4б.

Рисунок 6 - Орграф D

 

Пример 9. Для графа G, изображенного на рисунке 7, матри­ца A(G) приводится в табл. 5а, а матрица B(G) – в табл. 5б.

Рисунок 7 - Граф G

Замечание 6. Матрицу смежности можно определить и для псевдографов. Тогда в случае ориентированного (неориентированного) псевдографа аij=k, где k-кратность дуги (vi, vj) (ребра {vi, vj}) в этом псевдографе. Определение матрицы инцидентности без изменений переносится и на произвольные мультиграфы (ориентированные и неориентированные) и даже на неориентированные псевдографы.

 

Пример 10. Для ориентированного псевдографа D, изображенного на рисунке 8, матрица A(D) приводится в таблице 6.

Рисунок 8 - Псевдограф D

Нетрудно видеть, что матрица A(G) является симметричной для любого неориентированного графа G. Матрица A(D), где D-орграф, в общем случае не является симметричной (см. примеры 8 и 10).

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

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

Приведем очевидные свойства матриц смежности и инцидентности:

1. Сумма элементов матрицы A(G), где G=(V, X)-мультиграф, V={v1,...,vn}, по i-й строке (или по i-му столбцу равна (vi).

2. Суммы элементов матрицы A(D), где D=(V,X)-opиентированный псевдограф, V={v1,...,vn}, по i-й строке и по i-му столбцу соответственно равны (vi), (vi).

3. Пусть D-ориентированный мультиграф с непустым множеством дуг. Тогда

а) сумма строк матрицы В(D) является нулевой строкой;

б) любая строка матрицы B(D) является линейной комбинацией остальных строк;

в) ранг матрицы B(D) не превосходит n(D)-1;

г) для любого контура в D сумма столбцов матрицы B(D) соответствующих дугам, входящим в этот контур, равна нулевому столбцу.

4. Пусть G-мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:

a) сумма строк матрицы В(G) является нулевой строкой;

б) любая строка матрицы B(G) является суммой остальных строк;

в) для любого цикла в G сумма столбцов матрицы В(G) соответствующих ребрам, входящим в этот цикл, равна нулевому  столбцу.

Обозначим через А(k)=[a(k)ij] k-ю степень матрицы смежности A=A(D) орграфа D (аналогичное обозначение вводим для графа G).

Утверждение 5. Элемент а(k)ij матрицы А(k) ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)), где V={v1,...,vn}, равен числу всех путей (маршрутов) длины из vi в vj (соединяющих vi, vj).

Доказательство проведем для D (для G оно аналогично) индукцией по k. При k=1 справедливость доказываемого утверждения следует непосре| ственно из определения матрицы А=А(D). Предположим, что доказывает утверждение справедливо при k. Покажем его справедливость и при k=k+1. Обозначим через П(D, vi, vj, r), где r 1, множество путей длины r из vi в vj в ориентированном псевдографе D. Разобъем множество путей П(D, vi, vj, k+1) на п групп. Первая группа - это множество П(D, vi, v1, vj, k+1) путей с предпоследней вершиной v1, вторая группа - множество П(D, vi, v2, vj, k+1) путей с предпоследней вершиной v2 и т. д., n-я группа - множество П(D, vi, vn, vj, k+1) путей с предпоследней вершиной vn. Очевидно, что совокупность указанных групп является разбиением множества П(D, vi, vj, k+1). Заметим, что по правилу произведения

|П(D, vi, vl, vj, k+1)| = | П(D, vi, vl, k) || П(D, vl, vj, 1)| = | П(D, vi, vl, k)|aij, где l=1,2,…,n

Отсюда, используя то, что в силу индуктивного пред­положения выполняется равенство | П(D, vi, vl, k) |=a(k)il, получаем |П(D, vi, vl, vj, k+1)| = a(k+1)ij

Утверждение 5 имеет многочисленные следствия. приведем, например, утверждение, позволяющее по степеням матрицы смежности определять на­личие контуров в орграфе D.

Утверждение 6. Для того чтобы n-вершинный орграф D с матрицей смежности A=A(D) имел хотя бы один, контур, не­обходимо и достаточно, чтобы матрица K=A2+ A3+…+ An име­ла ненулевые диагональные элементы.

Достаточность. Пусть K=[kij] и для некоторого номера i выполняется kii>0. В этом случае для некоторого r={2,...,n} справедливо a(r)ii>0), а следовательно, в силу утверждения 5 найдется путь в D из vi в vi. Но тогда в силу утверждения 3 в орграфе D найдется простой контур.

Необходимость. Пусть в орграфе D имеется некоторый кон­тур. В утверждении 3 было показано, что из всякого контура можно выделить простой контур. Нетрудно видеть, что длина простого контура не превышает числа вершин п. Но тогда в силу утверждения 5 для любой вершины vi, принадлежащей некоторому простому контуру длины l, где 2 l n, элемент a(l)ii матрица Аl отличен от нуля, а следовательно, и элемент kii матрицы К отличен от нуля.

Замечание 5. В случае ориентированного n-вершинного псевдографа D для существования в D контура необходимо и достаточно, чтобы матрица K=A2+ A3+…+ An имела ненулевые диагональные элементы. Доказательство аналогично.

Связность. Компоненты связности

Говорят, что вершина w орграфа D (графа G) достижима из вершины v, если либо w=v, либо существует путь из v в w (мар­шрут, соединяющий v, w).

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

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

 

Псевдографом, ассоциированным с ориентированным псевдо­графом D=(V, X), называется псевдограф G=(V, Хо), в кото­ром Х0 получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w} (см. рисунок 9, где а - ориентирован­ный псевдограф, б - ассоциированный с ним псевдограф).

Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

Если граф (орграф) не является связным (слабо связным), то он на­зывается несвязным.

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

 

Пример 1. У графа, изображенного на рисунок 10, три ком­поненты связности.

Рисунок 10 - Граф

 

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

Рисунок 11 – Компоненты связности графа

Из определения компоненты связности (сильной связности) заключаем, что справедливо:

Утверждение 1.

1. Пусть G1=(V1, X1) – компонента связности графа G. Тог­да G1-подграф графа G, порожденный множеством V1.

2. Пусть D1=(V1, X1) – компонента сильной связности орграфа D. Тогда D1-подграф орграфа D, порожденный множе­ством V1.

Замечание 1. Утверждение 1 остается в силе и для про­извольных псевдографов (ориентированных и неориентирован­ных).

Нетрудно показать, что справедливы следующие утвержде­ния.

Утверждение 2. Пусть G=(V, X)-псевдограф с р ком­понентами связности: G1=(V1,X1),..., Gp=(Vp, Хр). Тогда

1) , , т.е.

2) , при

3) n(G1)+...+n(Gp)=n{G), m(G1)+...+m(Gp)=m(G).

Утверждение 3. Пусть D=(V, X) – ориентированный псевдограф с р компонентами сильной связности: D1=(V1, X1),..., Dp=(Vp, Xp). Тогда

1) ,

2) , при

3) n(G1)+...+n(Gp)=n{G), m(G1)+...+m(Gp) m(G).

Утверждение 4. Пусть – отношение достижимости на множестве V вершин псевдографа G, т. е. v w тогда и только тогда, когда либо v=w, либо существует маршрут, соединяю­щий v, w. Тогда:

1) - эквивалентность на V;

2) v w тогда и только тогда, когда вершины v, w принадле­жат одной компоненте связности псевдографа G;

3) для любого класса эквивалентности V1 V/ псевдограф G1, порожденный множеством V1 является компонентой связно­сти псевдографа G;

4) для любой компоненты связности G1=(V1, X1) псевдогра­фа G выполняется V1 V/ .

Утверждение 5. Пусть – отношение достижимости на множестве V вершин ориентированного псевдографа D, т. е. v w тогда и только тогда, когда вершина w достижима из v. Пусть также – отношение двусторонней достижимости на V, т. е. Тогда:

1) рефлексивно, транзитивное

2) эквивалентность на V;

3) v w тогда и только тогда, когда вершины v, w принадле­жат одной компоненте сильной связности ориентированного псевдографа D;

4) для любого класса эквивалентности V1 V/ ориентиро­ванный псевдограф D1, порожденный множеством V1, является компонентой сильной связности ориентированного псевдогра­фа D;

5) для любой компоненты сильной связности D1=(V1,X1) ориентированного псевдографа D выполняется V1 V / .

В дальнейшем количество компонент связности графа G бу­дем обозначать через p(G). Аналогично через p(D) будем обо­значать количество компонент сильной связности орграфа D.

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

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

Пример 3. Точками сочленения графа, изображенного на рисунке 12, являются вершины v3, v4, v6, v7.

Рисунок 12 – Точки сочленения графа

Следующее утверждение очевидно.

Утверждение 6. Если D/ – орграф, полученный в резуль­тате удаления нескольких вершин из орграфа D, то A(D/) полу­чается из A(D) в результате удаления строк и столбцов, соот­ветствующих удаленным вершинам.

Замечание 2. Аналогичное утверждение справедливо и для произвольных псевдографов (ориентированных и неориен­тированных).

Матрицы связности

Пусть D=(V, X) – орграф, где V={v1,.....,vn}. Матрицей дости­жимости орграфа D называется квадратная матрица Т(D)=[tij] порядка n, у которой tij=1, если вершина vj достижима из vi и tij=0 - в противном случае. Матрицей сильной связно­сти орграфа D называется квадратная матрица S(D)=[sij] порядка n, у которой sij=l, если вершина vj достижима из vj, и одновременно vj достижима из vi, и sij=0 – в противном слу­чае (т. е. sij=1 тогда и только тогда, когда вершины vj и vi принадлежат одной компоненте сильной связности орграфа D; см. утверждение 5, п. 3).

Пусть G=(V, X) – граф, где V={v1,.....,vn}. Матрицей связ­ности графа G называется квадратная матрица S(G)=[sij] порядка п, у которой sij=1, если i=j или существует маршрут, соединяющий vj и vi, и sij=0 – в противном случае (т. е. sij=1,тогда и только тогда, когда вершины vj и vi принадлежат одной компоненте связности графа G; см. утверждение 4, п.2).

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

Утверждение 7. Пусть G=(V, X), где V={v1,.....,vn} – граф с матрицей смежности А=А(G). Тогда , где Е - единичная матрица порядка n.

Утверждение 8. Пусть D=(V, X), где V={v1,.....,vn} – орграф с матрицей смежности А=А(D). Тогда

1) , где Е - единичная матрица порядка n;

2) , где * – обозначение операции транспонирования матрицы.

Утверждения 7 и 8 дают простые, легко реализуемые на ЭВМ методы вычисления матриц S(G), T(D), S(D). Сущест­вуют и более экономичные методы вычисления этих матриц, например, метод Уоршелла.

Выделение компонент связности

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

Воспользуемся следующими утверждениями.

Утверждение 9. Пусть D – орграф с р 2 компонентами сильной связности: D1,...,Dp. Тогда в результате удаления из D вершин, содержащихся в D1 получаем орграф с р-1 компонен­тами сильной связности: D2,...,Dp.

Воспользуемся тем очевидным фактом, что если D' – компо­нента сильной связности орграфа D, то D' является компонен­той сильной связности и любого подграфа орграфа D, содержа­щего все вершины и дуги орграфа D'. Используя утверждение 4.11, п. 2, заключаем, что после удаления из D вершин, содержащихся в D1, имеем орграф D, подграфами которого являются D2,...,Dp, а следовательно, D2,...,Dp являются компонентами сильной связности орграфа D. Кроме того, в силу утверждения 3, пп. 1, 2, получаем, что объединение множеств вершин орграфов D2,...,Dp дает множество вершин орграфа D, а значит D2,...,Dpвсе компоненты сильной связности орграфа D.

Утверждение 10. Пусть D' – компонента сильной связности орграфа D. Пусть также p(D) 2 и D" – орграф, получаемый в результате удаления из D вершин, содержащихся в D'. Тогда матрицами А(D"), S(D") являются подматрицы матриц A(D), S(D), получаемые в результате удаления из них строк и столбцов, соответствующих вершинам орграфа D'. Утверждение 10 является следствием утверждений 9 и 6.

Из определения матрицы сильной связности вытекает, что справедливо

Утверждение 11. Единицы i-й строки или i-го столбца матрицы сильной связности орграфа D=(V, X), где V={v1,.....,vn} соответствуют вершинам компоненты сильной связности ор­графа D, содержащей вершину vi.

Из утверждений 9–11 следует справедливость алгоритма определения числа компонент сильной связности орграфа D а также матриц смежности этих компонент.

Алгоритм 1.

Шаг 1. Полагаем р=1, S1=S(D).

Шаг 2. Включаем в множество вершин Vp очередной компо­ненты сильной связности Dp орграфа D вершины, соответствующие единицам первой строки матрицы Sp. В качестве A(Dp) бе­рем подматрицу матрицы A(D), находящуюся на пересечении строк и столбцов, соответствующих вершинам из Vp.

Шаг 3. Вычеркиваем из Sp строки и столбцы, соответствую­щие вершинам из Vp. Если в результате такого вычеркивания не остается ни одной строки (и соответственно ни одного столб­ца), то р --количество компонент сильной связности и A(D1),...,A(Dp) – матрицы смежности компонент сильной связности D1,...,Dp орграфа D. В противном случае обозначаем оставшу­юся после вычеркивания из Sp соответствующих строк и столб­цов матрицу через Sp+1, присваиваем р:=р+1 и переходим к шагу 2.

 

Замечание 3. После изменений в обозначениях и терми­нологии алгоритм 1 можно применить для определения числа компонент связности графа G, а также матриц смежности этих компонент. Для обоснования этого достаточно воспользоваться утверждениями, аналогичными утверждениям 9–11, но сформулированными для неориентированного графа G. Более того, алгоритм 1 остается справедливым и для произвольных псевдографов (ориентированных и не ориентированных). Доказательство аналогично.