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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --> Граф <m>G=\left(V,E\right)</m>. Найти полное покрытие двудольными подграфами <em>G</em>, т.е. ко…»)
 
Строка 4: Строка 4:
  
 
Найти полное покрытие двудольными подграфами <em>G</em>, т.е. коллекцию
 
Найти полное покрытие двудольными подграфами <em>G</em>, т.е. коллекцию
подмножеств вершин <em>V</em>  
+
подмножеств вершин <em>V</em>   → <m>$V_1,V_2,\ldots,V_k</m>, такую, что  
<m>$V_1,V_2,\ldots,V_k</m>, такую, что  
+
 
* каждое такое подмножество вершин <m>V_i</m> порождает полный двудольный граф.
 
* каждое такое подмножество вершин <m>V_i</m> порождает полный двудольный граф.
 
* каждое ребро <m>\left<u,v\right>\in E</m> содержит оба конца в каком-нибудь <m>V_i</m>
 
* каждое ребро <m>\left<u,v\right>\in E</m> содержит оба конца в каком-нибудь <m>V_i</m>

Версия 20:52, 6 апреля 2023


Граф .

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

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

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


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