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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --> Граф <m>G=\left(V, E\right)</m> и некое свойство (предикат) <em>P</em> над подграфами. * Свойство…»)
 
Строка 2: Строка 2:
  
 
Граф <m>G=\left(V, E\right)</m> и некое свойство (предикат) <em>P</em> над подграфами.
 
Граф <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>.
+
 
* Свойство нетривиальное, т.е. оно истинно и ложно для бесконечного количества графов.
 
* Свойство нетривиальное, т.е. оно истинно и ложно для бесконечного количества графов.
  

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


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

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

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

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


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