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

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

Граф G=(V,E).
Найти независимую последовательность в G, т.е. последовательность независимых вершин, v₁, …, v_m, таких, что для любого i < m, если вершина соседствует с , но то оно не будет соседствовать ни с одним v_j для любого j ≤ i.
Максимизировать «m» — длину этой последовательности.

@@ Строка 2: / Строка 2: @@
 * Граф <em>G=(V,E)</em>.
-* Найти независимую последовательность в <em>G</em>, т.е. последовательность независимых вершин, <m>v_1, \ldots, v_m</m>, таких, что для любого <em>i &lt; m</em>, если вершина <m>\bar v_i \in V</m> соседствует с <m>v_{i+1}</m>, но то оно не будет соседствовать ни с одним <m>v_j</m> для любого <em>j ≤ i</em>.
+* Найти независимую последовательность в <em>G</em>, т.е. последовательность независимых вершин, <em>v<sub>1</sub>, …, v<sub>m</sub></em>, таких, что для любого <em>i &lt; m</em>, если вершина <m>\bar v_i ∈  V</m> соседствует с <m>v_{i+1}</m>, но то оно не будет соседствовать ни с одним <em>v<sub>j</sub></em> для любого <em>j ≤ i</em>.
 * Максимизировать «m» — длину этой последовательности.