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

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

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

@@ Строка 1: / Строка 1: @@
 * Граф <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>,
-** каждое из которых содержит ровно три вершины — <m>V_i=\{u_i,v_i,w_i\}</m>, <m>$1≤i≤k</m>
+** каждое из которых содержит ровно три вершины — <m>V_i=\{u_i,v_i,w_i\}</m>, <em>1 ≤ i ≤ k</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>.
 * Максимизировать размерность этой упаковки треугольников, т.е. число этих непересекающихся подмножеств <em>V<sub>i</sub></em>.