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

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

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

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

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

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

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

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

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

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

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

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

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