Задачи и упражнения

• 1. На плоскости дано несколько окружностей, составляющих связную фигуру. Докажите, что эту фигуру можно нарисовать одним росчерком. Будет ли уникурсалыюй связная плоская кривая, являющаяся объединением конечного числа простых замкнутых линий?
• 2. Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?
• 3. Некоторый граф был начерчен одним росчерком, при этом в вершине А карандаш побывал трижды. Определите степень вершины А, если при вычерчивании графа движение карандаша:
  • а) не с нее начали и не на ней закончили;
  • б) не с нее начали, но на ней закончили;
  • в) с нее начали, но не на ней закончили;
  • г) с нее начали и на ней закончили?
• 4. Можно ли привязать к гвоздям А, В, С, D, Е и F веревку так, как показано на рис. 50, не разрезая ее на части и не сдваивая?

Рис. 50 Рис. 51

• 5. Можно ли прогуляться по парку и его окрестностям (см. рис. 51) так, чтобы перелезть через каждый забор ровно один раз?
• 6. Как известно, существует ровно пять типов правильных многогранников (Платоновых тел): тетраэдр, куб, октаэдр, додекаэдр и икосаэдр. Графы, образованные вершинами и ребрами этих многогранников, называются Платоновыми графами (примеры их геометрических реализаций представлены на рис. 52−56). Какие из платановых графов являются уникурсальными? Сколько росчерков требуется для изображения каждого из этих графов? Нарисуйте их, используя минимальное число росчерков.

Рис. 53

Рис. 54

Рис. 52

Рис. 55.

Рис. 56

7. Перечислите все полные графы, являющиеся уникурсальными.

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

Можно ли эту решетку составить.

• а) из 5 ломаных длины 8;
• б) из 8 ломаных длины 5? Рис. 57
• 10. Докажите, что любой разрез графа, являющегося эйлеровым циклом, содержит по крайней мере два ребра и что он обязательно состоит из четного числа ребер.