Вопрос:

2. Сколько из изображенных на рисунке графов можно нарисовать, не отрывая карандаша от бумаги?

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

Ответ:

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

Рассмотрим каждый граф:

  • Первый граф имеет все вершины четной степени (степень каждой вершины равна 2), следовательно, его можно нарисовать, не отрывая карандаша от бумаги.
  • Второй граф имеет 4 вершины нечетной степени (степень каждой вершины равна 3), следовательно, его нельзя нарисовать, не отрывая карандаша от бумаги.
  • Третий граф имеет все вершины четной степени (степень каждой вершины равна 2), следовательно, его можно нарисовать, не отрывая карандаша от бумаги.
  • Четвертый граф имеет все вершины четной степени, следовательно, его можно нарисовать, не отрывая карандаша от бумаги.
  • Пятый граф имеет 4 вершины нечетной степени, следовательно, его нельзя нарисовать, не отрывая карандаша от бумаги.

Таким образом, из изображенных графов можно нарисовать, не отрывая карандаша от бумаги, 3 графа.

Ответ: 3

ГДЗ по фото 📸

Похожие