Cтраница 2
Gm) графа G называется длиннейшей, если ее длина максимальна среди длин всех градуированных колосковых декомпозиций графа G. К сожалению, мы не знаем не только, как эффективно находить длиннейшую декомпозицию, но и как проверить, является ли данная декомпозиция длиннейшей. Поэтому мы обратимся к некоторым другим типам декомпозиций, которые связаны с этим типом, но легче поддаются обработке. [16]
Р-4) Ограниченные на множество вершин цветка указатели ц и ( р определяют его колосковую декомпозицию, начинающуюся с его базовой вершины. [17]
Граф G является элементарным и двудольным тогда и только тогда, когда он допускает двудольную колосковую декомпозицию. [18]
Из теоремы 5.4.2 и только что установленного результата следует, что каждый 1-расширяемый граф имеет неулучшаемую колосковую декомпозицию, начинающуюся с произвольного ребра ( или, что эквивалентно, с четного цикла), в которой каждый класс G - i образуется из предыдущего класса GJ добавлением одной или двух остей. [19]
Во-первых, чем длиннее градуированная колосковая декомпозиция, тем, вообще говоря, меньше остей будет в большинстве классов и поэтому иногда легче проследить за тем, что происходит с конкретными свойствами и параметрами при построении графа. Оказывается, эта оценка достижима. В самом деле, рассмотрим граф G, изображенный на рис. 5.4.4. Если р - число вершин в этом графе, то показанная на рисунке градуированная колосковая декомпозиция является неулучшаемой и имеет k l р / 2 1 классов. Возможна ли другая колосковая декомпозиция с более чем р / 1 классами. Значит, такой декомпозиции нет. Заметим, что в указанной нами декомпозиции каждый класс, за исключением двух первых, содержит ровно две ости. Из приводимой ниже теоремы 5.4.6 следует, что такая ситуация имеет место для любой неулучшаемой колосковой декомпозиции этого графа: все классы, кроме двух первых, состоят в точности из двух остей. [20]
Gm) - неулучшаемая градуированная колосковая декомпозиция 1-расширя-емого графа С, то для каждого i, 0 г m, граф Gi i получается из графа d добавлением не более двух остей. [21]
Это утверждение очевидно, ибо подграф G имеет градуированную колосковую декомпозицию и ее мы можем просто продолжить, чтобы получить G. В частности, каждый 1-расширяемый граф имеет градуированную колосковую декомпозицию, начинающуюся с произвольного заданного ребра. [22]
Введем новый вид декомпозиции, которая называется колосковой декомпозицией. [23]
Здесь уместно сделать одно тонкое ( и важное) замечание. В приведенном сейчас доказательстве мы видели, что колосковую декомпозицию 1-расширяемого графа G можно получить, начав с любого эластичного подграфа и добавляя на каждом шаге процедуры по одной ости. [24]
Выражаясь точнее, только что определенную декомпозицию следует называть двудольной колосковой декомпозицией. [25]
Одна из возможностей сделать это - хранить колосковую декомпозицию цветков. Поэтому сейчас мы обсудим, как можно экономным способом хранить колосковую декомпозицию факторно-критических графов. [26]
Колосковая система графа G относительно G - это множество вершинно не пересекающихся простых цепей нечетной длины в графе G, каждая из которых открыто не пересекается с подграфом G, но имеет в G обе концевые вершины. G и для каждого г подграф G - i получается из d присоединением колосковой относительно GJ системы. Отметим теперь, что только 1-расширяемые графы могут иметь градуированную колосковую декомпозицию. Целое число га 1 называют длиной декомпозиции. [27]
Мы называем подграф Н графа G эластичным, если граф G-V ( H) имеет совершенное паросочетание. Пусть ( Go, - - -, Gr i, Gr G) - набор графов, задающий какую-то колосковую декомпозицию. [28]
Строя двудольную колосковую декомпозицию двудольного графа, мы доказываем тем самым, что граф является элементарным. Таким образом, свойство быть элементарным графом принадлежит классу NP. В действительности, это свойство содержится в классе Р, ибо условие ( ii) в теореме 4.1.1 можно проверить за полиномиальное число шагов. Довольно часто существование у графа G колосковой декомпозиции удобнее устанавливать, доказывая его элементарность. [29]
В частности, допустим, что имеется неулучшаемая колосковая декомпозиция произвольного 1-расширяемого графа, начинающаяся с ребра. Выполним несколько ( по крайней мере одно) одноостевых добавлений; при всех таких одноостевых шагах текущий граф будет оставаться двудольным. Однако первое же двухостевое добавление даст недвудольный граф. Поэтому нахождение эластичного 1-расширяемого недвудольного подграфа с наименьшим цикломатическим числом эквивалентно выявлению того, как скоро появится двухостевое добавление в неулучшаемой колосковой декомпозиции. Ответ дает следующая теорема. [30]