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

Решение:

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

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

Ответ: 1