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

Пусть Χ — множество графов, G — произвольный граф. Множество попарно непересекающихся порождённых подграфов графа G, изоморфных графам из Χ, называется упаковкой графа G относительно Χ, или просто его Χ-упаковкой. Задача об Χ-упаковке (Χ-MATCHING) состоит в том, чтобы найти Χ-упаковку графа наибольшего размера.
Множество C вершин графа G такое, что любой порождённый подграф графа G, изоморфный графу из X, содержит хотя бы одну вершину из С, называется вершинным покрытием графа G относительно X, или просто его X-покрытием. Иными словами, X-покрытие графа G — это такое множество вершин C, что G/С ∈ Free (X).
Задача об X-покрытии (X-COVER) состоит в том, чтобы найти X-покрытие графа наименьшего размера.
Граф G называется кёниговым относительно X, если в любом его порождённом подграфе H размер наибольшей X-упаковки равен размеру наименьшего X-покрытия.
В докладе будет дан обзор задач об упаковке и покрытии относительно различных классов, а также будет приведено описание некоторых классов кёниговых графов.