Hardprob/Minimum Bounded Diameter Augmentation — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена <m>\vert E'\vert</m> на <em>|E'|</em>) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \cup на ∪) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
* Граф <em>G=(V,E)</em>, положительное целое <m>D<\vert V\vert</m>. | * Граф <em>G=(V,E)</em>, положительное целое <m>D<\vert V\vert</m>. | ||
| − | * Найти дополняющий набор новых ребер <em>E'</em> для <em>G</em>, т.е. набор <em>E'</em> неупорядоченных пар вершин из <em>V</em>, такой что <m>G'=\left(V,E | + | * Найти дополняющий набор новых ребер <em>E'</em> для <em>G</em>, т.е. набор <em>E'</em> неупорядоченных пар вершин из <em>V</em>, такой что <m>G'=\left(V,E ∪ E'\right)</m> имеет диаметр <em>D</em>, т.е. максимальное расстояние между любыми парами вершин будет не больше чем <em>D</em>. |
* Минимизировать размер дополняющего множества <em>|E'|</em>. | * Минимизировать размер дополняющего множества <em>|E'|</em>. | ||
Версия 11:39, 17 апреля 2023
- Граф G=(V,E), положительное целое .
- Найти дополняющий набор новых ребер E' для G, т.е. набор E' неупорядоченных пар вершин из V, такой что имеет диаметр D, т.е. максимальное расстояние между любыми парами вершин будет не больше чем D.
- Минимизировать размер дополняющего множества |E'|.
Задача в лаб22 (рид-онли просмотр)