Достижимость графов. Отношение достижимости модулей графов

Граф достижимости

Один из первых вопросов, возникающих при изучении графов, это вопрос о существовании путей между заданными или всеми парами вершин. Ответом на этот вопроc - введенное выше отношение достижимости на вершинах графа G=(V,E): вершина w достижима из вершины v, если v = w или в G есть путь из v в w. Иначе говоря, отношение достижимости является рефлексивным и транзитивным замыканием отношения E. Для неориентированных графов это отношение также симметрично и, следовательно, является отношением эквивалентности на множестве вершин V. В неориентированном графе классы эквивалентности по отношению достижимости называются связными компонентами. Для ориентированных графов достижимость, вообще говоря, не должна быть симметричным отношением. Симметричной является взаимная достижимость.

Определение 9.8. Вершины v и w ориентированного графа G=(V,E) называются взаимно достижимыми, если в G есть путь из v в w и путь из w в v.

Ясно, что отношение взаимной достижимости является рефлексивным, симметричным и транзитивным и, следовательно, эквивалентностью на на множестве вершин графа. Классы эквивалентности по отношению взаимной достижимости называются компонентами сильной связности или двусвязными компонентами графа.

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

Определение 9.9. Пусть G=(V,E) - ориентированный граф. Граф достижимости G * =(V,E *) для G имеет то же множество вершин V и следующее множество ребер E * ={ (u, v) | в графе G вершина v достижима из вершины u}.

Пример 9.3. Рассмотрим граф G из примера 9.2.

Рис. 9.2. Граф G

Тогда можно проверить, что граф достижимости G* для G выглядит так (новые ребра-петли при каждой из вершин 1-5 не показаны):

Рис. 9.3. Граф G*

Каким образом по графу G можно построить граф G * ? Один способ заключается в том, чтобы для каждой вершины графа G определить множество достижимых из нее вершин, последовательно добавляя в него вершины, достижимые из нее путями длины 0, 1, 2 и т.д.

Мы рассмотрим другой способ, основанный на использовании матрицы смежности A G графа G и булевых операций. Пусть множество вершин V={v 1 , … , v n }. Тогда матрица A G - это булева матрица размера n × n.

Ниже для сохранения сходства с обычными операциями над матрицами мы будем использовать "арифметические" обозначения для булевых операций: через + будем обозначать дизъюнкцию , а через · - конъюнкцию .

Обозначим через E n единичную матрицу размера n × n. Положим . Пусть Наша процедура построения G * основана на следующем утверждении.

Лемма 9.2. Пусть . Тогда

Доказательство проведем индукцией по k.

Базис. При k=0 и k=1 утверждение справедливо по определению и .

Индукционный шаг. Пусть лемма справедлива для k. Покажем, что она остается справедливой и для k+1. По определению имеем:

Предположим, что в графе G из v i в v j имеется путь длины k+1. Рассмотрим кратчайший из таких путей. Если его длина k, то по предположению индукции a_{ij}^{(k)}=1. Кроме того, a jj (1) =1. Поэтому a ij (k) a jj (1) =1 и a ij (k+1) =1. Если длина кратчайшего пути из из v i в v j равна k+1, то пусть v r - его предпоследняя вершина. Тогда из v i в v r имеется путь длины k и по предположению индукции a ir (k) =1. Так как (v r ,v j) E, то a_{rj}^{(1)}=1. Поэтому a ir (k) a rj (1) =1 и a ij (k+1) =1.

Обратно, если a ij (k+1) =1, то хотя бы для одного r слагаемое a ir (k) a rj (1) в сумме равно 1. Если это r=j, то a ij (k) =1 и по индуктивному предположению в G имеется путь из v i в v j длины k. Если же r j, то a ir (k) =1 и a rj (1) =1. Это означает, что в G имеется путь из v i в v r длины k и ребро (v r ,v j) E. Объединив их, получаем путь из v i в v j длины k+1.

Из лемм 9.1 и 9.2 непосредственно получаем

Следствие 1. Пусть G=(V,E) - ориентированный граф с n вершинами, а G * - его граф достижимости. Тогда A_{G*} = . Доказательство. Из леммы 5.1 следует, что, если в G имеется путь из u в v u, то в нем имеется и простой путь из u в v длины n-1. А по лемме 5.2 все такие пути представлены в матрице .

Таким образом процедура построения матрицы смежности A G* графа достижимости для G сводится к возведению матрицы в степень n-1. Сделаем несколько замечаний, позволяющих упростить эту процедуру.

где k - это наименьшее число такое, что 2 k n.

обнаруживается такое r, что a ir = 1 и a rj =1, то и вся сумма a ij (2) =1. Поэтому остальные слагаемые можно не рассматривать.

Пример 9.3. Рассмотрим в качестве примера вычисление матрицы графа достижимости A G* для графа G, представленного на рис.9.2 . В этом случае

Так как у G имеется 6 вершин, то . Вычислим эту матрицу:

и (последнее равенство нетрудно проверить). Таким образом,

Как видим, эта матрица действительно задает граф , представленный на рис.9.3 .

Взаимная достижимость, компоненты сильной связности и базы графа

По аналогии с графом достижимости определим граф сильной достижимости.

Определение 9.10. Пусть G=(V,E) - ориентированный граф. Граф сильной достижимости G * * =(V,E * *) для G имеет то же множество вершин V и следующее множество ребер E * * ={ (u, v) | в графе G вершины v и u взаимно достижимы}.

По матрице графа достижимости легко построить матрицу графа сильной достижимости. Действительно из определений достижимости и сильной достижимости непосредственно следует, то для всех пар (i,j), 1 i,j n, значение элемента равно 1 тогда и только тогда, когда оба элемента A G* (i, j) и A G* (j, i) равны 1, т.е.

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

Поместим в компоненту K 1 вершину v 1 и все такие вершины v j , что A_{G_*^*}(1,j) = 1.

Пусть уже построены компоненты K 1 , …, K i и v k - это вершина с минимальным номером, еще не попавшая в компоненты. Тогда поместим в компоненту K_{i+1} вершину v k и все такие вершины v j ,

что A_{G_*^*}(k,j) = 1.

Повторяем шаг (2) до тех пор, пока все вершины не будут распределены по компонентам.

В нашем примере для графа G на рис.2 по матрице получаем следующую матрицу графа сильной достижимости

Используя описанную выше процедуру, находим, что вершины графа G разбиваются на 4 компоненты сильной связности: K 1 = {v 1 , v 2 , v 3 }, \ K 2 ={ v 4 }, \ K 3 ={ v 5 }, \ K 4 ={ v 6 }. На множестве компонент сильной связности также определим отношение достижимости.

Определение 9.11. Пусть K и K" - компоненты сильной связности графа G. Компонента K достижима из компоненты K^\prime, если K= K" или существуют такие две вершины u K и v K", что u достижима из v. K строго достижима из K^\prime, если K K" и K достижима из K". Компонента K называется минимальной, если она не является строго достижимой ни из какой компоненты.

Так как все вершины в одной компоненте взаимно достижимы, то нетрудно понять, что отношения достижимости и строгой достижимости на компонентах не зависят от выбора вершин u K и v K".

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

Лемма 9.3. Отношение строгой достижимости является отношением частичного порядка, т.е. оно антирефлексивно, антисимметрично и транзитивно.

Это отношение можно представлять в виде ориентированного графа, вершинами которого являются компоненты, а ребро (K", K) означает, что K строго достижима из K". На рис. 9.4 показан этот граф компонент для рассматриваемого выше графа G.

Рис. 9.4.

В данном случае имеется одна минимальная компонента K 2 .

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

Определение 9.12. Пусть G=(V,E) - ориентированный граф. Подмножество вершин W V называется порождающим , если из вершин W можно достичь любую вершину графа. Подмножество вершин W V называется базой графа, если оно является порождающим, но никакое его собственное подмножество порождающим не является.

Следующая теорема позволяет эффективно находить все базы графа.

Теорема 9.1. Пусть G=(V,E) - ориентированный граф. Подмножество вершин W V является базой G тогда и только тогда, когда содержит по одной вершине из каждой минимальной компоненты сильной связности G и не содержит никаких других вершин.

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

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

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

Найти все компоненты сильной связности G.

Определить порядок на них и выделить минимальные относительно этого порядка компоненты.

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

Пример 9.5. Определим все базы ориентированного графа G, показанного на рис.9.5 .

Рис. 9.5. Граф G

На первом этапе находим компоненты сильной связности G:

На втором этапе строим граф строгой достижимости на этих компонентах.

Рис. 9.6. Граф отношения достижимости на компонентах G

Определяем минимальные компоненты: K 2 = { b }, K 4 ={ d,e, f, g} и K 7 = { r}.

Наконец перечисляем все четыре базы G: B 1 = { b, d, r}, B 2 = { b, e, r}, B 3 = { b, f, r} и B 1 = { b, g, r}.

Задачи

Задача 9.1. Докажите, что сумма степеней всех вершин произвольного ориентированного графа четна.

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

Задача 9.2. Перечислите все неизоморфные неориентированные графы, у которых не более четырех вершин.

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

Задача 9.4. Докажите, что неориентированный связный граф с n вершинами

содержит не менее n-1 ребер,

если содержит больше n-1 ребер, то имеет, по крайней мере, хотя бы один цикл.

Задача 9.5. Докажите, что в любой группе из 6 человек есть трое попарно знакомых или трое попарно незнакомых.

Задача 9.6. Докажите, что неориентированный граф G=(V,E) связен ↔ для каждого разбиения V= V 1 V 2 с непустыми V 1 и V 2 существует ребро, соединяющее V 1 с V 2 .

Задача 9.7. Докажите, что, если в неориентированном графе имеется ровно две вершины нечетной степени, то они связаны путем.

Задача 9.8. Пусть G=(V,E) неориентированный граф с |E| < |V|-1. Докажите, что тогда G несвязный граф.

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

Задача 9.10. Пусть неориентированный граф без петель G=(V,E) имеет k компонент связности. Доказать, что тогда

Задача 9.11. Определите, что представляет из себя граф достижимости для

графа с n вершинами и пустым множеством ребер;

графа с n вершинами: V= {v 1 ,… , v n }, ребра которого образуют цикл:

Задача 9.12. Вычислите матрицу графа достижимости для графа

и постройте соответствующий ей граф достижимости. Найдите все базы графа G.

Задача 9.13. Построить для заданного на рис. 9.7 ориентированного графа G 1 =(V,E) его матрицу смежности A G1 , матрицу инцидентности B G1 и списки смежности. Вычислить матрицу достижимости A G1* и построить соответствующий граф достижимости G 1 * .

Рис. 9.7.

Неориентированные и ориентированные деревья

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

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

Определение 10.2. Ориентированный граф G=(V,E) называется (ориентированным) деревом, если

На рис. 10.1 показаны примеры неориентированного дерева G 1 и ориентированного дерева G 2 . Обратите внимание на то, что дерево G 2 получено из G 1 с помощью выбора вершины c в качестве корня и ориентации всех ребер в направлении "от корня".

Рис. 10.1. Неориентированное и ориентированное деревья

Это не случайно. Докажите самостоятельно следующее утверждение о связи между неориентированными и ориентированными деревьями.

Лемма 10.1. Если в любом неориентированном дереве G=(V,E) выбрать произвольную вершину v V в качестве корня и сориентировать все ребра в направлении "от корня", т.е. сделать v началом всех инцидентных ей ребер, вершины, смежные с v - началами всех инцидентных им еще не сориентированных ребер и т.д., то полученый в результате ориентированный граф G" будет ориентированным деревом.

Неориентированные и ориентированные деревья имеют много эквивалентных характеристик.

Теорема 10.1. Пусть G=(V,E) - неориентированный граф. Тогда следующие условия эквивалентны.

G является деревом.

Для любых двух вершин в G имеется единственный соединяющий их путь.

G связен, но при удалении из E любого ребра перестает быть связным.

G связен и |E| = |V| -1.

G ациклический и |E| = |V| -1.

G ациклический, но добавление любого ребра к E порождает цикл.

Доказательство (1) (2): Если бы в G некоторые две вершины соединялись двумя путями, то, очевидно, в G имеелся бы цикл. Но это противоречит определению дерева в (1).

(2) (3): Если G связен, но при удалении некоторого ребра (u,v) E не теряет связности, то между u и v имеется путь, не содержащий это ребро. Но тогда в G имеется не менее двух путей, соединяющих u и v, что противоречит условию (2).

(3) (4): Предоставляется читателю (см. задачу 9.4).

(4) (5): Если G содержит цикл и является связным, то при удалении любого ребра из цикла связность не должна нарушиться, но ребер останется |E|= V -2, а по задаче 9.4(а) в связном графе должно быть не менее V -1 ребер. Полученное противоречие показывает, что циклов в G нет и выполнено условие (5).

(5) (6): Предположим, что добавление ребра (u,v) к E не привело к появлению цикла. Тогда в G вершины u и v находятся в разных компонентах связности. Так как |E|= V -1, то в одной из этих компонент, пусть это (V 1 ,E 1), число ребер и число вершин совпадают: |E 1 |=|V 1 |. Но тогда в ней имеется цикл (см. задачу 9.4 (б)), что противоречит ацикличности G.

(6) (1): Если бы G не был связным, то нашлись бы две вершины u и v из разных компонент связности. Тогда добавление ребра (u,v) к E не привелобы к появлению цикла, что противоречит (6). Следовательно, G связен и является деревом.

Для ориентированных деревьев часто удобно использовать следующее индуктивное определение.

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

Рис. 10.2 иллюстрирует это определение.

Рис. 10.2. Индуктивное определение ориентированных деревьев

Теорема 10.2. Определения ориентированных деревьев 10.2 и 10.3 эквивалентны.

Доказательство Пусть граф G=(V,E) удовлетворяет условиям определения 10.2. Покажем индукцией по числу вершин |V|, что .

Если |V|=1, то единственная вершина v V является по свойству (1) корнем дерева, т.е. в этом графе ребер нет: E = . Тогда .

Предположим, что всякий граф с n вершинами, удовлетворяющий определению 10.2 входит в . Пусть граф G=(V,E) с (n+1)-й вершиной удовлетворяет условиям определения 10.2. По условию (1) в нем имеется вершина-корень r 0 . Пусть из r 0 выходит k ребер и они ведут в вершины r 1 , … , r k (k 1). Обозначим через G i ,(i=1, …, k) граф, включающий вершины V i ={ v V|v \textit{ достижима из }r i } и соединяющие их ребра E i E. Легко понять, что G i удовлетворяет условиям условиям определения 10.2. Действительно, в r i не входят ребра, т.е. эта вершина - корень G i . В каждую из остальных вершин из V i входит по одному ребру как и в G . Если v V i , то она достижима из корня r i по определению графа G i . Так как |V i | n, то по индуктивному предположению . Тогда граф G получен по индуктивному правилу (2) определения 10.3 из деревьев G 1 , …, G k и поэтому принадлежит классу .

⇐ Если некоторый граф G=(V,E) входит в класс , то выполнение условий (1)-(3) определения 10.2 для него легко установить индукцией по определению 10.2. Предоставляем это читателю в качестве упражнения.

С ориентированными деревьями связана богатая терминология, пришедшая из двух источников: ботаники и области семейных отношений.

Корень - это единственная вершина, в которую не входят ребра, листья - это вершины, из которых не выходят ребра. Путь из корня в лист называется ветвью дерева. Высота дерева - это максимальная из длин его ветвей. Глубина вершины - это длина пути из корня в эту вершину. Для вершины v V, подграф дерева T=(V,E), включающий все достижимые из v вершины и соединяющие их ребра из E, образует поддерево T v дерева T с корнем v (см. задачу 10.3). Высота вершины v - это высота дерева T v . Граф, являющийся объединением нескольких непересекающихся деревьев, называется лесом.

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

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

По аналогии с графом достижимости определим граф сильной достижимости.

Определение: Пусть– ориентированный граф.Граф сильной достижимости
дляимеет тоже множество вершини следующее множество рёбер
в графевершиныивзаимно достижимы.

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

По матрице
можно выделить компоненты сильной связности графаследующим образом:

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

В нашем примере для графа примера 14.1. по матрице
получаем следующую матрицу графа сильной достижимости

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

Определение: Пусть
и
– компоненты сильной связности графа. Компонента
достижима из компоненты
, если
или существуют такие две вершины
и
, чтодостижима из.
строго достижима из
, если
и
достижима из
. Компонента
называется минимальной, если она не является строго достижимой ни из какой компоненты.

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

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

Лемма: Отношение строгой достижимости является отношением частичного порядка, т.е. оно антирефлексивно, антисимметрично и транзитивно.

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

В данном случае имеется одна минимальная компонента
.

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

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

Следующая теорема позволяет эффективно находить все базы графа.

Теорема: Пусть
- ориентированный граф. Подмножество вершин
является базой тогда и только тогда, когда содержит по одной вершине из каждой минимальной компоненты сильной связности и не содержит никаких других вершин.

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

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

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

Пример 14.3: Определим все базы ориентированного графа .

На первом этапе находим компоненты сильной связности :

На втором этапе строим граф строгой достижимости на этих компонентах.

Определяем минимальные компоненты:
,
и
.

Наконец перечисляем все четыре базы :
,
,
и
.

1. Достижимость и контрдостижимость

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

Достижимость в графе описывается матрицей достижимости R = ||г,у||, i,j =1,2,... п, где п - число вершин графа, а каждый элемент определяется следующим образом:

Гу- 1, если вершина х, достижима из х,

Гу= 0 в противном случае.

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

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

Как видим, множество достижимых вершин R(x,) представляет собой прямое транзитивное замыкание вершины х„ т.е. R(x,) = Т (х,). Следовательно, для построения матрицы достижимости находим достижимые множества R(x,) для всех вершин х, е X. Полагая г у - 1, если х 7 е R(x,) и гу- 0 в противном случае. Для графа, приведенного на рис. 59.4, а , множества достижимостей находятся следующим образом:

Рис. 59.4.

Матрицы смежности (А), достижимости (R), контрдостижимости (Q) имеют следующий вид:

Матрица контрдостижимости Q = qij, i,j= 1,2,... п, где п - число вершин графа, определяется следующим образом:

qij= 1, если из вершины ху можно достичь вершину x h qtj = Ов противном случае.

Контрдостижимым множеством Q(x,) является множество таких вершин, что из любой вершины этого множества можно попасть в вершину X/. Аналогично построению достижимого множества R(x,) можно записать выражение для Q(x,):

Таким образом, видно, что Q(x,) есть не что иное как обратное транзитивное замыкание вершины х, т.е. Q(x () = Т"(х,). Из определений видно, что столбец X, матрицы Q (в котором q t j = 1, если ху€ Q(x,), и с/у=0 в противном случае) совпадает со строкой х, матрицы R, т.е. Q = R , где R - матрица, транспонированная к матрице достижимости R.

Матрица контрдостижимости показана ранее.

Следует отметить, что поскольку все элементы матриц R и Q равны 1 или 0, каждую строку можно хранить в двоичной форме, экономя затраты памяти ЭВМ. Матрицы R и Q удобны для обработки на ЭВМ, так как в вычислительном отношении основными операциями являются быстродействующие логические операции.

2. Нахождение множества вершин, входящих в путь Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как Т + (х,) - это множество вершин, в которые есть пути из вершины х„ а Т"(У) - множество вершин, из которых есть пути в х / , то Т (х,) n Т(xj) - множество вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от х, к ху. Эти вершины называются существенными, или неотъемлемыми относительно двух концевых вершин X, и ху. Все остальные вершины графа называются несущественными, или избыточными, поскольку их удаление не влияет на пути от х/ к ху.

Так, для графа на рис. 59.5 нахождение вершин, входящих в путь, например, из вершины Х2 в вершину Х4, сводится к нахождению Т + (хг) = {хг, хз, Х4, Х5, Хб}, Т"(х4) = {xi, Х2, Х3, Х4, Х5}, и их пересечения Т + (хг) п Т(х4) = = {Х2, Хз, Х4, Х 5 }.

Пусть G = (X , Г) - граф модульной структуры, х г, х-. - вершины, принадлежащие X. Если в графе G существует ориентированная цепь от х, к Хр то вершина х,- - достижима из вершины х,-. Справедливо следующее утверждение: если вершина Xj достижима из х, ах (- из Хр то X/ достижима из х^ Доказательство этого факта очевидно. Рассмотрим бинарное отношение на множестве X, которое определяет достижимость между вершинами графа. Введем обозначение х, -> х, для достижимости вершины х,- из Xj. Отношение транзитивно. Обозначим через Я(х,) множество вершин графа G, достижимых из х; . Тогда равенство

определяет транзитивное замыкание х, по отношению к достижимости.

Докажем следующую теорему.

Теорема 1.1. Для выбранного компонента связности графа модульной структуры любая вершина достижима из корневой, соответствующей данному компоненту, т.е. выполняется равенство (х/- корневая вершина)

Доказательство. Предположим, вершинах, (х,е X) недостижима из Xj. Тогда х, ё X/ и множество X" = X х), непусто. Поскольку выбранный компонент графа связанный, то существуют вершина х,- е х, и цепь /7(х; , xj), ведущая от х, к х,-. Исходя из ацикличности графа G, в X" должна существовать простая цепь Н(х/, xj), где в вершину x f не входят дуги (данная цепь может быть пустой, если X" состоит только из х,). Рассмотрим цепь Я(х/, xj) = Н (х/, х,) U Я (х, xj). Это означает, что модуль х. достижим из вершин х, и Xj и обе вершины не содержат входящих дуг. А это противоречит определению графа модульной структуры с единственной корневой вершиной. Теорема доказана.

Основное требование для обеспечение достижимости - это отсутствие неориентированных циклов в графе. Исходя из графа на рис. 1.4, отмечаем, что граф содержит ориентированный цикл и модули, соответствующие вершинам х 4 , х 5 , ж 6 , никогда выполняться не будут. Таким образом, результаты теоремы 1.1 усиливают требование отсутствия ориентированных циклов в графе модулей.

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

Коэффициент а,у= 1, если модуль, соответствующий индексу /, достижим из модуля, соответствующего индексу i. Следующие результаты основаны на известной теореме из теории графов.

Рис. 1.4.

Теорема 1.2. Коэффициент ту l-й степени матрицы смежности Доопределяет количество различных маршрутов, содержащих / дуг и связывающих вершину X/ с вершиной ^-ориентированного графа.

Рассмотрим следующие три следствия из этой теоремы .

Следствие 1.1. Матрица М = "? J M t , где М - матрица смежности ориен-

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

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

я, определяет количество всех возможных путей в графе с количеством дуг п. Пусть коэффициент т 1} матрицы М отличен от нуля. Это означает, что существует степень матрицы М>, у которой соответствующий коэффициент т {} также отличен от нуля. Следовательно, существует путь, идущий от вершины Xj к Хр т.е. вершина ^ достижима из х г Данное следствие определяет связь матрицы вызовов графа модульной структуры, совпадающей с матрицей смежности А/, с матрицей достижимости А и определяет алгоритм построения последней.

Следствие 1.2. Пусть для некоторого i в последовательности степеней матрицы смежности М* существует коэффициент т Х1 > 0. Тогда в исходном графе существует ориентированный цикл.

Доказательство. Пусть m (i > 0 для некоторого I. Следовательно, Xj достижима из x v т.е. существует цикл. Согласно теореме 1.2 данный цикл имеет / дуг (в общем случае повторяющихся).

Следствие 1.3. Пусть п-я степень матрицы смежности М п ациклического графа совпадает с нулевой матрицей (все коэффициенты равны нулю).

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

Для ациклических графов отношение достижимости эквивалентно частичному строгому порядку. Транзитивность отношения достижимости рассмотрена выше. Антисимметричность следует из отсутствия ориентированных циклов: если вершина х } достижима из x v то обратное неверно. Введем обозначение х х > Хр если вершина Xj достижима из вершины x v

Пусть G = (X, Г) - ациклический граф, соответствующий некоторой модульной структуре. Рассмотрим убывающую цепь элементов частично упорядоченного множества X:

где через знак «>» обозначено отношение достижимости. Поскольку X конечно, то цепь обрывается х п > x i2 > ... > x in . Вершина x jn не имеет исходящих дуг, т.е. элемент x in минимальный (ему соответствует модуль, который не содержит обращения к другим модулям). Максимальный элемент во множестве X - корневая вершина.

• Доказательство этой теоремы приводится в работе (книга): Лаврищева Е. М., Грищенко В. Н. Сборочное программирование. Киев: Наукова думка, 1991. 287 с.

ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ В ГРАФАХ План лекции: Маршруты цепи и циклы. Связность графа и компоненты связности. Диаметр радиус и центр графа.

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 8. Достижимость и связность в графах

Лекция 8. ДОСТИЖИМОСТЬ И СВЯЗНОСТЬ В ГРАФАХ

План лекции:

1. Маршруты, цепи и циклы.
2. Связность графа и компоненты связности.
3. Диаметр, радиус и центр графа.
4. Матрицы достижимости и контрадостижимости.

1. Маршруты, цепи и циклы

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

, (1)

, (2)

(3)

являются путями.

Рис. 1.

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

Простой называется орцепь, в которой каждая вершина используется не более одн о го раза. Например, орцепь (3) является простой, а орцепь (2) – нет.

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

Аналогично тому, как мы определили орцепи и простые цепи, можно определить цепи и простые цепи.

Путь или маршрут можно изображать также последовательностью вершин. Напр и мер, путь (1) можно записать в виде: .

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

1. Связность графа и компоненты связности

Говорят, что вершина в орграфе достижима из вершины, если существует путь. Если при этом достижима из, то об этих вершинах говорят, что они взаимно достижимы.

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

° ° °

° ° ° ° ° °

° ° ° ° ° °

а б в

Рис. 2.

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

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

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

Для орграфа определены три типа компонент связности: сильная компонента – ма к симально сильный подграф, односторонняя компонента – максимальный одност о ронний подграф и слабая компонента – максимально слабый подграф.

Понятие сильной компоненты иллюстрирует рис. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Рис. 3

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

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

Графы являются связными и в сумме дают граф. Эти графы называются компонентами связности графа. Число – еще одна числовая характеристика графа. Для связного графа, если граф несвязный, то.

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

1. Диаметр, радиус и центр графа

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

2) ;

3) .

Определим расстояние от каждой вершины графа до самой далекой от нее вершины

которое называется эксцентриситетом . Очевидно, что эксцентриситет для всех вершин в полного графа равен единице, а для вершин простого цикла – .

Максимальный эксцентриситет носит название диаметра графа, а минимальный – радиуса графа. В полном графе имеем, а в простом цикле – .

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

Пример 1. Найти диаметр, радиус и центр графа, приведенного на рис. 4.

° °

° ° °

° °

° °

Рис. 4.

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

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

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

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

Матрица достижимостей определяется следующим образом:

Множество вершин графа, достижимых из заданной вершины, состоит из таких элементов, для которых -й элемент в матрице равен 1. Это множество можно представить в виде

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

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

Из определений следует, что -й столбец матрицы совпадает с -й строкой ма т рицы, т. е. , где – матрица, транспонированная к матрице.

Пример 2. Найти матрицы достижимостей и контрадостижимостей для графа, пр и веденного на рис. 5.

Рис. 5.

Определим множества достижимостей для вершин графа:

Следовательно, матрицы достижимостей и контрадостижимостей имеют вид:

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

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

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