База ответов ИНТУИТ

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

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

Укажите нижнюю границу количества ребер простого графа с n вершинами, превышение которой означает связность графа:

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

Варианты ответа
{\frac{1}{2}}(n-1)(n-2)(Верный ответ)
{\frac{1}{2}}n(n-1)
{\frac{1}{2}}n^2
{\frac{1}{2}}(n-2)(n-3)
Похожие вопросы
Для простого графа с n вершинами укажите количества ребер, обеспечивающие связность графа:
Укажите свойство простого графа с количеством вершин n и количеством ребер большим {\frac{1}{2}}(n-1)(n-2):
Как соотносятся между собой графы G и H, если множество вершин графа H является подмножеством вершин графа G и множество ребер графа H состоит из всех ребер графа G, соединяющих вершины графа H:
Укажите соотношение между количество ребер в полном ориентированном графе и количеством ребер в полном неориентированном графе, оба графа с количеством вершин n:
Как соотносятся между собой графы G и H, если множество вершин графа H является подмножеством вершин графа G и все ребра графа H яаляются ребрами графа G:
Определите сложность решения задачи поиска кратчайших путей в графе с неотрицательными весами ребер n - количество вершин графа:
Какова максимальная длина простого пути в графе с n вершинами:
Сколько ребер содержит дерево с n вершинами?
Максимальное количество ребер в простом графе с n вершинами и k компонентами связности равно:
Какие из методов доказательства применяются при подсчете количества деревьев на n вершинах с k концевыми вершинами: