АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Граф G1=(V, U1) называется транзитивным замыканием графа G=(V, U), если (a, b) U1

Граф G ₁=(V, U₁) называется транзитивным замыканием графа G =(V, U), если (a, b) U ₁ (в графе G вершины a и b соединяет некоторый путь).

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

Определим операцию логического умножения двоичных матриц.

Пусть A = (a_i, _j) и B = (b_i, _j) - двоичные матрицы, имеющие размер n n. Двоичная матрица C = (c_i, _j) размером n n, является логическим произведением A и B, если значение элемента c_i, _j, лежащего на пересечении строки с номером i и столбца с номером j матрицы C, равно:

c_{i , j} = .

Логическое произведение матриц A и B записывается как A B.

Тогда, если A - это матрица смежности для графа G =(V, U), где V = { v ₁,... v _n}, то a_{i , j} = 1 тогда и только тогда, когда из вершины v_i в вершину v_j ведет ребро.

В матрице A A значение a_i, _j = 1 тогда и только тогда когда в графе G из v_i в v_j ведет путь длиной 2.

Аналогично в матрице A^r = A ... A (произведение
r матриц A) элемент a_i, _j равен 1 тогда и только тогда, когда в G из v_i в v_j ведет путь длиной r - 1.

Если вершины v_i и v_j в графе G с n вершинами соединяет некоторый путь, то существует и элементарный путь между этими вершинами, который имеет длину, не превосходящую
n - 1.

Поэтому матрица B = A⁰ A¹ A² ... A^n-1 представляет транзитивное замыкание графа G.

Здесь дизъюнкция матриц понимается как поэлементная дизъюнкция одинаково расположенных в них элементов. Матрица A⁰ - это единичная диагональная матрица, которая содержит значение 1 только на главной диагонали. Такая матрица представляет наличие путей нулевой длины из всякой вершины графа в эту же вершину.

Действительно, элемент b_i,_j матрицы B принимает значение 1 тогда и только тогда, когда вершины v_i и v_j в G соединяет хотя бы один путь, длина которого не превосходит
n - 1.

Дата добавления: 2015-09-27 | Просмотры: 409 | Нарушение авторских прав