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

136 Изобразите какой-нибудь граф, у которого:

a) три цикла длин 3, 4 и 5;

б) два цикла длины 4 и один цикл длины 6.

а) три цикла длин 3, 4 и 5;

Для построения такого графа можно взять за основу цикл длины 5 и добавить одно ребро (хорду). Пусть граф $G$ имеет 5 вершин $V = \{V_1, V_2, V_3, V_4, V_5\}$.

Соединим вершины так, чтобы они образовывали цикл длины 5 (пятиугольник): ребра $(V_1, V_2), (V_2, V_3), (V_3, V_4), (V_4, V_5), (V_5, V_1)$. Этот цикл и будет нашим циклом длины 5.

Теперь добавим ребро $(V_1, V_3)$. Это ребро создает два новых цикла:

• Цикл $V_1-V_2-V_3-V_1$ имеет длину 3.
• Цикл $V_1-V_3-V_4-V_5-V_1$ имеет длину 4.

Исходный цикл длины 5 ($V_1-V_2-V_3-V_4-V_5-V_1$) также сохраняется, так как все его ребра присутствуют в графе.

Таким образом, полученный граф имеет 5 вершин, 6 ребер и содержит циклы длин 3, 4 и 5.

Циклы в данном графе:

• Длины 3: $V_1-V_2-V_3-V_1$
• Длины 4: $V_1-V_3-V_4-V_5-V_1$
• Длины 5: $V_1-V_2-V_3-V_4-V_5-V_1$

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

б) два цикла длины 4 и один цикл длины 6.

Для построения такого графа возьмем за основу цикл длины 6. Пусть граф $G$ имеет 6 вершин $V = \{V_1, V_2, V_3, V_4, V_5, V_6\}$.

Соединим вершины так, чтобы они образовывали цикл длины 6 (шестиугольник): ребра $(V_1, V_2), (V_2, V_3), (V_3, V_4), (V_4, V_5), (V_5, V_6), (V_6, V_1)$. Этот цикл будет искомым циклом длины 6.

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

• Первый четырехугольник образует цикл $V_1-V_2-V_3-V_4-V_1$. Его длина равна 4.
• Второй четырехугольник образует цикл $V_1-V_4-V_5-V_6-V_1$. Его длина также равна 4.

Исходный цикл длины 6 ($V_1-V_2-V_3-V_4-V_5-V_6-V_1$) также существует в графе.

В итоге мы получили граф с 6 вершинами, 7 ребрами, который удовлетворяет всем условиям задачи.

Циклы в данном графе:

• Длины 4 (первый): $V_1-V_2-V_3-V_4-V_1$
• Длины 4 (второй): $V_1-V_4-V_5-V_6-V_1$
• Длины 6: $V_1-V_2-V_3-V_4-V_5-V_6-V_1$

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