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