Просмотр исходного текста страницы Hardprob/Minimum Network Inhibition On Planar Graphs

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Граф <em>G=(V,E)</em>, пропускная способность ребер <em>c: E → N</em>, стоимость разрушения ребра <em>d: E → N</em>, и бюджет <em>B</em>.
* Найти стратегию атаки на эту сеть, т.е. функцию <m>\alpha: E → [0,1]</m>, такую, что <m>\sum_{e ∈  E}\alpha(e)d(e) ≤ B</m>.
* Минимизировать пропускную способность поврежденной сети, т.е. минимальный разрез в <em>G</em> с емкостью <m>c'(e)=\alpha(e)c(e)</m>.

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}} -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>
{{ViggoCode|node89}}
<!-- {{GDCode|ND16}} -->
<!-- * [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%A8%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D0%B0_%D0%BE_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5 Задача в википедии] -->
</small>
<!-- end -->

[[Категория:ClassicHardProblems]]