№4. В школьном лагере пять друзей: Коля, Оля, Петя, Света и Толя. Каждый вечер они записывают, с кем из других ребят они подружились за день. К концу недели выяснилось, что: Коля дружит с Олей и Петей Оля дружит с Колей, Петей и Светой Петя дружит с Колей, Олей и Светой Света дружит с Олей, Петей и Толей Толя дружит только со Светой а) Нарисуйте граф дружбы (вершины — имена людей, рёбра — дружба между ними). ли обойти всех друзей так, чтобы пройти по каждой дружбе ровно один раз,

Решение:

а) Граф дружбы:

Вершины графа: Коля (К), Оля (О), Петя (П), Света (С), Толя (Т).

Ребра (дружба):

• Коля - Оля
• Коля - Петя
• Оля - Петя
• Оля - Света
• Петя - Света
• Света - Толя

Визуализация графа:

Представим вершины как точки. Ребра — линии, соединяющие эти точки.

       К -- О
       |  / |
       | /  |
       П -- С -- Т

Объяснение:

• Коля связан с Олей и Петей.
• Оля связана с Колей, Петей и Светой.
• Петя связан с Колей, Олей и Светой.
• Света связана с Олей, Петей и Толей.
• Толя связан только со Светой.

б) Возможность обойти все дружбы ровно один раз:

Это задача на поиск Эйлерова пути или Эйлерова цикла в графе.

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

Проверим степени вершин:

• Степень Коли (К): 2 (связан с Олей и Петей)
• Степень Оли (О): 3 (связана с Колей, Петей, Светой)
• Степень Пети (П): 3 (связан с Колей, Олей, Светой)
• Степень Светы (С): 3 (связана с Олей, Петей, Толей)
• Степень Толи (Т): 1 (связан только со Светой)

В нашем графе есть четыре вершины с нечетной степенью (Оля, Петя, Света, Толя). Следовательно, ни Эйлеров цикл, ни Эйлеров путь (который требует ровно две вершины с нечетной степенью) не существуют.

Вывод: Обойти всех друзей так, чтобы пройти по каждой дружбе ровно один раз, невозможно.

Ответ:

а) Граф нарисован выше.

б) Нет, невозможно.