Очевидно, если граф состоит из многих компонент связности, то и в каждой компоненте связности будет выполняться условие отсутствия цеклов нечетной длины. Если удасться доказать, что каждая компонента связности - двудольный граф, то это будет верно и для всего графа. Поэтому будем считать, что граф связный.
Возьмем произвольную вершину G в графе. Пусть класс X - множество вершин, до которых минимальное расстояние до G четное, Y - до которых расстояние нечетное.
Докажем, что соседние вершины в графе принадлежат разным классам. Рассмотрим расстояния от G до двух соседних вершин U и V. Очевидно, они могут отличаться не более, чем на 1. Если они отличаются на 1, всё ок, U и V принадлежат разным классам. Если они равны, рассмотрим цикл, состоящий из наименьшего пути из G в U (некоторой длины n), ребра U-V и наименьшего пути из V в G (по предположению тоже длины n). Тогда цикл G - ... - U - V - ... - G длины 2n + 1 - нечетной, что запрещено по условию. Значит, любые соседние вершины принадлежат разным классам, что и требовалось доказать.
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку
