Question

Дан связный граф на 20 вершинах. Какое максимальное и какое минимальное количество ребер у него может быть

Answer 1

Ответ:

19900

Пошаговое объяснение:

200*199/2=19900

Answer 2

Для связного графа на $n$ вершинах (где $n \geq 2$), минимальное количество рёбер будет достигаться в случае дерева, а максимальное количество рёбер - в случае полного графа. Давайте рассмотрим минимальное и максимальное количество рёбер для связного графа на 20 вершинах:

1. Минимальное количество рёбер:

   • Минимальное количество рёбер будет в случае, если граф является деревом. Дерево на $n$ вершинах имеет $n-1$ ребро. Таким образом, минимальное количество рёбер для связного графа на 20 вершинах составляет $20-1 = 19$ рёбер.

2. Максимальное количество рёбер:

   • Максимальное количество рёбер достигается в случае полного графа. Полный граф на $n$ вершинах имеет $\frac{n(n-1)}{2}$ рёбер. Для связного графа на 20 вершинах максимальное количество рёбер составляет $\frac{20 \cdot 19}{2} = 190$ рёбер.

Итак, минимальное количество рёбер для связного графа на 20 вершинах - 19 рёбер, а максимальное количество рёбер - 190 рёбер.