Задача. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз? Ответ поясните с помощью теоремы Эйлера.

Решение:

Чтобы ответить на этот вопрос, воспользуемся теоремой Эйлера о графах. Теорема гласит, что граф можно нарисовать, не отрывая карандаша от бумаги и проходя каждое ребро ровно один раз, если выполнены два условия:

• 1. Все вершины графа имеют четную степень (количество ребер, выходящих из вершины).
• 2. Или ровно две вершины имеют нечетную степень, а все остальные — четную.

В нашем случае, рассматривая представленные на рисунке графы:

1. Первый граф (звезда):

   • В этом графе 5 вершин, расположенных по кругу. Каждая из этих вершин соединена с двумя соседними по кругу и с центральной вершиной. Итого степень каждой внешней вершины равна 3 (нечетная).
   • Центральная вершина соединена со всеми 5 внешними вершинами. Её степень равна 5 (нечетная).
   • Таким образом, в этом графе все 6 вершин имеют нечетную степень (3 или 5). По теореме Эйлера, такой граф нельзя нарисовать одним росчерком.

2. Второй граф (прямоугольник с диагоналями):

   • Здесь 4 вершины, находящиеся в углах прямоугольника. Каждая вершина соединена с двумя соседними по периметру и с противоположной вершиной по диагонали. Таким образом, степень каждой вершины равна 4 (четная).
   • Так как все вершины имеют четную степень, этот граф можно нарисовать одним росчерком.

3. Третий граф (домик):

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

Ответ:

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