Олимпиадная задача по теории графов — рисование связного графа с 2n не
Докажите, что связный граф с 2n нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно n –1 раз и не проводя никакое ребро дважды.
Разобрать решение
Разобьём нечётные вершины на пары и каждую пару соединим новым ребром. Согласно задаче 130806 полученный граф можно обойти по циклу. Удалив новые рёбра, мы разобьём цикл на n частей.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.