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

StasFomin: Массовая правка: замена PCRE (\w)_(\w),\s…\s,\s(\w)_(\w)<\/m> на \1_\2, …, \3_\4*

2023-04-17T22:54:02Z

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

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

2023-04-17T22:45:11Z

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

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

2023-04-17T22:16:38Z

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

StasFomin: Массовая правка: замена (u,v) ∈ E на (u,v)∈ E

2023-04-17T21:35:55Z

Массовая правка: замена <m>(u,v) ∈ E</m> на (u,v)∈ E

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

2023-04-17T21:26:19Z

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

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

2023-04-17T18:01:16Z

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

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

2023-04-17T11:34:09Z

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

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

2023-04-17T06:34:16Z

Массовая правка: замена <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: Новая страница: « * Сеть N=\left(V,E,b,c\right), где граф G=\left(V,E\right) ем…»

2023-04-12T22:53:07Z

Новая страница: « * Сеть <m>N=\left(V,E,b,c\right)</m>, где ** граф <m>G=\left(V,E\right)</m> ** ем…»

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

* Сеть <m>N=\left(V,E,b,c\right)</m>, где
** граф <m>G=\left(V,E\right)</m>
** емкость на вершинах <m>b:V → N</m>
** емкость на ребрах <m>c: E \rightarrow N</m>
** T — набор токенов <m>t=\left(u,v,p\right)</m>, где <m>u,v ∈ V</m>, и p — это либо путь из u в v или пустое множество.

* Найти расписание S, т.е. последовательность <m>f_0, \ldots, f_l</m> конфигурационных функций <m>f_i:T \rightarrow V</m>, таких что
** для любого токена <m>t=\left(u,v,p\right)</m>, <m>f_0(t)=u</m> и <m>f_l(t)=v</m>.
** для любого <m>0 \leq i \leq l-1</m> и для любого токена t,
*** если <m>f_i(t)=v</m> и <m>f_{i+1}(t)=w</m>, то
**** <m>(u,v) \in E</m>
**** <m>\vert\{t':f_i(t')=w\}\vert < b(w)</m>
**** <m>\vert\{t':f_{i+1}(t')=w\}\vert \leq b(w)</m>
**** <m>\vert\{t':f_i(t')=v ∧ f_{i+1}(t')=w \}\vert \leq c(v,w)</m>
* Минимизировать длину расписания, l.

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




----

{{ViggoCode|node196}}





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

@@ Строка 6: / Строка 6: @@
 ** <em>T</em> — набор токенов <m>t=\left(u,v,p\right)</m>, где <m>u,v ∈ V</m>, и <em>p</em> — это либо путь из <em>u</em> в <em>v</em> или пустое множество.
-* Найти расписание <em>S</em>, т.е. последовательность <m>f_0, …, f_l</m> конфигурационных функций <m>f_i:T →  V</m>, таких что
+* Найти расписание <em>S</em>, т.е. последовательность <em>f<sub>0</sub>, …, f<sub>l</sub></em> конфигурационных функций <m>f_i:T →  V</m>, таких что
 ** для любого токена <m>t=\left(u,v,p\right)</m>, <m>f_0(t)=u</m> и <m>f_l(t)=v</m>.
 ** для любого <m>0 ≤ i ≤ l-1</m> и для любого токена <em>t</em>,

@@ Строка 6: / Строка 6: @@
 ** <em>T</em> — набор токенов <m>t=\left(u,v,p\right)</m>, где <m>u,v ∈ V</m>, и <em>p</em> — это либо путь из <em>u</em> в <em>v</em> или пустое множество.
-* Найти расписание <em>S</em>, т.е. последовательность <m>f_0, \ldots, f_l</m> конфигурационных функций <m>f_i:T →  V</m>, таких что
+* Найти расписание <em>S</em>, т.е. последовательность <m>f_0, …, f_l</m> конфигурационных функций <m>f_i:T →  V</m>, таких что
 ** для любого токена <m>t=\left(u,v,p\right)</m>, <m>f_0(t)=u</m> и <m>f_l(t)=v</m>.
 ** для любого <m>0 ≤ i ≤ l-1</m> и для любого токена <em>t</em>,

@@ Строка 2: / Строка 2: @@
 * Сеть <m>N=\left(V,E,b,c\right)</m>, где
 ** граф <em>G=(V,E)</em>
-** емкость на вершинах <m>b:V → N</m>
+** емкость на вершинах <em>b: V → N</em>
 ** емкость на ребрах <em>c: E → N</em>
 ** <em>T</em> — набор токенов <m>t=\left(u,v,p\right)</m>, где <m>u,v ∈ V</m>, и <em>p</em> — это либо путь из <em>u</em> в <em>v</em> или пустое множество.

@@ Строка 10: / Строка 10: @@
 ** для любого <m>0 ≤ i ≤ l-1</m> и для любого токена <em>t</em>,
 *** если <m>f_i(t)=v</m> и <m>f_{i+1}(t)=w</m>, то
-**** <m>(u,v) ∈  E</m>
+**** <em>(u,v)∈ E</em>
 **** <m>\vert\{t':f_i(t')=w\}\vert < b(w)</m>
 **** <m>\vert\{t':f_{i+1}(t')=w\}\vert ≤ b(w)</m>

@@ Строка 8: / Строка 8: @@
 * Найти расписание <em>S</em>, т.е. последовательность <m>f_0, \ldots, f_l</m> конфигурационных функций <m>f_i:T →  V</m>, таких что
 ** для любого токена <m>t=\left(u,v,p\right)</m>, <m>f_0(t)=u</m> и <m>f_l(t)=v</m>.
-** для любого <m>0 \leq i \leq l-1</m> и для любого токена <em>t</em>,
+** для любого <m>0 ≤ i ≤ l-1</m> и для любого токена <em>t</em>,
 *** если <m>f_i(t)=v</m> и <m>f_{i+1}(t)=w</m>, то
 **** <m>(u,v) ∈  E</m>
 **** <m>\vert\{t':f_i(t')=w\}\vert < b(w)</m>
-**** <m>\vert\{t':f_{i+1}(t')=w\}\vert \leq b(w)</m>
+**** <m>\vert\{t':f_{i+1}(t')=w\}\vert ≤ b(w)</m>
-**** <m>\vert\{t':f_i(t')=v ∧ f_{i+1}(t')=w \}\vert \leq c(v,w)</m>
+**** <m>\vert\{t':f_i(t')=v ∧ f_{i+1}(t')=w \}\vert ≤ c(v,w)</m>
 * Минимизировать длину расписания, <em>l</em>.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Сеть <m>N=\left(V,E,b,c\right)</m>, где
-** граф <m>G=\left(V,E\right)</m>
+** граф <em>G=(V,E)</em>
 ** емкость на вершинах <m>b:V → N</m>
 ** емкость на ребрах <m>c: E \rightarrow N</m>