Покрытия булевых графов

Для графов, вложимых в $n$-куб (булевых графов), рассматривается задача покрытия связными графами, образующими некоторый базис. К этой задаче, в частности, сводится построение ДНФ булевой функции и нахождение ее представления в виде однородной сети пороговых элементов. Предлагается способ оценки необходимого числа базисных элементов с помощью введенного в статье аппарата систем существенных вершин, который для некоторых типов булевых графов, названных простыми, и соответствующих булевых функций позволяет доказывать минимальность их представлений базисными элементами. Применительно к различным базисам изучаются вопросы строения простых графов и графов, не являющихся простыми, выделяются классы базисов, названных трансверсальными, для которых все булевы графы являются простыми.