Определив обратные дуги в глубинном остовном лесу. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по программированию
Определив обратные дуги в глубинном остовном лесу

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

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Определив обратные дуги в глубинном остовном лесу, постройте граф G2 на основе исходного Графа, удалив найденные обратные дуги. Для графа G2 вычислите матрицу транзитивного замыкания.

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Предположим матрица стоимостей С совпадает с матрицей смежности для данного графа 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

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу