Hardprob/Minimum Maximum Disjoint Connecting Paths — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена PCRE <m>(\w)_(\w),\s*(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, \3<sub>\4</sub>, …, \5<sub>\6</sub></em>)
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
−
<!-- start -->
+
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
−
* Граф <m>G=\left(V,E\right)</m>, пути на ребрах <m>l:E \rightarrow 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>, такие что  
+
* Граф <em>G=(V,E)</em>, пути на ребрах <em>l: E → N</em>, и некоторая пара вершин <em>s,t</em> в <em>V</em>. Найти два непересекающихся по вершинам пути в <em>G</em>, соединающих <em>s</em> и <em>t</em>, т.е. две последовательности вершин <em>u<sub>1</sub>, u<sub>2</sub>, …, u<sub>m</sub></em> и <em>v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub></em>, такие что  
−
** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m>
+
** <m>\vert\{u_1,u_2,…,u_m,v_1,v_2,…,v_n\}\vert=m+n</m>
 
** <m>(s,u_1) ∈ E</m>
 
** <m>(s,u_1) ∈ E</m>
 
** <m>(s,v_1) ∈ E</m>
 
** <m>(s,v_1) ∈ E</m>
Строка 15: Строка 15:
 
----
 
----
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 +
<!-- * {{has-testdata-and-visualization}} -->
 +
<!-- * {{has-pyomo-model}} -->
 +
<!-- * {{has-npc-reduction}} -->
 +
<!-- * {{add-random-fuzzing-tests}} -->
 
----
 
----
 
<small>
 
<small>

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

  • Граф G=(V,E), пути на ребрах l: E → N, и некоторая пара вершин s,t в V. Найти два непересекающихся по вершинам пути в G, соединающих s и t, т.е. две последовательности вершин u1, u2, …, um и v1, v2, …, vn, такие что
  • Минимизировать максимальную длину этих путей, т.е.

Задача в лаб22 (рид-онли просмотр)

Источник — «https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&oldid=25324»