Hardprob/Maximum Induced Subgraph With Property P — различия между версиями

Версия 22:00, 6 апреля 2023

Граф и некое свойство (предикат) P над подграфами.

Свойство наследуемое, т.е. каждый подграф G' будет удовлетворять P,если сам G' ему удовлетворял.
Свойство нетривиальное, т.е. оно истинно и ложно для бесконечного количества графов.

Найти подмножество вершин , такое, что подграф порожденный V' имеет свойство P.

Максимизировать размер этого подграфа .

@@ Строка 2: / Строка 2: @@
 Граф <m>G=\left(V, E\right)</m> и некое свойство (предикат) <em>P</em> над подграфами.
-* Свойство наследуемое, т.е. каждый подграф <em>G'</em> будет удовлетворять <em>P</em>,
+* Свойство наследуемое, т.е. каждый подграф <em>G'</em> будет удовлетворять <em>P</em>,если сам <em>G'</em> ему удовлетворял.
-если сам <em>G'</em> ему удовлетворял. satisfies <em>P</em>.
 * Свойство нетривиальное, т.е. оно истинно и ложно для бесконечного количества графов.