Рассмотрим следующую проблему:
Вход: простой (неориентированный) граф .
Вопрос: существует ли ориентация удовлетворяющая свойству того, что для каждого существует не более одного (направленного) - шага?
Это может быть эквивалентно сформулировано как:
Вход: простой (неориентированный) граф .
Вопрос: существует ли ациклическая ориентация удовлетворяющая свойству того, что для каждого существует не более одного (направленного) - пути?
Для какого класса графиков ответ «да»? Можно ли решить эту проблему за полиномиальное время?
Некоторые наблюдения:
- Если график является двудольным, то ответ «да».
- Если график имеет треугольник, то ответ «нет».
Первое наблюдение следует, ориентируя края от одного раздела к другому. Второе наблюдение легко проверить. Это привело меня к двум неверным догадкам:
- Ответ «да», если и только если график является двудольным. (контрпример: 5-тактный)
- Ответ «да» тогда и только тогда, когда граф не содержит треугольников (контрпример: декартово произведение ребра с 5-циклом)
источник