Элиминационная игра.

Процесс преобразования первичного графа взаимодействия переменных, соответствующий процедуре элиминации переменных с помощью локального алгоритма, известен как «элиминационная игра», которая впервые была введена Партером[7], как графовая интерпретация метода исключения Гаусса. Входом для алгоритма элиминационной игры является граф и упорядочение графа (т.е. , если ‑ -я вершина в упорядочении ).

Алгоритм элиминационной игры состоит в следующем. Выбирается пер­вая, согласно упорядочению , вершина , и добавляются, если нужно, необ­хо­димые ребра так, чтобы все вершины, соседние с , образовывали клику. Затем удаляем вершину из измененного графа и продолжаем процесс, выбирая сле­дующую вершину нового графа согласно упорядочению . После про­хож­дения всех вершин добавляем в исходном графе все добавленные на каждом шаге ребра. Результатом этого алгоритма является пополненный граф , в котором, по сравнению с исходным графом , добавлены ребра.

В дальнейшем нам потребуется следующая

Лемма 8.1. или и для некоторого .