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

2 Может ли эйлеров граф быть несвязным?

Для ответа на этот вопрос необходимо вспомнить определения эйлерова графа и связности графа.

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

Критерий существования эйлерова цикла гласит: конечный неориентированный граф является эйлеровым тогда и только тогда, когда он связен и степень каждой его вершины чётна. На первый взгляд, требование связности в самом критерии сразу даёт отрицательный ответ на вопрос.

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

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

Предположим, что в графе $G$ есть эйлеров цикл. Этот цикл должен пройти по всем рёбрам графа $G$. Если хотя бы две компоненты, например $G_1$ и $G_2$, содержат рёбра, то эйлеров цикл невозможен. Цикл является непрерывным путем, и, пройдя по всем рёбрам в компоненте $G_1$, он не сможет "перепрыгнуть" в компоненту $G_2$, так как по определению между компонентами связности нет рёбер.

Но есть особый случай: что, если все рёбра графа $G$ содержатся только в одной его компоненте, например, в $G_1$, а все остальные компоненты ($G_2, \ldots, G_k$) состоят только из изолированных вершин (вершин без рёбер)?

В этом случае, если компонента $G_1$ сама по себе является эйлеровым графом (то есть она связна и степени всех её вершин чётны), то в ней существует эйлеров цикл. Этот цикл проходит через все рёбра компоненты $G_1$. А так как в других компонентах рёбер нет, то этот цикл по факту проходит через все рёбра всего графа $G$. Следовательно, граф $G$ является эйлеровым.

При этом, поскольку граф $G$ содержит изолированные вершины (компоненты $G_2, \ldots, G_k$), он по определению является несвязным.

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

Ответ: Да, может. Эйлеров граф может быть несвязным, если он состоит из одной компоненты связности, которая содержит все рёбра графа и является эйлеровой, и одной или нескольких компонент, представляющих собой изолированные вершины.