Колосковая декомпозиция
Cтраница 3
Во-первых, чем длиннее градуированная колосковая декомпозиция, тем, вообще говоря, меньше остей будет в большинстве классов и поэтому иногда легче проследить за тем, что происходит с конкретными свойствами и параметрами при построении графа. Оказывается, эта оценка достижима. В самом деле, рассмотрим граф G, изображенный на рис. 5.4.4. Если р - число вершин в этом графе, то показанная на рисунке градуированная колосковая декомпозиция является неулучшаемой и имеет k l р / 2 1 классов. Возможна ли другая колосковая декомпозиция с более чем р / 1 классами. Значит, такой декомпозиции нет. Заметим, что в указанной нами декомпозиции каждый класс, за исключением двух первых, содержит ровно две ости. Из приводимой ниже теоремы 5.4.6 следует, что такая ситуация имеет место для любой неулучшаемой колосковой декомпозиции этого графа: все классы, кроме двух первых, состоят в точности из двух остей. [31]
Во-первых, чем длиннее градуированная колосковая декомпозиция, тем, вообще говоря, меньше остей будет в большинстве классов и поэтому иногда легче проследить за тем, что происходит с конкретными свойствами и параметрами при построении графа. Оказывается, эта оценка достижима. В самом деле, рассмотрим граф G, изображенный на рис. 5.4.4. Если р - число вершин в этом графе, то показанная на рисунке градуированная колосковая декомпозиция является неулучшаемой и имеет k l р / 2 1 классов. Возможна ли другая колосковая декомпозиция с более чем р / 1 классами. Значит, такой декомпозиции нет. Заметим, что в указанной нами декомпозиции каждый класс, за исключением двух первых, содержит ровно две ости. Из приводимой ниже теоремы 5.4.6 следует, что такая ситуация имеет место для любой неулучшаемой колосковой декомпозиции этого графа: все классы, кроме двух первых, состоят в точности из двух остей. [32]
 |
Экстремальное семейство. [33] |
Все результаты о колосковой структуре 1-расширяемых графов, полученные в предыдущих разделах этой главы, справедливы, конечно, и для бикритических графов. Заметим, что в то время как 1-расширяемые графы обязательно 2-связны, факторно-критические графы, хотя они и являются 2-реберносвязными, могут иметь точки сочленения. Поэтому мы должны так расширить наше понятие ости, чтобы допустить случай совпадения двух концевых вершин у ости. Тогда легко будет получить колосковую декомпозицию произвольного факторно-критического графа. [34]
На самом деле, чересчур просто, чтобы оказаться для нас достаточно полезным. Однако, улучшив немного нашу технику, мы сможем получить более мощную колосковую теорему, которая и в самом деле позволит нам установить более тонкую нижнюю оценку для числа почти совершенных паросочетаний в факторно-критических графах. Сейчас мы покажем, что любой такой граф имеет колосковую декомпозицию, у которой каждая добавляемая ость является открытой. [35]
Во-первых, чем длиннее градуированная колосковая декомпозиция, тем, вообще говоря, меньше остей будет в большинстве классов и поэтому иногда легче проследить за тем, что происходит с конкретными свойствами и параметрами при построении графа. Оказывается, эта оценка достижима. В самом деле, рассмотрим граф G, изображенный на рис. 5.4.4. Если р - число вершин в этом графе, то показанная на рисунке градуированная колосковая декомпозиция является неулучшаемой и имеет k l р / 2 1 классов. Возможна ли другая колосковая декомпозиция с более чем р / 1 классами. Значит, такой декомпозиции нет. Заметим, что в указанной нами декомпозиции каждый класс, за исключением двух первых, содержит ровно две ости. Из приводимой ниже теоремы 5.4.6 следует, что такая ситуация имеет место для любой неулучшаемой колосковой декомпозиции этого графа: все классы, кроме двух первых, состоят в точности из двух остей. [36]
Страницы: 1 2 3