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

Profile

moonwalker72: (Default)
moonwalker72

June 2017

S M T W T F S
    123
45678910
1112 1314151617
18192021222324
252627282930 

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 21st, 2017 10:27 am
Powered by Dreamwidth Studios