moonwalker72: (Default)
[personal profile] moonwalker72
Оказывается написать алгоритм для подсчета числа возможных совершенных паросочетаний в произвольном графе - не так уж легко. Быстрый алгоритм FKT работает только для планарных графов. Попытка натравить его на граф, в котором был просто несвязный компонент K3,3 привела к запрещенной точке его конечного автомата. Причем понял я это не сразу, потому что прошляпил упоминание о планарных графах. То же видимо и про подсчет сов.паросочетаний через перманент редуцированной матрицы смежности для двудольного графа: где строка - соответствует левой вершине, столбец - правой. В частном случае несвязного графа из двух компонент - K3,3 и K2,2 это правильно посчиталось, но в общем случае - нет. Дошел наконец до алгоритма Вазирани, описанного в статье 1988 года - он, хотя и все равно медленно, но не убойно медленно позволяет подсчитать сов.паросочетания в произвольном графе. Но сам алгоритм трудоемок - если писать его с нуля легко может занять больше 2000 строк на С. Он в себя включает несколько алгоритмов разбиения на трехреберно-вершинные подграфы и сортировки. К счастью нашел библиотеку IGRAPH на C. Научился писать сишные расширения для Python.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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:21 am
Powered by Dreamwidth Studios