Прежде чем определить понятие конечного графа в наиболее общей форме, представим себе на плоскости (или в вещественном аффинном пространстве произвольной размерности 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 остается справедливым и для произвольных псевдографов (ориентированных и не ориентированных). Доказательство аналогично.
< Предыдущая | Следующая > |
---|