Розбиття графа

Розбиття графа на підграфи (англ. Graph partition) (іноді в літературі також вживається термін розрізання графа) — подання вихідного графа $G=\left\langle A,V\right\rangle$ у вигляді множини підмножин вершин $\mathrm {Sep} ~A=\left\{A_{1},A_{2},...,A_{n}\right\},A_{i}\subseteq V$ за певними правилами. Зазвичай за умовою задачі потрібно, щоб $\bigcup _{i=1}^{n}A_{i}=A$, тобто всі вершини вихідного графа повинні бути розподілені на підмножини, причому $A_{i}\neq \varnothing$. $\forall i\neq j~A_{i}\cap A_{j}=\varnothing$, $N=\left|A\right|$ понад 15-20 отриманих оптимальних розбиттів як правило неможливо за прийнятний час (іноді для цього використовується метод гілок і меж), тому на практиці обмежуються субоптимальними розв'язками, отриманими з використанням евристичних алгоритмів.

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

1. Задача розфарбовування графа — кожна множина вершин $V_{i}$ складається з вершин одного кольору, причому вершини одного кольору не мають спільних інцидентних ребер. Зазвичай цікавить відшукання мінімальної розмальовки, що в загальному випадку є завданням класу NP (критерій оптимальності— $n\rightarrow \min$).
2. Завдання визначення числа і складу компонента зв'язності графа.
3. Під час проєктування топології локальної мережі її розбиття на широкомовні домени визначається вимогами продуктивності (критерій оптимальності — обсяг переданого міждоменного трафіку при використанні різних серверів і мережевих служб (доступ до файлових серверів, служб DHCP, WINS, DNS і т. Д.), Обмеження — число портів і пропускна здатність комутаторів, маршрутизаторів і каналів зв'язку, а також вартість).
4. У задачі трасування з'єднань друкованих плат або мікросхем необхідно розбиття вихідної схеми на шари (кожен з яких є планарним графом). Критерії оптимальності — мінімальне число шарів і з'єднань (фактично, собівартість виробництва), обмеження — габаритні розміри і вимоги термічної і електромагнітної сумісності електронних компонентів.
   
5. У задачі розбиття граф-схеми алгоритму на блоки з метою реалізації на багатопроцесорній системі або логічному мультиконтроллером. Критерії оптимальності — мінімальне число блоків, мінімальні ступені дублювання сигналів мікрооперацій і логічних умов, мінімальне число міжмодульних передач управління, мінімальний трафік міжмодульних передач управління і даних; обмеження диктуються використовуваною елементною базою.
   
6. Подання графа у вигляді ярусно-паралельної форми або граф-схеми алгоритму у вигляді безлічі перетинів (безлічі вершин у складі перетинів можуть бути неортогональної).
7. Розбиття графа алгоритму на непересічні підграфи з подальшим їх розміщенням в процесорних елементах або елементах в складі ПЛІС при реалізації конвеєрної обробки даних (балансування навантаження).
   

Методи розбиття графа

• Покоординатне розбиття
• Рекурсивний інерційний метод поділу навпіл
• Розподіл мережі з використанням кривих Пеано
• Розподіл з урахуванням зв'язності (по суті, пошук в ширину)
• Алгоритм Кернігана — Ліна