Hardprob/Minimum Bounded Diameter Augmentation — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, положительное целое <m>D<\vert V\vert</m>. * Найти дополняющий набор…») |
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>, положительное целое <m>D<\vert V\vert</m>. | * Граф <m>G=\left(V,E\right)</m>, положительное целое <m>D<\vert V\vert</m>. | ||
* Найти дополняющий набор новых ребер <em>E'</em> для <em>G</em>, т.е. набор <em>E'</em> неупорядоченных пар вершин из <em>V</em>, такой что <m>G'=\left(V,E \cup E'\right)</m> имеет диаметр <em>D</em>, т.е. максимальное расстояние между любыми парами вершин будет не больше чем <em>D</em>. | * Найти дополняющий набор новых ребер <em>E'</em> для <em>G</em>, т.е. набор <em>E'</em> неупорядоченных пар вершин из <em>V</em>, такой что <m>G'=\left(V,E \cup E'\right)</m> имеет диаметр <em>D</em>, т.е. максимальное расстояние между любыми парами вершин будет не больше чем <em>D</em>. | ||
Версия 19:59, 10 апреля 2023
- Граф , положительное целое .
- Найти дополняющий набор новых ребер E' для G, т.е. набор E' неупорядоченных пар вершин из V, такой что имеет диаметр D, т.е. максимальное расстояние между любыми парами вершин будет не больше чем D.
- Минимизировать размер дополняющего множества .
Задача в лаб17 (рид-онли просмотр)