Материал: Дискретная математика. учебное пособие. Собенина О.В

Последовательность обозначается одной буквой D, т. е. D= . Очевидно, что порядок членов в графической последовательности несуществен, а каждый ее член удовлетворяет неравенствам . Часто удобно эти последовательности считать невозрастающими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом.

Назовем последовательность правильной, если выполняются два следующих условия:

1. , (4.1)

2. – четное число. (4.2)

Без ограничения общности графическую последовательность можно считать правильной.

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

Рассмотрим последовательность D=(2, 2, 2, 2, 1, 1, 1, 1). Существует ровно пять графов, являющихся реализациями последовательности D. Они имеют следующие компоненты: 1) С₄, К₂ и К₂, 2) К₃, Р₃ и К₂, 3) Р₆ и К₂, 4) Р₅ и Р₃, 5) Р₄ и Р₄. Здесь С₄ – простой цикл, содержащий 4 вершины, Р_n – простые цепи, содержащие n вершин (n=3,4,5,6).

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

Рассмотрим графическую последовательность , упорядоченную по невозрастанию: . Пусть – степень вершины . «Изъять » означает соединить соответствующую вершину с вершинами , если , или с вершинами , если . Последовательность , если , или , если , называется остаточной последовательностью после изъятия или просто остаточной последовательностью.

Хакими и Гавел предложили алгоритм построения простого графа (если он существует), имеющего заданную последовательность степеней [3]. Этот результат основан на результате, являющимся частным случаем (при k=1) следующей теоремы.

Теорема 4.7.1. Если последовательность , , является последовательностью степеней простого графа, то этим свойством обладает и остаточная последовательность после изъятия .

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

Шаг 1. – последовательность степеней, упорядоченная по невозрастанию. Выберем произвольное 0 и «изымем» из последовательности, соединяя вершину с первыми вершинами, не считая саму вершину .

Шаг 2. Упорядочим остаточную последовательность в порядке невозрастания.

Шаг 3. Шаги 1–2 выполнять до тех пор, пока не возникнет одна из следующих ситуаций:

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

б) хотя бы одна из остаточных степеней отрицательна – это означает, что последовательность не является графической, т. е. не существует простого графа, который ее реализует.

Для иллюстрации описанного алгоритма рассмотрим пример последовательности

D=(4, 3, 3, 2, 2).

После изъятия (обведенной кружком), получим последовательность

D'=(3, 2, 0, 1, 2),

которая после переупорядочивания остаточных степеней принимает вид

D₁=(3, 2, 2, 1, 0).

Затем, изымая степень, соответствующую вершине , получим

D'₁=(2, 1, 0, 1, 0).

Переупорядочивая остаточные степени в D'₁, получим

D₂=( 2, 1, 1, 0, 0).

Теперь, изымая степень, соответствующую вершине , получим

D'₂=(0, 0, 0, 0, 0).

Здесь алгоритм заканчивает работу, так как все остаточные степени равны нулю. Последовательность (4, 3, 3, 2, 2) графическая. Требуемый граф (рис. 4.22) получается в результате выполнения шагов, соответствующих порядку изъятия степеней:

1. Соединяем вершину с вершинами , и .

2. Соединяем вершину с вершинами и .

3. С оединяем вершину с вершинами и .

Рис. 4.22. Граф с последовательностью степеней (4, 3, 3, 2, 2)

Замечание. Можно привести пример последовательности, например, (3, 3, 1, 1), для которой условия (4.1) – (4.2) выполняются, но она не является графической. Условия (4.1) – (4.2) не являются достаточными для того, чтобы последовательность была графической.

4.8. Достижимость и связность

4.8.1. Основные определения

Понятия связности и достижимости используются для исследования структур различных организаций. Например, систему связи любой организации можно интерпретировать как граф, в котором люди представлены вершинами, а каналы связи – дугами. Естественно при рассмотрении такой системы поставить вопрос, может ли информация от одного лица x_i быть передана другому лицу х_j, т. е. существует ли путь, идущий от вершины x_i к вершине х_j. Если в графе существует путь, идущий от вершины x_i к вершине х_j, то говорят, что вершина x_j достижима из вершины х_i.

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

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

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

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

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

Маршрут есть неориентированный двойник пути. Маршрут позволяет осуществлять «движение» по дугам, без учета их направленности.

Пример. Граф, приведенный на рис. 4.23(а) является сильно связный. Граф, показанный на рис. 4.23(б), не является сильным, так как в нем нет пути из x₅ в x₂, но односторонне связный. Граф, изображенный на рис. 4.23(в), не является ни сильным, ни односторонним, поскольку в нем не существует путей от x₅ к x₂ и от x₂ к x₅. Он – слабо связный. Наконец, граф, приведен­ный на рис. 4.23(г), является несвязным.

Рис. 4.23. Сильно связный граф (а), односторонне связный граф (б), слабо связный граф (в), несвязный граф (г)

Пусть дано некоторое свойство Р, которым могут обладать графы. Максимальным подграфом графа G относительно свойства Р называется порожденный подграф (X_S) графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа (Х_H), у которого X_SX_H и который также обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связность, то максимальным сильным подграфом графа G является сильный подграф, который не содержится в любом другом сильном подграфе, такой подграф называется сильной компонентой графа G. Это определения можно дать так: всякий максимальный по включению сильно связный подграф данного графа называется его сильной компонентой связности. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента  максимальный слабый подграф.

Например, в графе G, приведенном на рис. 4.23(6), подграф ({х₁, x₄, х₅, х₆}) является сильной компонентой графа G. С другой стороны, подграфы ({х₁, х₆}) и ({х₁, х₅, х₆}) не являются сильными компонентами, хотя и являются сильными подграфами, поскольку они содержатся в графе ({х₁, x₄, x₅, х₆}) и, следова­тельно, не максимальные. В графе, показанном на рис. 4.23(в), подграф ({x₁, x₄, х₅}) является односторонней компонентой. В графе, приведенном на рис. 4.23(г), оба подграфа ({х₁, х₅, х₆}) и ({х₂, х₃, x₄}) являются слабыми компонентами, и у этого графа только две такие компоненты.

Из определений сразу же следует, что односторонние компоненты графа могут иметь общие вершины. Сильная компонента должна содержаться по крайней мере в одной односторонней компоненте, а односторонняя компонента содержится в некоторой слабой компоненте данного графа G.

Максимальный связный подграф неориентированного графа G называется компонентой связности.

Максимальный сильно связный подграф ориентированного графа G называется сильной компонентой связности (СК).

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

4.8.2. Матрицы достижимостей

и контрдостижимостей

М атрица достижимостей графа G=(X,V) , определяется следующим образом:

Множество вершин R(x_i) графа G, достижимых из заданной вершины x_i, состоит из таких элементов x_j, для которых (i, j)-й элемент в матрице достижимостей равен 1. Считают, что каждая вершина достижима из себя самой с помощью пути длины 0, поэтому все диагональные элементы в матрице R равны 1.

Поскольку Г(x_i) является множеством таких вершин x_j, которые достижимы из x_i c использованием путей длины 1 (т.е. Г(x_i) – такое множество вершин, для которых в графе суще­ствуют дуги (x_i, x_j)) и поскольку Г(x_j) является множеством вершин, достижимых из x_j с помощью путей длины 1, то множество Г(Г(x_i))=Г²(x_i) состоит из вершин, достижимых из x_i c использованием путей длины 2. Аналогично Г^p(x_i) является множеством вершин, которые достижимы из x_i с помощью путей длины р.

Так как любая вершина графа G, которая достижима из x_i, должна быть достижима с использованием пути (или путей) дли­ны 0, или 1, или 2, ..., или р (с некоторым конечным р≤n), то множество вершин, достижимых из x_i , можно представить в виде

R(x_i) = { x_i }ÈГ(x_i)È Г² (x_i )È…È Г^p (x_i ) (4.3)

Таким образом, множество R(x_i) может быть получено последова­тельным выполнением (слева направо) операций объединения в соотношении (4.3), до тех пор, пока «текущее» множество не перестанет изменяться при очередной операции объединения. С этого момента последующие операции не будут давать новых элементов множеству и, таким образом, будет получено, достижимое множество R(x_i). Число объединений, которое нужно выполнить, зависит от графа, но, очевидно, что число р меньше числа вершин в графе.

Матрицу достижимостей можно построить так. Находим достижимые множества R(x_i) для всех вершин x_iÎХ способом, приведенным выше. Положим r_ij=1, если x_jÎR(x_i), и r_ij=0 в противном случае. Полученная таким образом матрица R является матрицей достижимостей.

М атрица контрдостижимостей (матрица обратных достижимостей) , определяется следующим образом: