Просмотр исходного текста страницы Hardprob/Minimum Maximum Disjoint Connecting Paths

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Граф <em>G=(V,E)</em>, пути на ребрах <m>l:E →  N</m>, и некоторая пара вершин <em>s,t</em> в <em>V</em>. Найти два непересекающихся по вершинам пути в <em>G</em>, соединающих <em>s</em> и <em>t</em>, т.е. две последовательности вершин <m>u_1,u_2,\ldots,u_m</m> и <m>v_1,v_2,\ldots,v_n</m>, такие что 
** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m>
** <m>(s,u_1) ∈ E</m>
** <m>(s,v_1) ∈ E</m>
** <m>(u_m,t) ∈ E</m>
** <m>(v_n,t) ∈ E</m>
** <m>∀i (u_i ,u_{i+1}) ∈ E</m>
** <m>∀i (v_i ,v_{i+1}) ∈ E</m>

* Минимизировать максимальную длину этих путей, т.е. 
<m>\max(l(s,u_1)+\sum_{i=1}^{m-1} l(u_i,u_{i+1})+l(u_m,t),
l(s,v_1)+\sum_{i=1}^{n-1} l(v_i,v_{i+1})+l(v_n,t))</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}} -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>
{{ViggoCode|node123}}
{{GDCode|ND41}}
<!-- * [ Задача в википедии] -->
</small>
<!-- end -->

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