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

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

Граф G=(V,E), пути на ребрах l: E → N, и некоторая пара вершин s,t в V. Найти два непересекающихся по вершинам пути в G, соединающих s и t, т.е. две последовательности вершин u₁, u₂, …, u_m и v₁, v₂, …, v_n, такие что

@@ Строка 1: / Строка 1: @@
 <!-- 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,v_1) ∈ E</m>
@@ Строка 15: / Строка 15: @@
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
+<!-- * {{has-testdata-and-visualization}} -->
+<!-- * {{has-pyomo-model}} -->
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>