Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
 |
Пусть 
- матрица смежности 
, 
задает все пути длины 2, 
– все пути длины 3, и т. д.
Тогда 
– матрица ТЗ,
Построение ТЗ напрямую требует 
умножений матриц
=> 
ЭШ.
Алгоритм Уоршолла расчета ТЗ орграфа
Рассмотрим последовательность матриц 
, элементы которых определяются рекуррентно:
Значения 
определяют, существует ли путь из 
в 
, в котором в качестве промежуточных могут использоваться только вершины из множества 
, к-рые могут следовать в произвольном порядке и не обязательно все 
(число дуг в пути 
).
Докажем, что 
тогда и только тогда, когда 
путь из в при заданных ограничениях на промежуточные вершины (МИ):
1. Базис очевиден.
2. Пусть 
, когда путь из в , проходящего только через вершины 
.
На следующем шаге путь существует, если выполняется одно из условий:
- он уже существовал на предыдущем шаге (
),
- он обязательно проходит через вершину , причем на предыдущем шаге уже было установлено существование путей из в и из в (
и 
).
В последнем случае на путях из в и из в не может быть совпадающих промежуточных вершин (в противном случае выполнялось бы 1-е условие). Конец док-ва.
=>
– искомые элементы матрицы транзитивного замыкания.
Расчет элементов матрицы ТЗ (исп-ся одна лог. матрица):
for (l = 1; l <= n; l++)
for (i = 1; i <= n; i++)
if (C[i][l])
for (j = 1; j <= n; j++)
C[i][j] |= C[l][j];
Трудоемкость алгоритма составляет 
.
2-й вариант алгоритма – строки матрицы смежности заданы как битовые строки длины :
for (l = 1; l <= n; l++)
for (i = 1; i <= n; i++)
if (C[i][l]) C[i] = C[i] | C[l];
Операции поиска кратчайших путей и ТЗ – частный случай операции замыкания над полукольцами 
:
.
Для транзитивного замыкания: 
.
Для кратчайших путей: 
.
Выделение компонент связности (кластеризация)
Компоненты связности неориентированного графа можно выделять с помощью транзитивного замыкания, но лучше – на основе поиска в глубину. При поиске для каждой вершины будем запоминать:
- номер в порядке обхода при поиске в глубину 
(синий),
- номер текущей компоненты связности 
(зеленый).
При поиске в глубину множество ребер графа разбивается на 2 непересекающихся подмножества:
– древесные (синие) и 
– обратные (красные).
 |
По ребрам, принадлежащим , производится переход от текущей вершины к очередной непроверенной. Древесные ребра образуют глубинный остовный лес – отдельные деревья (остовы) для каждой компоненты связности.
Каждая вершина графа принадлежит некоторому глубинному остовному дереву и имеет в нем предков и\или потомков в соответствии с порядком обхода вершин. Древесные ребра ведут от «отца» к «сыну», а обратные – от потомка к предку в глубинном дереве.
При поиске в глубину любое ребро 
проверяется дважды – как и как 
, но по результатам поиска оно будет отнесено либо к древесным, либо к обратным ребрам:
если 
, то 
.
Лемма: Если 
, то либо 
- предок 
, либо наоборот.
Док-во: Если рекурсивный поиск от вершины начинается раньше, то он не закончится, пока не будут просмотрены все вершины, достижимые из , в том числе, и . Но - обратное ребро, следовательно, и другой путь из в (состоящий только из древесных ребер).
Следствие: обратная дуга замыкает некоторый цикл, в котором остальные ребра – древесные.
Пусть 
вершины определен ее номер в порядке обхода при поиске в глубину (новый номер) 
. Тогда, если – предок, а – потомок в остовном дереве, то 
.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)