Hardprob/Minimum B-Vertex Separator — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->) |
StasFomin (обсуждение | вклад) (Массовая правка: замена 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}}}} --> | ||
| − | * Граф < | + | * Граф <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\} | + | * Найти разбиение <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> одновременно. |
| − | * Минимизировать размер разделителя, т.е. < | + | * Минимизировать размер разделителя, т.е. <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 (рид-онли просмотр)