5. Показать, что ранг матрицы инциденций В связного графа с п вершинами равен п - 1; затем доказать, что ранг матрицы инциденций В графа с Р (слабыми) компонентами равен п -Р.

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

7. Доказать, что неориентированный граф с п вершинами

(а) содержит по крайней мере п - 1 ребер,

(б) если содержит более, чем п - 1 ребер, то имеет по крайней мере один цикл.

10. Список литературы

1. Берж К. (1962), Теория графов и ее применения, ИЛ, М.

2. Нагагу F., Norman R. Z., Cartwright D. (1965), Structural models: An introduction to the theory of directed graphs, Wiley, New York.

3. Kuratowski K. (1930), Sur le probleme des courbes gauches en topologie. Fund. Math., 15-16, p. 271.

4. Roy B. (1969, 1970), Algebre moderne et theorie des graphes. Vol. 1 (1969), Vol. 2 (1970), Dunod, Paris.

5*. Харари Ф., Теория графов, М., Мир , 1973.

Глава 2

ДОСТИЖИМОСТЬ и связность

1. Введение

в предыдущей главе отмечалось, что систему связи любой организации можно интерпретировать как граф, в котором люди представлены вершинами, а каналы связи дугами. Естественно при рассмотрении такой системы поставить вопрос, может ли информация от одного лица Xt быть передана другому лицу Х/, г. е. существует ли путь, идущий от вершины Xi к вершине xj. Если такой путь существует, то говорят, что вершина Xj достижима из Xi. Можно интересоваться достижимостью вершины xj из вершины Xi только на таких путях, длины которых не превосходят заданной величины. Целью этой главы является обсуждение некоторых фундаментальных понятий, касающихся достижимости и свойств связности графов, а также введение ряда весьма важных алгоритмов.

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

(i) Каково наименьшее число сотрудников, для которых каждый другой сотрудник в этой организации может быть достижим?

(ii) Каково наибольшее число сотрудников, которые взаимно достижимы?

(iii) Как между собой связаны вопросы (1) и (ii)?

2. Матрицы достижимостей и контрадостижимостей

Матрица достижимостей R = [г^] определяется следующим образом:

1, если вершина xj достижима из Xi, О в противном случае.

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

Контрадостижимым множеством Q (х,) графа G является множество таких вершин, что из любой вершины этого множества можно достигнуть вершину х,-. Аналогично построению достижимого множества R (х;) на основе соотношения (2.1) можно сформировать множество Q (xj), используя следующее выражение:

Q {Xi) = {х,-} и (хО и Г-2 (i) и . и Г- [Xi), (2.2) где Г-2(хг) = Г- (Г- (0) и т. д.

В оригинале применяется термин areaching matrix*. Мы будем испопь-аовать также термин матрица обратных достижимостей*.- Прим. ред..

Поскольку г (Xj) является множеством таких вершин х/, которые достижимы из х,- с использованием путей длины 1 (т. е. Г (х{) - такое множество вершин, для которых в графе существуют дуги (xj, X/)) и поскольку Г (xj) является множеством вершин, достижимых из Xj с помощью путей длины 1, то множество Г (Г (х,)) = Р (Х{) состоит из вершин, достижимых из Xj с использованием путей длины 2. Аналогично Г' (х^) является множеством вершин, которые достижимы из Xj с помощью путей длины р.

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

R Ы = {X,} и r.(xt) и П (хО и .... и (Xt). (2.1)

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

Матрицу достижимостей можно построить так. Находим достижимые множества R (х;) для всех вершин х,- £ X способом, приведенным выше. Положим Гц = 1, если xj R (xj), и = О в противном случае. Полученная таким образом матрица R является матрицей достижимостей.

Матрица контрадостижимостей ) Q = [q,]] определяется следующим образом:

1, если из вершины Х/ можно достигнуть вершину х,