Hardprob/Minimum Ratio-Cut - История изменений

StasFomin: Массовая правка: замена PCRE (\w)_(\w) на \1_\2

2023-04-17T22:33:38Z

Массовая правка: замена PCRE <m>(\w)_(\w)</m> на \1\2

StasFomin: Массовая правка: замена \cap на ∩

2023-04-17T21:49:05Z

Массовая правка: замена \cap на ∩

StasFomin: Массовая правка: замена \in на ∈

2023-04-17T18:01:14Z

Массовая правка: замена \in на ∈

StasFomin: Массовая правка: замена c: E \rightarrow N на c: E → N

2023-04-17T06:34:15Z

Массовая правка: замена <m>c: E \rightarrow N</m> на c: E → N

StasFomin: Массовая правка: замена G=\left(V,E\right) на G=(V,E)

2023-04-17T05:46:27Z

Массовая правка: замена <m>G=\left(V,E\right)</m> на G=(V,E)

StasFomin: Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}}

2023-04-10T20:45:33Z

Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}}

StasFomin: Массовая правка: замена на

2023-04-10T19:59:15Z

Массовая правка: замена  на

StasFomin: Новая страница: « * Граф G=\left(V,E\right), пропускная способность на ребрах c: E \rightarrow N, k това…»

2023-04-07T22:15:07Z

Новая страница: « * Граф <m>G=\left(V,E\right)</m>, пропускная способность на ребрах <m>c: E \rightarrow N</m>, k това…»

Новая страница

* Граф <m>G=\left(V,E\right)</m>, пропускная способность на ребрах <m>c: E \rightarrow N</m>, k
товаров, т.е., k пар <m>(s_i,t_i) \in V^2</m>, и запросы <m>d_i</m> для каждой пары.
* Найти разрез, т.е. разбиение V на два непересекающихся набора <m>V_1</m> и <m>V_2</m>.
* Минимизировать емкость разреза деленную на объем запросов через этот разрез:

<m>
\begin{displaymath}\sum_{v_1\in V_1, v_2\in V_2 \atop (v_1,v_2) \in E}c(v_1,v_2)/
\sum_{i:\vert\{s_i,t_i\} \cap V_1\vert=1}d_i.
\end{displaymath}
</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
----

{{ViggoCode|node94}}





[[Категория:ClassicHardProblems]]

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Граф <em>G=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em>
-товаров, т.е., <em>k</em> пар <m>(s_i,t_i) ∈  V^2</m>, и запросы <m>d_i</m> для каждой пары.
+товаров, т.е., <em>k</em> пар <m>(s_i,t_i) ∈  V^2</m>, и запросы <em>d<sub>i</sub></em> для каждой пары.
-* Найти разрез, т.е. разбиение <em>V</em> на два непересекающихся набора <m>V_1</m> и <m>V_2</m>.
+* Найти разрез, т.е. разбиение <em>V</em> на два непересекающихся набора <em>V<sub>1</sub></em> и <em>V<sub>2</sub></em>.
 * Минимизировать емкость разреза деленную на объем запросов через этот разрез:

@@ Строка 7: / Строка 7: @@
 <m>
 \begin{displaymath}\sum_{v_1∈  V_1, v_2∈  V_2 \atop (v_1,v_2) ∈  E}c(v_1,v_2)/
-\sum_{i:\vert\{s_i,t_i\} \cap V_1\vert=1}d_i.
+\sum_{i:\vert\{s_i,t_i\} ∩  V_1\vert=1}d_i.
 \end{displaymath}
 </m>

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Граф <em>G=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em>
-товаров, т.е., <em>k</em> пар <m>(s_i,t_i) \in V^2</m>, и запросы <m>d_i</m> для каждой пары.
+товаров, т.е., <em>k</em> пар <m>(s_i,t_i) ∈  V^2</m>, и запросы <m>d_i</m> для каждой пары.
 * Найти разрез, т.е. разбиение <em>V</em> на два непересекающихся набора <m>V_1</m> и <m>V_2</m>.
 * Минимизировать емкость разреза деленную на объем запросов через этот разрез:
 <m>
-\begin{displaymath}\sum_{v_1\in V_1, v_2\in V_2 \atop (v_1,v_2) \in E}c(v_1,v_2)/
+\begin{displaymath}\sum_{v_1∈  V_1, v_2∈  V_2 \atop (v_1,v_2) ∈  E}c(v_1,v_2)/
 \sum_{i:\vert\{s_i,t_i\} \cap V_1\vert=1}d_i.
 \end{displaymath}

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Граф <em>G=(V,E)</em>, пропускная способность на ребрах <m>c: E \rightarrow N</m>, <em>k</em>
+* Граф <em>G=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em>
 товаров, т.е., <em>k</em> пар <m>(s_i,t_i) \in V^2</m>, и запросы <m>d_i</m> для каждой пары.
 * Найти разрез, т.е. разбиение <em>V</em> на два непересекающихся набора <m>V_1</m> и <m>V_2</m>.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Граф <m>G=\left(V,E\right)</m>, пропускная способность на ребрах <m>c: E \rightarrow N</m>, <em>k</em>
+* Граф <em>G=(V,E)</em>, пропускная способность на ребрах <m>c: E \rightarrow N</m>, <em>k</em>
 товаров, т.е., <em>k</em> пар <m>(s_i,t_i) \in V^2</m>, и запросы <m>d_i</m> для каждой пары.
 * Найти разрез, т.е. разбиение <em>V</em> на два непересекающихся набора <m>V_1</m> и <m>V_2</m>.

@@ Строка 13: / Строка 13: @@
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
 ----
 <small>