Расставить в правильном порядке шаги алгоритма Гомори-Ху.

Условие:

Расставить в правильном порядке шаги алгоритма Гомори-Ху.

Решение:

Чтобы правильно расставить шаги алгоритма Гомори-Ху, следуйте такому порядку: 1. Выбрать две вершины графа. Обозначить одну из них через vs, а другую через vt. 2. По алгоритму Форда-Фалкерсона найти максимальный поток из источника vs в сток vt. 3. Заменить ребра из минимального разреза \((Vs, Vt)\) одним ребром, а вершины бока разреза, в котором не лежат вершины \(vi, vj\) - одной вершиной. Пропускную способность в ребре принять равным пропускной способности разреза \((Vs, Vt)\). 4. Выбрать две вершины графа \(vi\) и \(vj\) из \(Vs\) или \(Vt\). Положить \(vi = vs\), \(vj = vt\) и вернуться к шагу на нахождению максимального потока. 5. Получено конечное дерево разрезов. В этом дереве каждой вершине соответствует одна вершина исходного графа. По нему строится матрица максимальных потоков. Расставим эти шаги правильно в опроснике: 1. "Выбрать две вершины графа. Обозначить одну из них через vs, а другую через vt." 2. "По алгоритму Форда-Фалкерсона найти максимальный поток из источника vs в сток vt." 3. "Заменить ребра из минимального разреза (Vs, Vt) одним ребром, а вершины бока разреза, в котором не лежат вершины vi, vj – одной вершиной. Пропускную способность в ребре принять равными пропускной способности разреза (Vs, Vt)." 4. "Выбрать две вершины графа vi и vj из Vs или Vt. Положить vi = vs, vj = vt и вернуться к шагу на нахождению максимального потока." 5. "Получено конечное дерево разрезов. В этом дереве каждой вершине соответствует одна вершина исходного графа. По нему строится матрица максимальных потоков." Теперь порядок шагов может правильно отображать алгоритм Гомори-Ху в опроснике.