"Записки научных семинаров ПОМИ"

Том 437, стр. 62-80

С.-Петербургский государственный университет, Университетский пр., д. 28, Старый Петергоф, 198504 С.-Петербург, Россия

obursian@gmail.com

Аннотация: В статье рассматривается преобразование графа $G$, которое заменяет индуцированный подграф $H$ произвольного размера на маленький новый подграф $h$. При этом $h$ подбирается таким образом, чтобы выполнялось равенство $M(G) = x M(G')$, где $G'$ -- новый граф, а $x$ -- множитель, зависящий от чисел паросочетаний графа $H$ и его подграфов. Приведен способ построения подграфа $h$ в случае, когда $G$ является плоским графом, а $H$ -- двудольным графом с условием на раскраску вершин, соединяющих его с остальной частью графа $G$. Показано, что в частных случаях небольшого числа таких вершин при замене плоского двудольного подграфа $H$ равенство выполнено для произвольного графа $G$. Библ. -- 8 назв.
Ключевые слова: число паросочетаний, ``Urban renewal'', пфаффиан [ matching number, ``Urban renewal'', Pfaffian]