Участник:Midmedian/Алгоритм Федуччи-Маттеуса

Автор описания: И.А.Бабкин

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Федуччи-Маттеуса (FM-алгоритм) является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) за линейной время.

1.2 Математическое описание алгоритма

Пусть дан гиперграф [math]P=(C,N)[/math], где [math]C[/math] - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей (гиперрёбер) [math]N[/math]. Гарантируется, что гиперграф состоит как минимум из двух ячеек и что каждая из ячеек содержится хотя бы в одной из сетей.

Количество ячеек в [math]i[/math]-ой сети обозначим как [math]n(i)[/math], а размер [math]j[/math]-ой ячейки (количество сетей, в которые входит ячейка) за [math]s(j)[/math].

Размер блока [math]B[/math] определим, как

[math]|B|=\sum\limits_{i=1}^{|N|} n(i)=\sum\limits_{i=1}^{|C|} s(i)[/math].

Задача заключается в разделении [math]P[/math] на непересекающиеся блоки [math]A[/math] и [math]B[/math] размерами [math]|A|[/math] и [math]|B|[/math] соответственно так, чтобы выполнялось условие

[math]\frac{|A|}{|A|+|B|} \cong r[/math],

где [math]r[/math] - коэффициент разделения ([math]0 \lt r \lt 1[/math]).