Если обычное паросочетание состоит "двоек" (пар) вершин, то "3-ки" можно найти, например, с помощью max flow (как и 2-ки). 3-ка формулируется примерно так: есть вершины L и вершины R, но R состоят из двух типов вершин (R1, R2), нужно скомбинировать вершину из L с R1 и R2. Ну и это можно легко сделать потоком S->R1->L->L'->R2->T. Ну и получается тройка вершин
А если R состоит из k-1 типа и нужно сделать, не 3-ки и k-группы? На первый взгляд схему типа S->R1->L->L'->R2->T применить не выйдет, т.к. поток будет проходить через 2 подряд идущие Ri и Rj и информация потеряется
