FasterHarder:
это, очевидно, что ложь
________________.png (, : 81)
----------------------------------------------------
в итоге, еще подумав над раскраской начал осознавать, что здесь все гораздо и гораздо и гораздо сложнее, это я за себя говорю)) + сформулировать правила раскраски - проблемно...

ласт попытка сделать некие правила, хотя ни в одном из них я уже не уверен:
1. все тупики красные по дефалту и они являются эпицентрами начала движения по вершинам орграфа (дуги инвентированы)
2. зеленую порождает красная
3. красную порождает зеленая
4. красная вершина должна иметь только зеленых соседей. ИСКЛЮЧЕНИЕ: если есть хотя бы один красный сосед, то у этого красного соседа в свою очередь все соседи должны быть красными. Но это невозможно, чтобы у красного все соседи были красными), поэтому, красная вершина должна иметь ТОЛЬКО зеленых соседей - я не уверен в этом на 100%, не знаю...
5. зеленая вершина должна иметь хотя бы одного красного соседа (ИСКЛЮЧЕНИЕ: если все соседи зеленые, то у любого из этих зеленых соседей тоже все соседи должны быть зелеными, но это вроде тоже невозможно - не уверен на 100%, не знаю...)
не уверен, но вроде в п4 и п5 исключения можно отбросить. не знаю
и т.д.

ну и главная проблема - порядок обхода вершин, хотя это не должно влиять, а по факту влияет. Картинка чуть выше. Если сделать обход чуть по-другому, то вершина №1 станет красной и это уже будет правильно.

зы: уже нет абсолютно никакой уверенности, что задачу эту можно решить именно подобной раскраской и ведь выше было замечено, что здесь полный перебор (класс NP), хотя я не уверен, что я правильно понял про какой перебор там идет речь - слишком поверхностно все было написано. 1ая мысль, которая пришла в ум - был полный перебор - не удивлюсь, что в конечном итоге все к нему и сведется, т к раскраской эта задача НЕ решается))

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845535