Номер 5, страница 87, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

5 Может ли в цикле рёбер быть меньше, чем вершин?

5 Нет, в цикле не может быть рёбер меньше, чем вершин. В любом цикле количество рёбер в точности равно количеству вершин.

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

Представим цикл, содержащий $n$ вершин. Обозначим эти вершины в порядке их следования в цикле: $v_1, v_2, \dots, v_n$.

Чтобы соединить эти вершины в последовательную цепь (простой путь), необходимо ребро между $v_1$ и $v_2$, затем между $v_2$ и $v_3$, и так далее, вплоть до ребра между $v_{n-1}$ и $v_n$. Такой путь, проходящий через $n$ вершин, будет состоять из $n-1$ рёбер.

Однако эта структура ещё не является циклом, так как она не замкнута. Чтобы замкнуть путь и образовать цикл, необходимо добавить ещё одно ребро, которое соединит последнюю вершину пути ($v_n$) с первой ($v_1$).

Таким образом, общее количество рёбер в цикле, который проходит через $n$ вершин, будет равно сумме рёбер в исходном пути и замыкающего ребра: $(n-1) + 1 = n$.

Получается, что для любого цикла с количеством вершин $V$ количество рёбер $E$ будет равно $V$. Математически это записывается как $E = V$.

Следовательно, ситуация, в которой количество рёбер меньше количества вершин ($E < V$), в цикле невозможна.

Примеры:

• Простейший цикл в простом графе — это треугольник. Он имеет 3 вершины и 3 ребра ($V=3, E=3$).
• Цикл из четырёх вершин (квадрат) имеет 4 вершины и 4 ребра ($V=4, E=4$).
• В общем виде, цикл $C_k$ имеет $k$ вершин и $k$ рёбер.

Ответ: Нет, не может. В любом цикле количество рёбер всегда равно количеству вершин.