02 марта 2018 г.

Д.Б. Мокеев (ИИТММ ННГУ им. Н.И. Лобачевского)

"Об упаковках и вершинных покрытиях и о кёниговых графах"

          Пусть Χ – множество графов, G – произвольный граф. Множество попарно непересекающихся порождённых подграфов графа G, изоморфных графам из Χ, называется упаковкой  графа  G  относительно  Χ,  или  просто  его  Χ-упаковкой.  Задача   об Χ-упаковке (Χ-MATCHING) состоит в том, чтобы найти Χ-упаковку графа наибольшего размера.

        Множество C вершин графа G такое, что любой порождённый подграф графа G, изоморфный графу из X, содержит хотя бы одну вершину из С, называется вершинным покрытием  графа  G  относительно  X,  или  просто  его  X-покрытием. Иными  словами, X-покрытие  графа  G – это  такое множество  вершин C,  что Задача об X-покрытии (X-COVER) состоит в том, чтобы найти X-покрытие графа наименьшего размера.

        Граф G называется кёниговым относительно X, если в любом его порождённом подграфе H размер наибольшей X-упаковки равен размеру наименьшего X-покрытия.

        В докладе будет дан обзор задач об упаковке и покрытии относительно различных классов, а также будет приведено описание некоторых классов кёниговых графов.

Наверх