Определив обратные дуги в глубинном остовном лесу

Предположим матрица стоимостей С совпадает с матрицей смежности для данного графа G т.е. С[i,j]=1, только в том случае, если есть дуга i→j и С[i,j]=0, если такой дуги не существует. Мы ходим вычислить матрицу А, такую что А \[i,j]=1, тогда и только тогда, когда существует путь от вершины i до j вершины длиной не менее 1, и А[i,j]=0, в противном случае. Такую матрицу A зачастую называют транзитивным замыканием матрицы смежности
bd – обратная дуга
Матрица смежностиМатрица замыкания
a b c d e
a b c d e
a 0 1 1 0 0
a 0 1 1 1 1
b 0 0 1 1 0
b 1 0 1 1 1
c 0 0 0 0 1
с 1 1 0 1 1
d 0 0 1 0 0
d 1 1 1 0 1
e 1 0 0 1 0
e 1 1 1 1 0
Рассмотрим граф G2 в качестве сети N2, задав источник и сток изобразите сеть N2(G2, c), где в качестве пропускных способностей дуг положите значение веса соответствующей дуги графа G2.
В теории графов транспортная сеть — ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток.
Выделяются две вершины: источник s и сток t такие, что любая другая вершина сети лежит на пути из s в t.
Пусть источник – a, а сток – d, тогда:
Для сети N2 определите её максимальный поток и найдите все минимальные разрезы.
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Минимальный разрез — разрез с минимальной пропускной способностью.
Максимальный поток равен 11;
{ce;ab;bd} – минимальный разрез;
15