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

Текущая версия на 22:45, 17 апреля 2023

Граф G=(V,E).

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

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

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-Граф <m>G=\left(V,E\right)</m>.
+Граф <em>G=(V,E)</em>.
 Найти полное покрытие двудольными подграфами <em>G</em>, т.е. коллекцию
-подмножеств вершин <em>V</em>
+подмножеств вершин <em>V</em>   → <m>$V_1,V_2,…,V_k</m>, такую, что
-<m>$V_1,V_2,\ldots,V_k</m>, такую, что
+* каждое такое подмножество вершин <em>V<sub>i</sub></em> порождает полный двудольный граф.
-* каждое такое подмножество вершин <m>V_i</m> порождает полный двудольный граф.
+* каждое ребро <em>(u,v) ∈ E</em> содержит оба конца в каком-нибудь <em>V<sub>i</sub></em>
-* каждое ребро <m>\left<u,v\right>\in E</m> содержит оба конца в каком-нибудь <m>V_i</m>
 Минимизировать «k» — размер этого покрытия.
@@ Строка 13: / Строка 12: @@
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
+<!-- * {{has-testdata-and-visualization}} -->
+<!-- * {{has-pyomo-model}} -->
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>