Неориентированные графы и конъюктивные нормальные формы, их задающие

Abstract

В дискретной математике весьма важен алгоритм построения по конъюнктивной нормальной форме (КНФ) неориентированного графа (с обозначением его вершин 2-наборами). Его важность в том, что этот алгоритм доказывает полиномиальную сводимость проблемы ВЫП к проблеме m-клики. Естественно возникает вопрос о том, каждый ли неориентированный граф (неорграф), если его вершины обозначить аналогично, может быть построен по соответствующей КНФ. В данной статье показывается, что этот подход осуществить в общем случае невозможно, то есть описывается серия неориентированных графов, которые не могут быть заданы ни одной КНФ.