Алгоритмы канонического разложения графа и распознавания полярности

Abstract

Все рассматриваемые здесь графы конечные, неориентированные, без петель и кратных ребер. В [6] введено понятие «полярный граф». Если для множества VG вершин графа G существует такое разбиение VG—A[]B, что все связные компоненты индуцированного графа G(B) и дополнительного G(A) являются полными графами, то G называется полярным графом, а указанное разбиение — полярным разбиением. А называется верхней долей графа G, В — его нижней долей; одна из них может быть пустой.