"Записки научных семинаров ПОМИ"
Том 432, стр. 5-29
Удаление чипов. Urban Renewal revisited
В. Е. Аксенов, К. П. Кохась
НИУ ИТМО,
Кронверкский пр., д. 49,
197101 С.-Петербург, Россия
kpk@arbital.ru
- Аннотация:
В статье предлагается новое комбинаторно-алгебраическое преобразование графов ``удаление чипа'',
которое является обобщением известного трюка ``Urban renewal'' Куперберга и Проппа.
Удаление чипов можно использовать при вычислении определителей матриц смежности и чисел паросочетаний графов.
Красивым применением этой техники является теорема об удалении четырехконтактного чипа, \break
обобщаюшая идеи метода графической конденсации Куо.
Приведены многочисленные примеры.
Библ. -- 6 назв.
- Ключевые слова:
определитель матрицы смежности, число паросочетаний,
``Urban renewal'', пфаффиан, комбинаторная линейная алгебра
[determinant of adjacency matrix, matching number, ``Urban renewal'', pfaffian, combinatorial linear algebra]
Полный текст(.pdf)