https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Hardprob%2FMinimum_Upgrading_Spanning_Tree
Hardprob/Minimum Upgrading Spanning Tree - История изменений
2026-04-25T15:16:32Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25578&oldid=prev
StasFomin в 21:10, 26 апреля 2023
2023-04-26T21:10:31Z
<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;">Версия 21:10, 26 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l18" >Строка 18:</td>
<td colspan="2" class="diff-lineno">Строка 18:</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>
<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><!-- end --></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><!-- end --></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 style="font-weight: bold; text-decoration: none;">{{reserve-task|[[Участник:StasFomin|StasFomin]] 08:36, 25 апреля 2023 (UTC)}}</del></div></td><td colspan="2"> </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;"></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;"></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>[[Категория:ClassicHardProblems]]</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>[[Категория:ClassicHardProblems]]</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25527&oldid=prev
StasFomin в 08:36, 25 апреля 2023
2023-04-25T08:36:24Z
<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;">Версия 08:36, 25 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l18" >Строка 18:</td>
<td colspan="2" class="diff-lineno">Строка 18:</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>
<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><!-- end --></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><!-- end --></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;">{{reserve-task|[[Участник:StasFomin|StasFomin]] 08:36, 25 апреля 2023 (UTC)}}</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;"></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;"></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>[[Категория:ClassicHardProblems]]</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>[[Категория:ClassicHardProblems]]</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25243&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em>
2023-04-17T22:33:38Z
<p>Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</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:33, 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="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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <em>v ∈ V</em>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <em>v ∈ V</em>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>W⊆V</em>, так чтобы вес минимального остовного дерева с весами <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">d_W</del></<del class="diffchange diffchange-inline">m</del>>, была ограничена  <em>D</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>* Найти набор обновляемых вершин <em>W⊆V</em>, так чтобы вес минимального остовного дерева с весами <<ins class="diffchange diffchange-inline">em>d<sub</ins>><ins class="diffchange diffchange-inline">W</ins></<ins class="diffchange diffchange-inline">sub></em</ins>>, была ограничена  <em>D</em>.  </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>><del class="diffchange diffchange-inline">d_W</del></<del class="diffchange diffchange-inline">m</del>> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W∩  \{u,v\}\vert=i</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>><ins class="diffchange diffchange-inline">d<sub>W</ins></<ins class="diffchange diffchange-inline">sub></em</ins>> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W∩  \{u,v\}\vert=i</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>c(W)=\sum_{v∈  W} c(v)</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>c(W)=\sum_{v∈  W} c(v)</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;"></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;"></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25174&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на <em>\1 ∈ \2</em>
2023-04-17T22:05:31Z
<p>Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на <em>\1 ∈ \2</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:05, 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> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">v∈  </del>V</<del class="diffchange diffchange-inline">m</del>>, и некое ограничивающее значение <em>D</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <<ins class="diffchange diffchange-inline">em</ins>><ins class="diffchange diffchange-inline">v ∈ </ins>V</<ins class="diffchange diffchange-inline">em</ins>>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>* Найти набор обновляемых вершин <em>W⊆V</em>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>* Найти набор обновляемых вершин <em>W⊆V</em>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W∩  \{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W∩  \{u,v\}\vert=i</m>.</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25156&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>(\w)\s*⊆\s*(\w)</m> на <em>\1⊆\2</em>
2023-04-17T22:01:38Z
<p>Массовая правка: замена PCRE <m>(\w)\s*⊆\s*(\w)</m> на <em>\1⊆\2</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:01, 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="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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v∈  V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v∈  V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>><del class="diffchange diffchange-inline">W⊆ V</del></<del class="diffchange diffchange-inline">m</del>>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</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>* Найти набор обновляемых вершин <<ins class="diffchange diffchange-inline">em</ins>><ins class="diffchange diffchange-inline">W⊆V</ins></<ins class="diffchange diffchange-inline">em</ins>>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W∩  \{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W∩  \{u,v\}\vert=i</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>c(W)=\sum_{v∈  W} c(v)</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>c(W)=\sum_{v∈  W} c(v)</m>.</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25140&oldid=prev
StasFomin: Массовая правка: замена \cap на ∩
2023-04-17T21:49:05Z
<p>Массовая правка: замена \cap на ∩</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;">Версия 21:49, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >Строка 2:</td>
<td colspan="2" class="diff-lineno">Строка 2:</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v∈  V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) ≤ d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v∈  V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>W⊆ V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>W⊆ V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert <del class="diffchange diffchange-inline">W\cap </del>\{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert <ins class="diffchange diffchange-inline">W∩  </ins>\{u,v\}\vert=i</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>c(W)=\sum_{v∈  W} c(v)</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>c(W)=\sum_{v∈  W} c(v)</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;"></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;"></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:25082:newid:25140 -->
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25082&oldid=prev
StasFomin: Массовая правка: замена \leq на ≤
2023-04-17T21:26:20Z
<p>Массовая правка: замена \leq на ≤</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;">Версия 21:26, 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> d_2(e) ≤ d_1(e) <del class="diffchange diffchange-inline">\leq </del>d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v∈  V</m>, и некое ограничивающее значение <em>D</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) <ins class="diffchange diffchange-inline">≤ </ins>d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v∈  V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>W⊆ V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>W⊆ V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</m>.</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=25051&oldid=prev
StasFomin: Массовая правка: замена \in на ∈
2023-04-17T18:01:30Z
<p>Массовая правка: замена \in на ∈</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;">Версия 18:01, 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> d_2(e) ≤ d_1(e) \leq d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m><del class="diffchange diffchange-inline">v\in </del>V</m>, и некое ограничивающее значение <em>D</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) \leq d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m><ins class="diffchange diffchange-inline">v∈  </ins>V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>W⊆ V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>W⊆ V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</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>c(W)=\sum_{<del class="diffchange diffchange-inline">v\in </del>W} c(v)</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>c(W)=\sum_{<ins class="diffchange diffchange-inline">v∈  </ins>W} c(v)</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;"></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;"></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>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=24824&oldid=prev
StasFomin: Массовая правка: замена \subseteq на ⊆
2023-04-17T11:08:44Z
<p>Массовая правка: замена \subseteq на ⊆</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:08, 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="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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) \leq d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v\in V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>* Граф <em>G=(V,E)</em>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) \leq d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v\in V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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><del class="diffchange diffchange-inline">W\subseteq </del>V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</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><ins class="diffchange diffchange-inline">W⊆ </ins>V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</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>c(W)=\sum_{v\in W} c(v)</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>c(W)=\sum_{v\in W} c(v)</m>.</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Upgrading_Spanning_Tree&diff=24684&oldid=prev
StasFomin: Массовая правка: замена <m>G=\left(V,E\right)</m> на <em>G=(V,E)</em>
2023-04-17T05:46:27Z
<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> d_2(e) ≤ d_1(e) \leq d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v\in V</m>, и некое ограничивающее значение <em>D</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>* Граф <<ins class="diffchange diffchange-inline">em</ins>>G=(V,E)</<ins class="diffchange diffchange-inline">em</ins>>, три функции весов на ребрах <m> d_2(e) ≤ d_1(e) \leq d_0(e) </m> (для всех <em>e ∈ E</em>), где <m>d_i(e)</m> означает вес ребра <em>e</em>, если <em>i</em> его концов «обновлены», причем известна стоимость обновления <em>c(v)</em> для каждой вершины <m>v\in V</m>, и некое ограничивающее значение <em>D</em> для веса минимального остовного дерева.</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>W\subseteq V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>W\subseteq V</m>, так чтобы вес минимального остовного дерева с весами <m>d_W</m>, была ограничена  <em>D</em>.  </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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</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>d_W</m> означает вес ребра в результате обновления вершин в <em>W</em>, т.е. <m>d_W(u,v)=d_i(u,v)</m>, где <m>\vert W\cap \{u,v\}\vert=i</m>.</div></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:24605:newid:24684 -->
</table>
StasFomin