Hardprob/Maximum Triangle Packing — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена PCRE <m>(\w)\s*≤\s*(\w)\s*≤\s*(\w)\s*</m> на <em>\1 ≤ \2 ≤ \3</em>)
 
(не показано 8 промежуточных версий этого же участника)
Строка 1: Строка 1:
Граф <m>G=\left(V,E\right)</m>.
+
* Граф <em>G=(V,E)</em>.
 
+
* Найти «упаковку треугольников» для <em>G</em>, т.е. набор <em>V<sub>1</sub>, V<sub>2</sub>, , V<sub>k</sub></em> непересекающихся подмножеств <em>V</em>,  
Найти «упаковку треугольников» для <em>G</em>, т.е. набор <m>V_1, V_2, \ldots, V_k</m> непересекающихся подмножеств  
+
** каждое из которых содержит ровно три вершины — <m>V_i=\{u_i,v_i,w_i\}</m>, <em>1 i k</em>
<em>V</em>,  
+
** и все три ребра <m>\left<u_i,v_i\right></m>, <m>\left<u_i,w_i\right></m>, <m>\left<v_i,w_i\right></m> есть в <em>E</em>.
* каждое из которых содержит ровно три вершины — <m>V_i=\{u_i,v_i,w_i\}</m>, <m>$1\le i\le k</m>
+
* Максимизировать размерность этой упаковки треугольников, т.е. число этих непересекающихся подмножеств <em>V<sub>i</sub></em>.
* и все три ребра <m>\left<u_i,v_i\right></m>, <m>\left<u_i,w_i\right></m>, <m>\left<v_i,w_i\right></m> есть в <em>E</em>.
+
 
+
Максимизировать размерность этой упаковки треугольников, т.е. число этих непересекающихся подмножеств <m>V_i</m>.
+
  
 
----
 
----
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 
{{hard-problem-on-lab17|{{PAGENAME}}}}
 +
<!-- * {{has-testdata-and-visualization}} -->
 +
<!-- * {{has-pyomo-model}} -->
 +
<!-- * {{has-npc-reduction}} -->
 +
<!-- * {{add-random-fuzzing-tests}} -->
 
----
 
----
 
<small>
 
<small>

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

  • Граф G=(V,E).
  • Найти «упаковку треугольников» для G, т.е. набор V1, V2, …, Vk непересекающихся подмножеств V,
    • каждое из которых содержит ровно три вершины — , 1 ≤ i ≤ k
    • и все три ребра , , есть в E.
  • Максимизировать размерность этой упаковки треугольников, т.е. число этих непересекающихся подмножеств Vi.

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