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

Один из примеров применения принципа разбиения на пары в графах — алгоритм Кернигана — Лина. 1 Он предполагает обмен вершинами между подмножествами имеющегося разбиения графа. 1 Для этого из вершин, которые ещё не были переставлены на данной итерации, формируются все возможные пары (в парах должно присутствовать по одной вершине из каждой части имеющегося разбиения графа). 1 Затем каждая пара поочерёдно используется для обмена вершинами между частями графа для получения множества новых вариантов деления. 1

Также принцип разбиения на пары используется в задачах о максимальном паросочетании. 4 Например, для распределения имеющихся подарков так, чтобы они удовлетворили пожеланиям максимального числа одариваемых. 4 Для решения задачи используется двудольный граф: вершины его делятся на две части, с одной стороны находятся элементы одного множества (например, люди), с другой стороны — элементы второго множества (например, подарки). 4 Далее от каждой вершины левой доли (от каждого человека) проводятся рёбра к нескольким вершинам второй доли (конкретно к тем подаркам, которые можно подарить этому человеку, чтобы он остался доволен). 4 Затем выбирается множество рёбер так, чтобы каждое из них соединяло ровно одного человека с одним подарком. 4