(no subject)

[moonwalker72]

Оказывается написать алгоритм для подсчета числа возможных совершенных паросочетаний в произвольном графе - не так уж легко. Быстрый алгоритм FKT работает только для планарных графов. Попытка натравить его на граф, в котором был просто несвязный компонент K_3,3 привела к запрещенной точке его конечного автомата. Причем понял я это не сразу, потому что прошляпил упоминание о планарных графах. То же видимо и про подсчет сов.паросочетаний через перманент редуцированной матрицы смежности для двудольного графа: где строка - соответствует левой вершине, столбец - правой. В частном случае несвязного графа из двух компонент - K_3,3 и K_2,2 это правильно посчиталось, но в общем случае - нет. Дошел наконец до алгоритма Вазирани, описанного в статье 1988 года - он, хотя и все равно медленно, но не убойно медленно позволяет подсчитать сов.паросочетания в произвольном графе. Но сам алгоритм трудоемок - если писать его с нуля легко может занять больше 2000 строк на С. Он в себя включает несколько алгоритмов разбиения на трехреберно-вершинные подграфы и сортировки. К счастью нашел библиотеку IGRAPH на C. Научился писать сишные расширения для Python.