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}}}} -->
-* Граф <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>, т.е. две последовательности вершин <m>u_1,u_2,…,u_m</m> и <m>v_1,v_2,…,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,…,u_m,v_1,v_2,…,v_n\}\vert=m+n</m>
 ** <m>(s,u_1) ∈ E</m>