Разбиение графа: различия между версиями

'''Разбиение графа''' (на подграфы, иногда в литературе также употребляется термин '''разрезание графа'''<ref>Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.</ref>) — представление исходного [[Граф (математика)|графа]] <math>G=\left \langle A, V \right \rangle</math> в виде [[Множество|множества]] подмножеств вершин <math>\mathrm{Sep}~A = \left \{ A_1, A_2, ..., A_n \right \}, A_i \subseteq V</math> по определенным правилам. Обычно по условию задачи требуется, чтобы <math>\bigcup_{i=1}^{n} A_i = A</math>, т.е. все вершины исходного графа должны быть распределены по подмножествам, причем <math>A_i \neq \varnothing</math>. Обычно также дополнительно вводится требование [[ортогональность|ортогональности]] разбиения: <math>\forall i \neq j~ A_i \cap A_j = \varnothing</math>, т.е. одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Верхняя оценка числа разбиений определяется [[Число Белла|числом Белла]], однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), т.е. оценка является завышенной. При значениях числа вершин графа <math>N=\left| A \right|</math> более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется [[метод ветвей и границ]]), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием [[эвристический алгоритм|эвристических алгоритмов]].