А) Придумать два графа, которые можно обвести одним росчерком и два – которые нельзя.

Для решения задачи о графах, которые можно или нельзя обвести одним росчерком, рассмотрим понятие "обводить граф одним росчерком". Это значит, что мы должны пройти по всем рёбрам графа, не поднимая ручку от бумаги и не проходя по одному и тому же ребру дважды. ### Условия: 1. **Граф, который можно обвести одним росчерком:** По теореме Эйлера, для того чтобы граф можно было обвести одним росчерком, он должен быть связным и должен иметь либо 0, либо 2 вершины нечётной степени. 2. **Граф, который нельзя обвести одним росчерком:** Если в графе есть более двух вершин нечётной степени или если граф разъединён (несвязный), то его нельзя обвести одним росчерком. ### Примеры: #### Графы, которые можно обвести одним росчерком: 1. **Граф с 4 вершинами и 4 рёбрами (квадрат):** - Вершины: A, B, C, D - Рёбра: AB, BC, CD, DA - Все вершины имеют чётную степень (по 2), и граф является связным. 2. **Граф с 3 вершинами (треугольник):** - Вершины: A, B, C - Рёбра: AB, BC, CA - Все вершины имеют чётную степень (по 2) и граф также связан. #### Графы, которые нельзя обвести одним росчерком: 1. **Граф с 3 вершинами, но с одной из вершин соединенной с двумя рёбрами (шапка):** - Вершины: A, B, C - Рёбра: AB, AC, BC - Вершина A - нечётная (степень 2), а B и C - чётные (степень 1). В результате, 1 вершина нечётной степени делает невозможным обвести граф одним росчерком. 2. **Граф с 4 вершинами и 5 рёбрами (одна вершина соединена с двумя):** - Вершины: A, B, C, D - Рёбра: AB, AC, AD, BC, BD - Вершины A, B и C - нечётные (степень 3), а D - чётная (степень 2). Здесь 3 вершины имеют нечётную степень, так что это также невозможно. ### Вывод Таким образом, графы могут быть классифицированы по возможности обведения одним росчерком в зависимости от степени их вершин. Считаем вершины сначала, проверяем чётность, чтобы определить, можно ли обвести граф целиком.