Дискретный анализ

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

Каким свойством обладает длина максимальных путей в графе без гамильтоновых циклов:

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

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

длина максимального пути не меньше суммы степеней начальной и конечной вершин графа

длина максимальных путей больше суммы двух наименьших степеней вершин графа

длина максимальных путей не меньше суммы двух наименьших степеней вершин графа(Верный ответ)

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

Определите сложность решения задачи поиска кратчайших путей в графе без циклов,

- количество вершин графа:

Длина пути в графе - это:

Какова минимальная длина цикла в простом графе:

Длина пути в ориентированном графе с весами ребер - это:

Определите сложность решения задачи поиска кратчайших путей в орграфе без циклов отрицательной длины,

- количество вершин графа

Определите сложность решения задачи поиска кратчайших путей в графе с неотрицательными весами ребер

- количество вершин графа:

Какова максимальная длина простого пути в графе с

вершинами:

Укажите соотношение между количество ребер в полном ориентированном графе и количеством ребер в полном неориентированном графе, оба графа с количеством вершин

Путь в графе - это:

Гамильтонов путь на простом неориентрованном графе - это: