Тараканы Аркадий и Иннокентий - соседи, они живут на поверхности куба и могут ползать только по его ребрам. Аркадий и Иннокентий поссорились и теперь ни один из них не хочет ползать по тем же ребрам, что и его сосед. Могут ли они разделить между собой ребра куба так, чтобы каждый ползал только по своим ребрам, но при этом мог добраться в любую вершину куба?
Для решения этой задачи мы можем использовать понятие графов. Куб можно представить как граф, где вершины - это углы куба, а ребра - это соединения между этими вершинами.
Структура куба: Куб имеет 8 вершин и 12 рёбер. Каждая вершина соединена с 3 другими вершинами.
Проблема разделения рёбер: Нам нужно разделить 12 рёбер между двумя тараканами так, чтобы каждый из них мог добраться до любой вершины, но при этом они не могли использовать одни и те же рёбра.
Проверка связности: Чтобы каждый таракан мог добраться до любой вершины, граф, состоящий из рёбер, которые он использует, должен...