"Записки научных семинаров ПОМИ"
Том 436, стр. 5-33
Удаление чипов при подсчете пфаффианов
В. Е. Аксенов, К. П. Кохась
НИУ ИТМО,
Кронверкский пр., д. 49,
197101 С.-Петербург, Россия
С.-Петербургский
государственный университет;
НИУ ИТМО,
С.-Петербург, Россия
kpk@arbital.ru
- Аннотация:
Пусть $G$ -- произвольный связный (неориентированный) граф. Рассмотрим
произвольную ориентацию его ребер. В этой заметке мы вводим
специальную операцию -- вырезание чипа, -- которая обобщает трюк
``Urban Renewal'' Куперберга и Проппа, применяемый при подсчете
паросочетаний графа, и технику вырезания чипа при подсчете
определителей, развитую авторами в предыдущей статье. Удалив из графа
$G$ чип $H$, мы добавляем к оставшемуся графу несколько ребер так, что
полученный граф $G'$ удовлетворяет соотношению $\mathrm{Pf}(G) = \mathrm{Pf}(H)
\mathrm{Pf}(G')$. Мы приводим примеры подсчета числа паросочетаний графов с
помощью этой техники.
Библ. -- 10 назв.
- Ключевые слова:
пфаффиан, число паросочетаний, графическая конденсация
[Pfaffian, matching number, graphical condensation]
Полный текст(.pdf)