41
правка
Изменения
→Примеры #P-Complete задач
Построение графа <tex>G'</tex> выполним за полиномиальное время. Для этого будем использовать три вида блоков. (Все ребра, для которых на схеме не указан вес, имеют вес <tex>1</tex>.)
'''Блок переменной'''. Блок каждой переменной имеет два покрытия циклами, соответствующие присвоению <tex>true</tex> или <tex>false</tex> данной переменной. Присвоение <tex>true</tex> соответствует покрытию, содержащему все "внешние" ребра, присвоение <tex>false</tex> соответствует покрытию, включающему ребра-петли и ребро <tex>"``false"</tex>. Каждое внешнее ребро ассоциировано с одним клозом, в котором присутствует данная переменная.
'''Блок клоза'''. Любое покрытие циклами для данного блока не содержит в себе как минимум одно внешнее ребро. И для любого подмножества внешних ребер (за исключением набора из всех ребер) существует единственное покрытие и его вес равен <tex>1</tex>. Каждое внешнее ребро рассматриваемого клоза ассоциировано с одной переменной, присутствующей в нем.
