Рисунок 32 135 Укажите, какие графы на рисунке 32 содержат цив 136 Изобразите какой-нибудь граф, у которого: а) три цикла длин 3, 4 и 5; б) два цикла длины 4 и один цикл длины 6. 137 Изобразите два графа с шестью вершинами степен гой - нет. 138 В деревне 9 домов. Соседними будем считать учас забор. Известно, что у Петра соседи Иван и Ав и Сергею, Виктор - Дмитрию и Никите, а такж ний с Никитой, Иван с Сергеем, Евгений с Дми и больше соседей в деревне нет. Может ли Пётр, седних участков, пробраться на участок к Никите? 139 в Солнечной

Этот граф может быть создан путем объединения трех циклов, где каждый цикл имеет указанную длину. Например, можно начать с цикла длины 3 (треугольник), затем добавить вершину и ребра, чтобы сформировать цикл длины 4, и еще одну вершину и ребра для цикла длины 5.

Аналогично, можно создать два цикла длины 4, имеющие общие вершины, и затем добавить вершины и ребра для формирования цикла длины 6.

• Первый граф: Каждая вершина соединена как минимум с двумя другими вершинами, образуя, например, два треугольника, соединенных ребром.
• Второй граф: Все вершины соединены в цикл длины 6, где каждая вершина имеет степень 2.

Дано: 9 домов в деревне. Соседи разделены забором.

• Петр соседствует с Иваном и Сергеем.
• Виктор соседствует с Дмитрием и Никитой, а также с Никитой.
• Иван с Сергеем.
• Евгений с Дмитрием.
• Больше соседей нет.

Вопрос: Может ли Петр пробраться на участок к Никите?

Для ответа на этот вопрос нужно понять, как связаны дома между собой. Если нет общей цепочки соседства от Петра к Никите, то Петр не сможет попасть на участок Никиты, не нарушая границ соседних участков.

Из условия задачи можно построить граф соседства:

• Петр - Иван, Сергей
• Иван - Сергей
• Виктор - Дмитрий, Никита
• Евгений - Дмитрий

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