Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности

G(V,X) с петлями, но без кратных дуг задает бинарное отношение Х на множестве V. Полный граф соответствует универсальному соотношению. Неориентированный граф соответствует симметричному соотношению. Дополнение графа соответствует дополнению отношения. Изменение направления дуг соответствует обратному отношению.

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

Вершина b орграфа (графа) G называется достижимой из U в том и только том случае, когда U=V или существует путь (маршрут) соединяющий U с V (U – начальная вершина, V – конечная вершина). Таким образом на множестве вершин орграфа (графа) определено не только отношение смежности А, но и отношение достижимости Т.

Матрицей достижимости Т орграфа(графа) G называется T² n×n, элементы которой находятся из условия: 1, если достижимо из ; 0, если не достижимо из .

Введенное отношение достижимости на вершинах графа G(V,Х): вершина w достижима из вершины v, если v = w или в G есть путь из v в w. Иначе говоря, достижимость является рефлексивным и транзитивным замыканием отношения смежности.

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

Введенное отношение достижимости на вершинах графа G(V,Х): вершина w достижима из вершины v, если v = w или в G есть путь из v в w. Иначе говоря, достижимость является рефлексивным и транзитивным замыканием отношения смежности.

Найти матрицу смежности, транзитивное и рефлексивное замыкание.

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

G(V,Х) называется связным, если любая его вершина достижима из любой другой вершины.

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

Орграф G(V,Х) называется сильно связным, если любая его вершина достижима из любой другой.

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

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

Компонентой сильнодействующей связи орграфа G(V,Х) называется максимальное, по числу вхождения вершин сильносвязный подграф данного орграфа. Аналогично определяется компонента связности не орграфа.

Матрицей сильной связности (связности) орграфа (графа) G(V,Х) называется S n×n, элементы которой находятся из условия: 1, если достижимо из и достижимо из ; 0, если не достижимо из и не достижимо из .

Про содержание матрицы S можно судить о том, является или нет соответствующей ей граф

(орграф) сильносвязным или связным, для этого достаточно определить наличие 0 в матрице, если

0 нет, то граф (орграф) является связным (сильносвязным) в противном случае нет.

Матрица сильной связности может быть построена из матрицы достижимости по формуле