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

Том 507, стр. 26-34

St. Petersburg Department of Steklov Institute of Mathematics and Chebyshev Laboratory, St. Petersburg State University, St. Petersburg, Russia

zograf@pdmi.ras.ru

Аннотация: Предлагается универсальный подход к целому кругу перечислительных задач в графах, основанный на тензорных сетях. Ключевой момент состоит в сворачивании вдоль ребер графа подходящих симметрических тензоров, помещенных в его вершины. В частности, такой подход позволяет получить простые формулы для подсчета числа $d$-регулярных подграфов произвольного графа (включая число $d$-факторов) и число правильных реберных раскрасок. Также кратко обсуждается вопрос о вычислительной сложности основанных на этих формулах алгоритмов. Библ. -- 9 назв.
Ключевые слова: тензорные сети, $d$-регулярные подграфы, $d$-факторы, реберные раскраски [tensor network, $d$-regular subgraph, $d$-factor, edge coloring]