https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Hardprob%2FMinimum_Maximum_Disjoint_Connecting_Paths
Hardprob/Minimum Maximum Disjoint Connecting Paths - История изменений
2026-04-26T13:26:14Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=25324&oldid=prev
StasFomin: Массовая правка: замена 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>
2023-04-17T22:58:05Z
<p>Массовая правка: замена 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></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 22:58, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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>, т.е. две последовательности вершин <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">u_1</del>,<del class="diffchange diffchange-inline">u_2</del>,…,<del class="diffchange diffchange-inline">u_m</del><<del class="diffchange diffchange-inline">/</del>m> и <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">v_1</del>,<del class="diffchange diffchange-inline">v_2</del>,…,<del class="diffchange diffchange-inline">v_n</del></<del class="diffchange diffchange-inline">m</del>>, такие что  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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>, т.е. две последовательности вершин <<ins class="diffchange diffchange-inline">em>u<sub>1</sub</ins>>, <ins class="diffchange diffchange-inline">u<sub>2</sub></ins>, …, <ins class="diffchange diffchange-inline">u</ins><<ins class="diffchange diffchange-inline">sub></ins>m<ins class="diffchange diffchange-inline"></sub></em</ins>> и <<ins class="diffchange diffchange-inline">em>v<sub>1</sub</ins>>, <ins class="diffchange diffchange-inline">v<sub>2</sub></ins>, …, <ins class="diffchange diffchange-inline">v<sub>n</ins></<ins class="diffchange diffchange-inline">sub></em</ins>>, такие что  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,…,u_m,v_1,v_2,…,v_n\}\vert=m+n</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,…,u_m,v_1,v_2,…,v_n\}\vert=m+n</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=25282&oldid=prev
StasFomin: Массовая правка: замена \ldots на …
2023-04-17T22:45:07Z
<p>Массовая правка: замена \ldots на …</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 22:45, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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,<del class="diffchange diffchange-inline">\ldots</del>,u_m</m> и <m>v_1,v_2,<del class="diffchange diffchange-inline">\ldots</del>,v_n</m>, такие что  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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,<ins class="diffchange diffchange-inline">…</ins>,u_m</m> и <m>v_1,v_2,<ins class="diffchange diffchange-inline">…</ins>,v_n</m>, такие что  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,<del class="diffchange diffchange-inline">\ldots</del>,u_m,v_1,v_2,<del class="diffchange diffchange-inline">\ldots</del>,v_n\}\vert=m+n</m></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,<ins class="diffchange diffchange-inline">…</ins>,u_m,v_1,v_2,<ins class="diffchange diffchange-inline">…</ins>,v_n\}\vert=m+n</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,v_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,v_1) ∈ E</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=25187&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>(\w)\s*:\s*(\w)\s*→\s*(\w)</m> на <em>\1: \2 → \3</em>
2023-04-17T22:16:37Z
<p>Массовая правка: замена PCRE <m>(\w)\s*:\s*(\w)\s*→\s*(\w)</m> на <em>\1: \2 → \3</em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 22:16, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Граф <em>G=(V,E)</em>, пути на ребрах <<del class="diffchange diffchange-inline">m</del>>l:E → <del class="diffchange diffchange-inline"> </del>N</<del class="diffchange diffchange-inline">m</del>>, и некоторая пара вершин <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>, такие что  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Граф <em>G=(V,E)</em>, пути на ребрах <<ins class="diffchange diffchange-inline">em</ins>>l: E → N</<ins class="diffchange diffchange-inline">em</ins>>, и некоторая пара вершин <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>, такие что  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=24874&oldid=prev
StasFomin: Массовая правка: замена \rightarrow на →
2023-04-17T11:34:06Z
<p>Массовая правка: замена \rightarrow на →</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 11:34, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Граф <em>G=(V,E)</em>, пути на ребрах <m>l:E <del class="diffchange diffchange-inline">\rightarrow </del>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>, такие что  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Граф <em>G=(V,E)</em>, пути на ребрах <m>l:E <ins class="diffchange diffchange-inline">→  </ins>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>, такие что  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=24669&oldid=prev
StasFomin: Массовая правка: замена <m>G=\left(V,E\right)</m> на <em>G=(V,E)</em>
2023-04-17T05:46:26Z
<p>Массовая правка: замена <m>G=\left(V,E\right)</m> на <em>G=(V,E)</em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 05:46, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Граф <<del class="diffchange diffchange-inline">m</del>>G=<del class="diffchange diffchange-inline">\left</del>(V,E<del class="diffchange diffchange-inline">\right</del>)</<del class="diffchange diffchange-inline">m</del>>, пути на ребрах <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>, такие что  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Граф <<ins class="diffchange diffchange-inline">em</ins>>G=(V,E)</<ins class="diffchange diffchange-inline">em</ins>>, пути на ребрах <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>, такие что  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=23572&oldid=prev
StasFomin: Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}} -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
2023-04-10T20:45:32Z
<p>Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}} <!-- * {{has-testdata-and-visualization}} --> <!-- * {{has-pyomo-model}} --> <!-- * {{has-npc-reduction}} --> <!-- * {{add-random-fuzzing-tests}} --></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 20:45, 10 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l15" >Строка 15:</td>
<td colspan="2" class="diff-lineno">Строка 15:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{hard-problem-on-lab17|{{PAGENAME}}}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{hard-problem-on-lab17|{{PAGENAME}}}}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{has-testdata-and-visualization}} --></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{has-pyomo-model}} --></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{has-npc-reduction}} --></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{add-random-fuzzing-tests}} --></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><small></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><small></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=23433&oldid=prev
StasFomin: Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
2023-04-10T19:59:14Z
<p>Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 19:59, 10 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><!-- start --></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><!-- start <ins class="diffchange diffchange-inline">--><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} </ins>--></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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>, такие что  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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>, такие что  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=23304&oldid=prev
StasFomin в 23:19, 8 апреля 2023
2023-04-08T23:19:53Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 23:19, 8 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Граф <m>G=\left(V,E\right)</m>, пути на ребрах <m>l:E \rightarrow N</m>, и некоторая пара вершин <em>s,t</em> в <em>V</em>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Граф <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>, такие что  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Найти два непересекающихся по вершинам пути в <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>, такие что  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>** <m>(s,u_1) ∈ E</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Maximum_Disjoint_Connecting_Paths&diff=23303&oldid=prev
StasFomin: Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, пути на ребрах <m>l:E \rightarrow N</m>, и некоторая пара вершин <em>s,t</em>…»
2023-04-08T23:19:30Z
<p>Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, пути на ребрах <m>l:E \rightarrow N</m>, и некоторая пара вершин <em>s,t</em>…»</p>
<p><b>Новая страница</b></p><div><!-- start --><br />
* Граф <m>G=\left(V,E\right)</m>, пути на ребрах <m>l:E \rightarrow N</m>, и некоторая пара вершин <em>s,t</em> в <em>V</em>.<br />
Найти два непересекающихся по вершинам пути в <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>, такие что <br />
** <m>\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n</m><br />
** <m>(s,u_1) ∈ E</m><br />
** <m>(s,v_1) ∈ E</m><br />
** <m>(u_m,t) ∈ E</m><br />
** <m>(v_n,t) ∈ E</m><br />
** <m>∀i (u_i ,u_{i+1}) ∈ E</m><br />
** <m>∀i (v_i ,v_{i+1}) ∈ E</m><br />
<br />
* Минимизировать максимальную длину этих путей, т.е. <br />
<m>\max(l(s,u_1)+\sum_{i=1}^{m-1} l(u_i,u_{i+1})+l(u_m,t),<br />
l(s,v_1)+\sum_{i=1}^{n-1} l(v_i,v_{i+1})+l(v_n,t))</m><br />
<br />
----<br />
{{hard-problem-on-lab17|{{PAGENAME}}}}<br />
----<br />
<small><br />
{{ViggoCode|node123}}<br />
{{GDCode|ND41}}<br />
<!-- * [ Задача в википедии] --><br />
</small><br />
<!-- end --><br />
<br />
[[Категория:ClassicHardProblems]]</div>
StasFomin