Hardprob/Minimum B-Vertex Separator — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->)
(Массовая правка: замена PCRE <m>\\vert (\w+)\\vert</m> на <em>|\1|</em>)
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Граф <m>G=\left(V,E\right)</m>, рациональное <em>b</em>, <m>0<b\le 1/2</m>.
+
* Граф <em>G=(V,E)</em>, рациональное <em>b</em>, <m>0<b≤1/2</m>.
* Найти разбиение <em>V</em> на непересекающиеся множества <em>A, B</em>, и <em>C</em>, такие что <m>\max\{\vert A\vert ,\vert B\vert\}\le b\cdot \vert V\vert</m>, и ни одно ребро не лежит разными концами в <em>A</em> и <em>B</em> одновременно.
+
* Найти разбиение <em>V</em> на непересекающиеся множества <em>A, B</em>, и <em>C</em>, такие что <m>\max\{\vert A\vert ,\vert B\vert\}≤b\cdot \vert V\vert</m>, и ни одно ребро не лежит разными концами в <em>A</em> и <em>B</em> одновременно.
* Минимизировать размер разделителя, т.е. <m>\vert C\vert</m>.
+
* Минимизировать размер разделителя, т.е. <em>|C|</em>.
  
 
----
 
----
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 +
<!-- * {{has-testdata-and-visualization}} -->
 +
<!-- * {{has-pyomo-model}} -->
 +
<!-- * {{has-npc-reduction}} -->
 +
<!-- * {{add-random-fuzzing-tests}} -->
 
----
 
----
 
<small>
 
<small>

Текущая версия на 23:06, 17 апреля 2023

  • Граф G=(V,E), рациональное b, .
  • Найти разбиение V на непересекающиеся множества A, B, и C, такие что , и ни одно ребро не лежит разными концами в A и B одновременно.
  • Минимизировать размер разделителя, т.е. |C|.

Задача в лаб22 (рид-онли просмотр)