Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. Ви можете допомогти вдосконалити цю статтю, погодивши її із чинними мовними стандартами.

Розбиття графа на підграфи (англ. 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]

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