Автоматизированное проектирование промышленных изделий

<<- Назад к вопросам

Какие алгоритмы разбиения графа предполагают первоначальное разбиение на определённое число частей произвольным образом либо с помощью последовательного алгоритма. Затем по определённым правилам производится перестановка вершин из одной части в другую с целью минимизации числа внешних рёбер?

(Отметьте один правильный вариант ответа.)

Варианты ответа

алгоритмы, основанные на методе ветвей и границ

последовательные алгоритмы

итерационные алгоритмы(Верный ответ)

смешанные алгоритмы

Похожие вопросы

Какие алгоритмы разбиения графа предполагают первоначальное определение нижней оценки разбиения графа на заданное число частей. Затем производится построение дерева решений и осуществляется поиск оптимального результата?

Какие алгоритмы разбиения графа предполагают первоначальное "разрезание" с использованием алгоритма последовательного формирования кусков; дальнейшая оптимизация решения осуществляется перераспределением вершин между отдельными кусками графа?

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

Какая характристика графа указывает то наименьшее число рёбер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т.е. добиться отсутствия у графа циклов?

Как называют наименьшее возможное число подмножеств, получаемое в результате разбиения вершин графа G (X, U)

В каких алгоритмах производится переразмещение элементов или их групп с целью минимизации выбранного критерия?

Как называют минимальное число рёбер, которое необходимо удалить из графа для его плоского изображения?

Как называется часть графа, которая наряду с некоторым подмножеством рёбер графа содержит все вершины графа ( $X^{/} = X, U^{/} \subset U$ )?

Какие методы предполагают изменение значений технологических факторов процесса производится лишь после анализа предшествующих ситуаций?

Как называют граф, если известно, что число некратных рёбер графа $r \le n + 2$ ?