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

Упражнения. Параграф 36. Деление рациональных чисел. Глава 4. Рациональные числа - номер 1269, страница 259.

Условие.

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

Решение.

Решение 2.

Представим города и дороги в виде графа, где города являются вершинами, а дороги — рёбрами. Пусть $V$ — это множество вершин. По условию задачи, в стране 7 городов, следовательно, количество вершин в графе $|V| = 7$.

Условие о том, что каждый город соединён дорогами более чем с двумя городами, в терминах теории графов означает, что степень каждой вершины (количество рёбер, исходящих из неё) строго больше двух. Так как степень вершины является целым числом, то для любой вершины $v$ выполняется неравенство $deg(v) \ge 3$.

Задача заключается в том, чтобы доказать, что данный граф является связным. Связный граф — это граф, в котором для любых двух вершин существует путь, их соединяющий.

Будем доказывать от противного. Предположим, что граф не является связным. Это значит, что он состоит из двух или более не связанных между собой частей, называемых компонентами связности. Пусть граф состоит из $k$ компонент связности, где $k \ge 2$.

Рассмотрим произвольную компоненту связности. Пусть она состоит из $n$ вершин. Возьмём любую вершину $v$ из этой компоненты. По определению, все рёбра, инцидентные этой вершине, соединяют её только с другими вершинами из той же самой компоненты. Максимальное число вершин, с которыми может быть связана вершина $v$ в этой компоненте, равно $n-1$ (все остальные вершины компоненты). Таким образом, для любой вершины $v$ её степень не может превышать $n-1$: $deg(v) \le n-1$.

С другой стороны, по условию задачи мы знаем, что $deg(v) \ge 3$. Объединяя эти два неравенства, получаем: $3 \le deg(v) \le n-1$. Из этого следует, что $3 \le n-1$, что эквивалентно $n \ge 4$.

Это означает, что любая компонента связности в нашем графе должна содержать не менее 4 вершин.

Так как мы предположили, что граф несвязный, он должен иметь как минимум две компоненты связности. Обозначим число вершин в первой компоненте как $n_1$, а во второй — как $n_2$. Согласно нашему выводу, $n_1 \ge 4$ и $n_2 \ge 4$.

Тогда общее число вершин в графе $|V|$ должно быть не меньше суммы вершин в этих двух компонентах: $|V| \ge n_1 + n_2 \ge 4 + 4 = 8$.

Мы получили, что общее число городов должно быть не менее 8. Однако по условию в стране всего 7 городов ($|V|=7$). Это приводит нас к противоречию, так как $7 \ge 8$ — ложное утверждение.

Противоречие возникло из-за нашего первоначального предположения о том, что граф несвязный. Следовательно, это предположение неверно, и граф должен быть связным.

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