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

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

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

1. Если "цепь" — это простая цепь (или путь)

Простая цепь — это такая последовательность вершин, в которой ни одна вершина не повторяется. Пусть в такой цепи $n$ вершин: $v_1, v_2, \dots, v_n$. Эти вершины последовательно соединены рёбрами $(v_1, v_2), (v_2, v_3), \dots, (v_{n-1}, v_n)$.

В этом случае количество вершин равно $n$, а количество рёбер $m$ всегда будет на единицу меньше:

$m = n - 1$

Например, в цепи $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4$ 4 вершины и 3 ребра. Здесь количество рёбер меньше количества вершин. При таком определении ответ на вопрос — нет.

2. Если в цепи разрешены повторения вершин (маршрут)

Если рассматривать цепь как маршрут, в котором можно возвращаться в уже пройденные вершины, то количество рёбер может превысить количество вершин. Это происходит, когда маршрут содержит один или несколько циклов.

Рассмотрим конкретный пример. Пусть есть граф в виде треугольника с вершинами $A, B, C$.

Построим в этом графе цепь (маршрут), которая начинается в вершине $A$, проходит по кругу и делает ещё один шаг:

$A \rightarrow B \rightarrow C \rightarrow A \rightarrow B$

Подсчитаем количество уникальных вершин в этой цепи. Это вершины $A, B, C$. Их общее количество $n=3$.

Теперь подсчитаем количество рёбер в этой цепи (то есть количество "шагов"). Маршрут состоит из 4 рёбер: $(A, B)$, $(B, C)$, $(C, A)$ и снова $(A, B)$. Таким образом, количество рёбер $m=4$.

В данном примере мы имеем $m = 4$ и $n = 3$, что удовлетворяет условию $m > n$.

Ответ: Да, в цепи может быть больше рёбер, чем вершин, если под цепью понимать маршрут, в котором допускается повторное прохождение вершин.