Вопрос:

б) Можно ли обойти всех друзей так, чтобы пройти по каждой дружбе ровно один раз, начав с Толи?

Смотреть решения всех заданий с листа

Ответ:

Эта задача сводится к поиску Эйлерова пути в графе дружбы.

Правила для Эйлерова пути:

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

Определим степени вершин (количество друзей у каждого):

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

У нас четыре вершины с нечетной степенью (Толя, Света, Оля, Петя).

Вывод:

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

Ответ: Нет, нельзя.

ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие