Hardprob/Minimum Bounded Diameter Augmentation — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена <m>\vert E'\vert</m> на <em>|E'|</em>)
(Массовая правка: замена \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 \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 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 (рид-онли просмотр)