Намиране на минимален набор от върхове, които отговарят на дадените ограничения

Забележка: няма нужда от официално доказателство или нещо подобно, само общата идея на алгоритъма и аз лично ще навляза по-дълбоко.

При даден насочен график: G(V,E), искам да намеря най-малкия набор от върхове T, така че за всеки връх t в T да не съществуват следните ръбове: {(t,v) | for every v outside t} в O(V+E)

С други думи, на t е позволено да получава ръбове от върхове извън T, но не и да изпраща.

(Можете да го демонстрирате като телефонно обаждане, при което е позволено да ми се обаждат отвън и е безплатно, но не е позволено да им се обаждам от моя страна)


Видях, че този проблем е толкова близък или подобен на намирането на всички силно свързани компоненти (scc) в насочена графика, чиято времева сложност е O(V+E), и мисля да изградя нова графика и да стартирам този алгоритъм, но не съм напълно сигурен в това.


person Community    schedule 08.05.2021    source източник
comment
дали въпросът ми е формулиран ясно, не получавам никакви коментари или отговори, бих искал да знам какъв е проблемът   -  person    schedule 08.05.2021
comment
Заглавието не отговаря на описанието в основната част на въпроса. По-конкретно, изложението на проблема, дадено в тялото, не изисква T да бъде силно свързан компонент.   -  person user3386109    schedule 08.05.2021
comment
@user3386109 можеш ли да ми помогнеш да избера по-добро заглавие, освен това знам, че не се изисква T да е силно свързан компонент, но казах, че е почти същото (като половината силно свързан компонент), така че съм сигурен, че по някакъв начин можем да използваме алгоритъма за да намерите SCC на някаква редактирана графика   -  person    schedule 08.05.2021
comment
Може би е най-добре да запазите заглавието неясно и да оставите тялото да попълни подробностите. Нещо като намиране на минимален набор от върхове, които отговарят на дадените ограничения.   -  person user3386109    schedule 08.05.2021
comment
Най-малкото такова T е празното множество. (Мисля, че има други ограничения, които не сте описали?)   -  person j_random_hacker    schedule 09.05.2021


Отговори (1)


Основната идея е да се свие всеки силно свързан компонент (SCC) на G в един връх, като същевременно се запази оценка за това колко върха са били свити, за да се създаде всеки връх в свитата графика (кондензация на G). Получената графа е насочена ациклична графа. Отговорът е върхът с по-нисък резултат сред тези с изходяща степен, равна на 0.

Структурата на отговора е обединение на силно свързани компоненти поради ограничението върху ръбовете и можете да докажете, че има само SCC, включен в отговора поради ограничението за мин.

person Eloy Pérez Torres    schedule 08.05.2021
comment
Здравейте, идеята ви няма да работи, тъй като отговорът не е непременно силно свързан компонент. (ръбовете могат да идват извън SCC, което противоречи на определението за SCC) - person ; 08.05.2021
comment
@john Връх на силно свързан компонент може да има входящи x или изходящи ръбове към върхове на други силно свързани компоненти. Например: G({1, 2, 3, 4}, {‹1, 2›, ‹2, 1›, ‹3, 1›, ‹2, 4›}), има 3 SCC ({1, 2 }. {3}. {4}), отговорът на проблема е {4} и има край, който идва извън такъв SCC (‹2, 4›). - person Eloy Pérez Torres; 09.05.2021