200
правок
Изменения
Нет описания правки
Пусть <tex>I_i \in \mathcal{I}_i</tex>, для <tex>i = 1\ldots k</tex> с <tex>I_i \cap I_j = \emptyset</tex>, если <tex>i \neq j</tex>. Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex> так, что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in \mathcal{I}_i</tex>.
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> {{---}} множество элементов <tex>s \notin I_i</tex> с <tex>I_i \cup {s} \in \mathcal{I}_i</tex>. Определим <tex>I = I_1 \cup \ldots \cup I_k</tex> которые могут быть добавлены в <tex>I_i</tex> таким образом, что <tex>I_i + xF = F_1 \cup \ldots \cup F_k</tex> независимое множество в и <tex>M_i\mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex> . Или формально:
Все наши кандидаты находятся в <tex>S \setminus I</tex> . Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>.
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
'''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n - 1</tex>
построить [[Граф замен|граф замен]] <tex>D_{M_i}(I_i)</tex>
'''if''' <tex>I_i + x s \in \mathcal{I}_i</tex> <tex>J \leftarrow I_i + xs</tex>
|id=th_1
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I + \cup s \in J \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам графа <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex>
