Забележка: няма нужда от официално доказателство или нещо подобно, само общата идея на алгоритъма и аз лично ще навляза по-дълбоко.
При даден насочен график: G(V,E)
, искам да намеря най-малкия набор от върхове T
, така че за всеки връх t
в T
да не съществуват следните ръбове: {(t,v) | for every v outside t}
в O(V+E)
С други думи, на t
е позволено да получава ръбове от върхове извън T
, но не и да изпраща.
(Можете да го демонстрирате като телефонно обаждане, при което е позволено да ми се обаждат отвън и е безплатно, но не е позволено да им се обаждам от моя страна)
Видях, че този проблем е толкова близък или подобен на намирането на всички силно свързани компоненти (scc) в насочена графика, чиято времева сложност е O(V+E)
, и мисля да изградя нова графика и да стартирам този алгоритъм, но не съм напълно сигурен в това.
T
да бъде силно свързан компонент. - person user3386109   schedule 08.05.2021T
е празното множество. (Мисля, че има други ограничения, които не сте описали?) - person j_random_hacker   schedule 09.05.2021