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

Упражнения. Параграф 40. Деление рациональных чисел. Глава 4. Рациональные числа и действия над ними - номер 1150, страница 243.

Условие.

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

Решение.

Решение 2.

Данную задачу можно смоделировать с помощью теории графов. Города будем считать вершинами графа, а дороги, соединяющие их, — рёбрами. Таким образом, мы имеем граф $G$ с $n=7$ вершинами.

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

Нам нужно доказать, что из любого города можно доехать до любого другого. Это эквивалентно тому, чтобы доказать, что граф $G$ является связным (т. е. между любыми двумя его вершинами существует путь).

Докажем это утверждение методом от противного. Предположим, что граф $G$ не является связным (является несвязным).

Несвязный граф по определению состоит как минимум из двух отдельных частей, не соединённых рёбрами. Эти части называются компонентами связности. Пусть наш граф $G$ состоит из двух или более компонент связности.

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

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

Отсюда следует, что $3 \le k-1$, что равносильно $k \ge 4$.

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

По нашему предположению, граф несвязный, значит, он имеет как минимум две компоненты связности. Пусть первая компонента содержит $k_1$ вершин, а вторая — $k_2$ вершин. Мы доказали, что размер каждой компоненты не может быть меньше 4, следовательно: $k_1 \ge 4$ $k_2 \ge 4$

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

Итак, мы пришли к выводу, что если граф несвязный, то в нём должно быть не менее 8 вершин. Однако по условию задачи в стране Севентаун всего 7 городов, то есть $n=7$.

Полученное противоречие ($7 \ge 8$ — неверно) означает, что наше первоначальное предположение о том, что граф несвязный, было ошибочным. Следовательно, граф является связным. А это и означает, что из любого города можно доехать до любого другого.

Доказательство

Представим города в виде вершин графа, а дороги — в виде рёбер. По условию, у нас есть граф с 7 вершинами, и степень каждой вершины не меньше 3. Нужно доказать, что граф связный.

Предположим противное: граф не является связным. Тогда он распадается как минимум на две компоненты связности. Пусть в одной из компонент $k$ вершин. Поскольку каждая вершина этой компоненты соединена рёбрами только с вершинами той же компоненты, её степень не может быть больше $k-1$. По условию, степень каждой вершины не меньше 3, значит, $k-1 \ge 3$, откуда $k \ge 4$.

Итак, в каждой компоненте связности должно быть не менее 4 вершин. Но если в графе есть хотя бы две компоненты связности, то общее число вершин в нём должно быть не менее $4 + 4 = 8$. Это противоречит условию, так как в графе всего 7 вершин. Следовательно, наше предположение неверно, и граф является связным. Это означает, что из любого города можно добраться до любого другого.

Ответ: Утверждение доказано.