Во-первых, чем длиннее градуированная колосковая декомпозиция, тем, вообще говоря, меньше остей будет в большинстве классов ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Ловас Л.N.
Прикладные задачи теории графов
Во-первых, чем длиннее градуированная колосковая декомпозиция, тем, вообще говоря, меньше остей будет в большинстве классов и поэтому иногда легче проследить за тем, что происходит с конкретными свойствами и параметрами при построении графа. Оказывается, эта оценка достижима. В самом деле, рассмотрим граф G, изображенный на рис. 5.4.4. Если р - число вершин в этом графе, то показанная на рисунке градуированная колосковая декомпозиция является неулучшаемой и имеет k l р / 2 1 классов. Возможна ли другая колосковая декомпозиция с более чем р / 1 классами. Значит, такой декомпозиции нет. Заметим, что в указанной нами декомпозиции каждый класс, за исключением двух первых, содержит ровно две ости. Из приводимой ниже теоремы 5.4.6 следует, что такая ситуация имеет место для любой неулучшаемой колосковой декомпозиции этого графа: все классы, кроме двух первых, состоят в точности из двух остей.