Hardprob/Minimum B-Vertex Separator — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, рациональное <em>b</em>, <m>0<b\le 1/2</m>. * Найти разбиение <em>V</em> на не…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->) |
||
| Строка 1: | Строка 1: | ||
| − | <!-- start --> | + | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> |
* Граф <m>G=\left(V,E\right)</m>, рациональное <em>b</em>, <m>0<b\le 1/2</m>. | * Граф <m>G=\left(V,E\right)</m>, рациональное <em>b</em>, <m>0<b\le 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\}\le b\cdot \vert V\vert</m>, и ни одно ребро не лежит разными концами в <em>A</em> и <em>B</em> одновременно. | ||
Версия 19:59, 10 апреля 2023
- Граф , рациональное b, .
- Найти разбиение V на непересекающиеся множества A, B, и C, такие что , и ни одно ребро не лежит разными концами в A и B одновременно.
- Минимизировать размер разделителя, т.е. .
Задача в лаб17 (рид-онли просмотр)