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

Глава 2. Целые выражения. §5. Степень с натуральным показателем - номер 203, страница 43.

Условие.

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

Решение 1.

Решение 2.

Решение 3.

Решение 4.

Решение 5.

Решение 6.

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

Вершина, удаление которой из связного графа делает его несвязным, называется точкой сочленения. Таким образом, задача сводится к доказательству того, что в любом связном графе с числом вершин $n \ge 2$ существует хотя бы одна вершина, не являющаяся точкой сочленения.

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

Чтобы доказать, что граф $G-v_k$ связен, нужно показать, что для любых двух различных станций $u$ и $w$, оставшихся после закрытия $v_k$ (то есть $u, w \in V \setminus \{v_k\}$), существует маршрут между ними, не проходящий через $v_k$.

Поскольку исходный граф $G$ связен, между $u$ и $w$ существует некоторый путь $\pi$. Возможны два случая. Первый случай: путь $\pi$ не проходит через вершину $v_k$. В этом случае тот же самый путь существует и в графе $G-v_k$, а значит, станции $u$ и $w$ соединены маршрутом.

Второй случай: путь $\pi$ проходит через вершину $v_k$. Пусть $a$ — вершина, из которой путь $\pi$ приходит в $v_k$, а $b$ — вершина, в которую путь $\pi$ уходит из $v_k$. Таким образом, $a$ и $b$ — соседи вершины $v_k$. Все соседи вершины $v_k$ должны лежать на пути $P$. Действительно, если бы у $v_k$ был сосед $z$, не лежащий на пути $P$, то мы могли бы построить новый простой путь $(v_1, v_2, \dots, v_k, z)$. Этот путь содержит $k+1$ вершину, что противоречит предположению о том, что $P$ — самый длинный простой путь в графе. Следовательно, все соседи $v_k$, включая $a$ и $b$, находятся среди вершин $\{v_1, v_2, \dots, v_{k-1}\}$.

Поскольку $a$ и $b$ обе лежат на пути $P$, между ними существует путь, состоящий только из вершин этого пути (и не содержащий $v_k$). Этот путь — просто участок пути $P$ между $a$ и $b$. Теперь мы можем построить новый маршрут от $u$ до $w$, обходящий станцию $v_k$: сначала двигаемся от $u$ до $a$ по части исходного пути $\pi$, затем от $a$ до $b$ по участку пути $P$, и, наконец, от $b$ до $w$ по другой части исходного пути $\pi$. Этот новый маршрут соединяет $u$ и $w$ и не использует вершину $v_k$. Следовательно, он целиком лежит в графе $G-v_k$.

Таким образом, мы показали, что для любой пары станций $u, w$ в сети, оставшейся после закрытия станции $v_k$, существует соединяющий их маршрут. Это означает, что сеть метро остаётся связной. Следовательно, всегда существует станция (например, конечная станция самого длинного маршрута), которую можно закрыть, не нарушая общую связность системы.

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