У нас есть ориентированный циклический граф с некоторыми ребрами, обусловленными двоичной переменной, и нам нужно найти присвоение переменной, которое приведет к наибольшему размеру графа (сумме размеров посещаемых узлов).
- Может быть
k таких переменных, и одна и та же переменная может появляться в графике несколько раз.
- Переменные не зависят друг от друга.
- Каковы возможные пути эффективного решения этой проблемы?
- От чего зависит сложность?
- Каким будет эффективный способ выборки размеров графа из пространства всех возможных назначений переменных? (с целью понимания распределения)
- Какие известные алгоритмы / концепции теории графов могут быть связаны с этой проблемой?
Прилагается пример графика и результирующего дерева решений, которое перечисляет все возможности. Числа представляют размер узла. Максимальное назначение в этом случае - [A = false, B = false, C = true], которое включает в себя узлы 1,2,3,5,6,7,8,9 для общего размера 41.
