О линейных пространствах двудольных графов

В статье рассматриваются симметрические линейные пространства двудольных графов (СЛПДГ), т. е. множество двудольных графов с фиксированными долями, замкнутое относительно симметрической разности и перестановок вершин в каждой доле. В работе получено структурное описание всех СЛПДГ. Симметрические линейные пространства двудольных графов делят на тривиальные (четыре СЛПДГ) и нетривиальные. Нетривиальные, в свою очередь, подразделяют на два семейства: серия С, состоящая только из биполных графов (графов, являющихся дизъюнктным объединением двух полных двудольных графов (крылья графа)) и серия D, состоящая из множества графов, у которых степени вершин в~одной доле имеют одинаковую четность, а в другой могут быть любыми. Доказано, что любое СЛПДГ серии D совпадает с одним из девяти множеств, заданных четностями степеней вершин. Для СЛПДГ серии C (множество биполных графов) получено, что любое двустороннее СЛПДГ (т. е. содержащее графы, оба крыла которых имеют непустые доли) является пересечением множества всех биполных графов с множеством всех графов с четным числом ребер или каким-нибудь из пространств серии D.