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

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

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

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

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

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

Примітки

1. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.
2. Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
3. Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.
4. Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с.
5. Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с.
6. Ватутин Э.
7. Каляев И. А., Левин И. И., Семерников Е. А., Шмойлов В. И. Реконфигурируемые мультиконвейерные вычислительные структуры: 2-е издание. Ростов н/Д: изд-во ЮНЦ РАН, 2009. 344 с.
8. Каляев И. А., Левин И. И. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач обработки информации и управления // Пленарные доклады 5-й международной конференции «Параллельные вычисления и задачи управления» (PACO'10). М.: ИПУ РАН, 2010 г. С. 23—37.
9. INTUIT.ru: Курс: Теория и практика ..: Лекция № 10: Параллельные методы на графах^[недоступне посилання з квітня 2019]