Вариант 757761122.
Гамильтонов цикл в графе:
Какой алгоритм используется в алгоритме Кристофидеса?
В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:
Для чего применяется «метод условных вероятностей»:
Если алгоритму из темы про полиномиальный в среднем алгоритм упаковки подать на вход единичную матрицу инцидентности, он, если считать от длины входа, затратит время …
Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:
Формулировка (в виде ЦЛП) какой задачи приведена ниже:
Какова точность, гарантируемая алгоритмом Кристофидеса в метрической задаче коммивояжера?
Паросочетание, это подмножество...
Какие условия на существование полиномиального в среднем алгоритма упаковки требуются в соответствующей теме?