Номер 286, страница 52 - гдз по алгебре 7 класс учебник Мерзляк, Полонский

Упражнения. Параграф 6. Степень с натуральным показателем. Глава 1. Алгебраические выражения. Уравнения с одной переменной - номер 286, страница 52.

Условие.

286. В некотором городе с любой станции метро можно проехать на любую другую станцию (возможно, с пересадками). Докажите, что существует станция, которую можно закрыть (без права проезда через неё), и при этом с любой из оставшихся станций можно будет проехать на любую другую.

Решение 2.

Решение 3.

Решение 4.

Решение 5.

Представим схему метро в виде графа $G=(V, E)$, где станции являются вершинами $V$, а перегоны между ними — ребрами $E$. Условие, что с любой станции можно доехать до любой другой, означает, что этот граф является связным. Закрытие станции эквивалентно удалению вершины из графа вместе со всеми прилегающими к ней ребрами. Нам нужно доказать, что существует такая станция (вершина), удаление которой не нарушит связность графа, то есть все оставшиеся станции по-прежнему будут образовывать единую сеть.

Рассмотрим в графе $G$ один из самых длинных простых путей. Простой путь — это путь, который не проходит через одну и ту же вершину дважды. Поскольку число станций конечно, такой самый длинный путь обязательно существует. Обозначим его как $P = (v_1, v_2, \dots, v_k)$, где $v_i$ — это станции (вершины), а $k$ — их количество в этом пути. Станции $v_1$ и $v_k$ являются конечными станциями этого пути.

Докажем, что конечная станция этого пути, например $v_1$, и является искомой станцией, которую можно закрыть. Для этого сначала покажем, что любая станция, соединенная перегоном с $v_1$, также должна находиться на пути $P$.
Предположим обратное: существует станция $u$, соединенная с $v_1$ ребром, но не принадлежащая пути $P$ (то есть $u \notin \{v_1, v_2, \dots, v_k\}$). Тогда мы можем построить новый путь, начав со станции $u$, затем переехав на $v_1$ и далее проследовав по всему пути $P$: $u, v_1, v_2, \dots, v_k$. Этот новый путь является простым (поскольку $u$ не было на $P$, а остальные вершины не повторяются) и содержит $k+1$ станцию. Его длина больше, чем у пути $P$, который содержит $k$ станций. Это противоречит нашему первоначальному выбору $P$ как самого длинного простого пути. Следовательно, наше предположение неверно, и любая станция, напрямую соединенная с $v_1$, уже является одной из станций на пути $P$, то есть принадлежит множеству $\{v_2, v_3, \dots, v_k\}$.

Теперь докажем, что если закрыть станцию $v_1$, система метро останется связной. Это означает, что для любых двух оставшихся станций $A$ и $B$ (отличных от $v_1$) по-прежнему будет существовать маршрут между ними.

Возьмем две произвольные станции $A$ и $B$ из множества оставшихся станций. Так как исходный граф был связным, в нем существовал путь между $A$ и $B$.

1. Если этот путь не проходил через станцию $v_1$, то он целиком сохранится и после ее закрытия. Следовательно, $A$ и $B$ остаются связанными.

2. Если же путь проходил через $v_1$, он имел вид: $A \to \dots \to s_1 \to v_1 \to s_2 \to \dots \to B$, где $s_1$ и $s_2$ — это станции, напрямую соединенные с $v_1$.
Как мы доказали ранее, станции $s_1$ и $s_2$ должны принадлежать пути $P$. Пусть $s_1 = v_i$ и $s_2 = v_j$ для некоторых индексов $i, j$ из множества $\{2, \dots, k\}$. Но тогда между станциями $s_1$ и $s_2$ существует другой путь, не проходящий через $v_1$: это участок исходного пути $P$ между вершинами $v_i$ и $v_j$. Мы можем заменить участок маршрута $s_1 \to v_1 \to s_2$ на путь по перегонам, составляющим путь $P$ между $s_1$ и $s_2$. Новый маршрут $A \to \dots \to s_1 \to \dots (\text{вдоль } P) \to s_2 \to \dots \to B$ не использует станцию $v_1$ и соединяет $A$ и $B$.

Таким образом, для любой пары оставшихся станций существует маршрут, не проходящий через $v_1$. Это означает, что после закрытия станции $v_1$ сеть метро остается связной. Мы доказали, что конечная станция самого длинного простого маршрута в сети метро может быть закрыта без нарушения общей связности системы. Поскольку в любой конечной связной сети метро существует хотя бы один маршрут, то существует и самый длинный, а значит, всегда найдется станция, удовлетворяющая условию задачи.

Ответ: Утверждение доказано. Существует станция, которую можно закрыть, сохранив связность сети. В качестве такой станции можно выбрать любую конечную станцию одного из самых длинных простых маршрутов в системе метро.