Hardprob/Minimum Point-To-Point Connection — различия между версиями

Текущая версия на 22:45, 17 апреля 2023

Граф G=(V,E), веса на ребрах w: E → N и множество стартовых и финишных точек.
Найти связь точка-точка, т.е. подмножество ребер E' ⊆ E, таких, что для каждой пары старт-финиш, можно проложить путь в E'.
Минимизировать вес этой связи, .

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Граф <m>G=\left(V,E\right)</m>, веса на ребрах <m>w : E \rightarrow N</m> и множество стартовых <m>S=\{s_1, \ldots, s_p\}</m> и финишных <m>D=\{d_1,\ldots,d_p\}</m> точек.
+* Граф <em>G=(V,E)</em>, веса на ребрах <em>w: E → N</em> и множество стартовых <m>S=\{s_1, …, s_p\}</m> и финишных <m>D=\{d_1,…,d_p\}</m> точек.
-* Найти связь точка-точка, т.е. подмножество ребер <m>E'\subseteq E</m>, таких, что для каждой пары старт-финиш, можно проложить путь в <em>E'</em>.
+* Найти связь точка-точка, т.е. подмножество ребер <em>E' ⊆ E</em>, таких, что для каждой пары старт-финиш, можно проложить путь в <em>E'</em>.
-* Минимизировать вес этой связи, <m>\sum_{e \in E'}w(e)$</m>.
+* Минимизировать вес этой связи, <m>\sum_{e ∈  E'}w(e)$</m>.
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
+<!-- * {{has-testdata-and-visualization}} -->
+<!-- * {{has-pyomo-model}} -->
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>