Разбиение графа

Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа $G=⟨A,V⟩$$G=\left\langle A,V\right\rangle$ в виде множества подмножеств вершин $\mathrm{S}\mathrm{e}\mathrm{p}A=\left\{A_1,A_2,...,A_n\right\},A_i\subseteq <!--\; \subseteq \; -->A$$\mathrm {Sep} ~A=\left\{A_{1},A_{2},...,A_{n}\right\},A_{i}\subseteq A$ по определенным правилам. Обычно по условию задачи требуется, чтобы $\underset{i=1}{\overset{n}{\bigcup <!--\; \bigcup \; -->}}{A}_i=A$$\bigcup _{i=1}^{n}A_{i}=A$, то есть все вершины исходного графа должны быть распределены по подмножествам, причём $A_i\ne <!--\; \ne \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}$$A_{i}\neq \varnothing$. Обычно также дополнительно вводится требование ортогональности разбиения: $\mathrm{\forall <!--\; \forall \; -->}i\ne <!--\; \ne \; -->j{A}_i\cap <!--\; \cap \; -->A_j=\mathrm{\varnothing <!--\; \varnothing \; -->}$$\forall i\neq j~A_{i}\cap A_{j}=\varnothing$, то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа $N=\left|A\right|$$N=\left|A\right|$ более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов.

Пример разбиения параллельной граф-схемы алгоритма логического управления. В составе блоков, отмеченных разными цветами, нет параллельных вершин

Необходимость получения разбиения возникает при решении ряда задач:

1. Задача раскраски графа — каждое множество вершин $V_i$$V_i$ состоит из вершин одного цвета, причём вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса NP (критерий оптимальности — $n\to <!--\; \to \; -->min$$n\rightarrow \min$).
2. Задача определения числа и состава компонент связности графа.
3. При проектировании топологии локальной сети её разбиение на широковещательные домены определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к файловым серверам, службам DHCP, WINS, DNS и т. д.), ограничения — число портов и пропускная способность коммутаторов, маршрутизаторов и каналов связи, а также стоимость).
4. В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.
5. В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.
6. Представление графа в виде ярусно-параллельной формы или граф-схемы алгоритма в виде множества сечений (множества вершин в составе сечений могут быть неортогональными).
7. Разбиение графа алгоритма на непересекающиеся подграфы с последующим их размещением в процессорных элементах или элементах в составе ПЛИС при реализации конвейерной обработки данных (балансировка нагрузки).

Методы разбиения графаПравить

• Покоординатное разбиение
• Рекурсивный инерционный метод деления пополам
• Деление сети с использованием кривых Пеано
• Деление с учётом связности (по сути, поиск в ширину)
• Алгоритм Кернигана — Лина (англ.)

См. такжеПравить

• Gerasim@Home