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

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

Рисунок 21

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

Исходный граф является полным двудольным графом, который обозначается как $K_{2,3}$. Он имеет 5 вершин, разделённых на две доли. В одной доле 2 вершины, в другой — 3. Каждая вершина из первой доли соединена с каждой вершиной из второй. Такой граф является планарным, что и позволяет изобразить его на плоскости без пересечений рёбер.

Решение:

Чтобы устранить пересечения, можно расположить вершины, принадлежащие разным долям, определённым образом.

1. Возьмём 3 вершины, которые в исходном рисунке находятся справа, и расположим их в один ряд по горизонтали.
2. Оставшиеся 2 вершины (те, что в исходном рисунке слева) разместим так: одну — над центральной вершиной горизонтального ряда, а другую — под ней.
3. Теперь соединим верхнюю вершину с каждой из трёх вершин в ряду.
4. Аналогично соединим нижнюю вершину с каждой из трёх вершин в ряду.

При таком расположении вершин ни одно ребро не будет пересекать другое.

Ответ:

Изображение графа без пересечения рёбер представлено ниже.

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