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

Решение:

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

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

Ответ: 0.