Cтраница 1
Колосковые декомпозиции с разнообразными специальными свойствами пригодятся нам впоследствии. [1]
Двудольную колосковую декомпозицию иногда удобно описывать с помощью набора подграфов ( G0 Gi... G), где GO х и G, х PI Pi при 1 г г. В силу теоремы 4.1.6 каждый граф G является элементарным двудольным графом. [2]
Строя двудольную колосковую декомпозицию двудольного графа, мы доказываем тем самым, что граф является элементарным. Таким образом, свойство быть элементарным графом принадлежит классу NP. В действительности, это свойство содержится в классе Р, ибо условие ( ii) в теореме 4.1.1 можно проверить за полиномиальное число шагов. Довольно часто существование у графа G колосковой декомпозиции удобнее устанавливать, доказывая его элементарность. [3]
В каждой колосковой декомпозиции минимального факторно-критического графа все ости собственные. [4]
Следовательно, хотя колосковая декомпозиция может не быть единственной, но число остей в каждой такой декомпозиции всегда одно и то же. Рг, где PI обозначает начальный четный простой цикл. [5]
Такие правила гарантируют разнообразные эластичные свойства получаемых колосковых декомпозиций. [6]
Одна из возможностей сделать это - хранить колосковую декомпозицию цветков. Поэтому сейчас мы обсудим, как можно экономным способом хранить колосковую декомпозицию факторно-критических графов. [7]
Каждый недвудольный 1-расширяемый граф G имеет неулучшаемую градуированную колосковую декомпозицию ( Go, GI, G-2, Сз, , Gm G), где GO - отдельное ребро и GI - четный цикл, такую, что либо граф GI, либо граф Сз получается при двух-остевом добавлении. [8]
В частности, допустим, что имеется неулучшаемая колосковая декомпозиция произвольного 1-расширяемого графа, начинающаяся с ребра. Выполним несколько ( по крайней мере одно) одноостевых добавлений; при всех таких одноостевых шагах текущий граф будет оставаться двудольным. Однако первое же двухостевое добавление даст недвудольный граф. Поэтому нахождение эластичного 1-расширяемого недвудольного подграфа с наименьшим цикломатическим числом эквивалентно выявлению того, как скоро появится двухостевое добавление в неулучшаемой колосковой декомпозиции. Ответ дает следующая теорема. [9]
Это утверждение очевидно, ибо подграф G имеет градуированную колосковую декомпозицию и ее мы можем просто продолжить, чтобы получить G. В частности, каждый 1-расширяемый граф имеет градуированную колосковую декомпозицию, начинающуюся с произвольного заданного ребра. [10]
Показать, что отображения ц и ( р определяют колосковую декомпозицию единственным образом. [11]
В завершение этого раздела мы применим средства, предоставляемые колосковой декомпозицией, для изучения свойств минимальных элементарных графов. [12]
Мы уже видели, что для факторно-критических графов существует теория колосковой декомпозиции, абсолютно аналогичная соответствующей теории для элементарных двудольных графов. Эту технику можно весьма успешно применить для изучения минимальных факторно-критических графов, и полученные результаты совершенно аналогичны результатам, относящимся к минимальным элементарным двудольным графам. [13]
В свете изложенного естественно спросить, есть ли что-нибудь подобное рассмотренной колосковой декомпозиции, могущее оказаться полезным для случая недвудольных элементарных графов. К сожалению, не всегда удается получить декомпозицию такого графа в виде цепочки элементарных подграфов, каждый из которых строится из предыдущего путем добавления одной ости. G - 1 получается из графа G, путем добавления одной или двух остей. [14]
Если G - минимальный элементарный двудольный граф, то рассмотрим его произвольную колосковую декомпозицию, начинающуюся с какого-либо эластичного цикла. Всякая хорда в этом цикле была бы остью, что, как мы видели, невозможно. [15]