Hardprob/Minimum Complete Bipartite Subgraph Cover — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена <!-- 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>G=\left(V,E\right)</m>.

Версия 19:59, 10 апреля 2023


Граф .

Найти полное покрытие двудольными подграфами G, т.е. коллекцию подмножеств вершин V → , такую, что

  • каждое такое подмножество вершин порождает полный двудольный граф.
  • каждое ребро содержит оба конца в каком-нибудь

Минимизировать «k» — размер этого покрытия.

Задача в лаб17 (рид-онли просмотр)

Источник — «https://discopal.ispras.ru/index.php?title=Hardprob/Minimum_Complete_Bipartite_Subgraph_Cover&oldid=23390»