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

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

Граф .

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

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

@@ Строка 4: / Строка 4: @@
 Найти полное покрытие двудольными подграфами <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>\left<u,v\right>\in E</m> содержит оба конца в каком-нибудь <m>V_i</m>