Отыскание всех наименьших покрытий графа кликами

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