Изменения

<mathtex>IND\,\!</mathtex> и <mathtex>CLIQUE\,\!</mathtex> <mathtex>–\,\!</mathtex> множество пар <mathtex>\langle G, k \rangle \,\!</mathtex>, где <mathtex>G\,\!</mathtex> – граф, <mathtex>k\,\!</mathtex> – натуральное число. Пара <mathtex>\langle G, k \rangle \,\!</mathtex> принадлежит <mathtex>IND\,\!</mathtex>, если в графе <mathtex>G\,\!</mathtex> есть подграф с <mathtex>k\,\!</mathtex> вершинами, в котором все вершины не связаны ребрами. Пара <mathtex>\langle G, k \rangle \,\!</mathtex> принадлежит <mathtex>CLIQUE\,\!</mathtex>, если в графе <mathtex>G\,\!</mathtex> есть подграф с <mathtex>k\,\!</mathtex> вершинами, в котором между каждой парой вершин проходит ребро.

Существует функция <mathtex>f\,\!</mathtex> такая, что <mathtex>f(\langle G, k \rangle ) = \langle H, k \rangle \,\!</mathtex>, где <mathtex>H\,\!</mathtex> – граф, в котором столько же вершин, сколько и в <mathtex>G\,\!</mathtex>, а ребра расставлены следующим образом: если в графе <mathtex>G\,\!</mathtex> между вершинами <mathtex>u\,\!</mathtex> и <mathtex>v\,\!</mathtex> есть ребро, то в графе <mathtex>H\,\!</mathtex> это ребро не проводится, если же в графе <mathtex>G\,\!</mathtex> между этими вершинами его не было, то в <mathtex>H\,\!</mathtex> оно есть между соответствующими вершинами. Эта функция вычисляется за линейное время от длины входа, если представлять граф в виде матрицы смежности.

Заметим, что если в графе <mathtex>G\,\!</mathtex> был независимый подграф с <mathtex>k\,\!</mathtex> вершинами, то в <mathtex>H\,\!</mathtex> между всеми вершинами подграфа будут ребра, следовательно, в графе <mathtex>H\,\!</mathtex> будет клика с <mathtex>k\,\!</mathtex> вершинами.

С другой стороны, если в <mathtex>H\,\!</mathtex> есть клика с <mathtex>k\,\!</mathtex> вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе <mathtex>G\,\!</mathtex>. Т.о. в графе <mathtex>G\,\!</mathtex> был независимый подграф с <mathtex>k\,\!</mathtex> вершинами.

Из всего сказанного следует, что <mathtex>IND \le CLIQUE\,\!</mathtex>.