О сложности сборки полных и полных двудольных графов

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