Cтраница 1
Галлаи ( 1963а) доказал, что для связных графов справедливо также и обратное утверждение. [1]
Галлаи [2] доказал, что это справедливо всегда. [2]
Рассмотрим декомпозицию Галлаи - Эдмондса для данного графа G. Через G обозначим двудольный граф, получаемый из G удалением входящих в C ( G) вершин и стягиваемых множеством A ( G) ребер и сжатием каждой связной компоненты графа ( D ( G)) в одиночную вершину. [3]
Итак, каноническая декомпозиция Галлаи - Эдмондса тривиальна в трех случаях: для факторно-критических графов, для графов, имеющих совершенные паросочетания, и для двудольных графов с положительным избытком. С другой стороны, данный факт говорит о том, что каждый граф может быть построен из графов этих трех типов. [4]
Гипотеза о возможности такой классификации была высказана Галлаи. [5]
Хайошем [130], Хайналом и Шураньи [129], Галлаи и другими математиками изучались свойства таких графов, которые допускают следующее представление с помощью систем интервалов на прямой: вершины графа отвечают интервалам, причем две вершины смежны тогда и только тогда, когда соответствующие им интервалы различны и имеют непустое пересечение. Один из критериев такой представимости графа, выражаемый в терминах цепей и циклов, установлен Леккеркеркером и; Боландом [151] в связи с задачами генетики. [6]
Один из нескольких важных вырожденных случаев в теореме Галлаи - Эдмондса возникает тогда, когда рассматриваемый граф имеет совершенное паросочетание. Однако Коциг уже начал закладывать основы канонического представления таких графов в серии статей, вышедших в 1959 и 1960 гг. К сожалению, эти важные работы остались незамеченными, поскольку были написаны на словацком языке. [7]
Приведем два вспомогательных утверждения, которые установили Эрдеш и Галлаи; эти утверждения понадобятся нам в дальнейшем. [8]
Приводимые ниже упражнения иллюстрируют еще некоторые приложения структурной теоремы Галлаи - Эдмондса. [9]
Алгоритм Эдмондса дает нам как побочный продукт важную структурную теорему Галлаи - Эдмондса. Представляемый далее алгоритм, так сказать, обращает эту взаимосвязь и показывает, что результат Галлаи - Эдмондса может служить в качестве отправной точки для алгоритма построения паросочетаний. [10]
Сравнить эти результаты с теми, которые получаются с помощью теоремы Эрдеша - Галлаи. [11]
Теперь мы можем объяснить более точно глубину различия между теоремой Кенига и тождеством Галлаи, отмеченную в начале этой вставки: формула f ( G) р - p ( G) не дает хорошую характеризацию для числа паросочетания. Но это значит, что вершины G не могут быть покрыты менее, чем р - k ребрами, и быстрого способа убедить короля Артура в этом не существует. [12]
Следующую простую лемму можно рассматриватцкак обратное ( в некотором смысле) утверждение для структурной теоремы Галлаи - Эдмондса. [13]
Следующие два результата демонстрируют некоторые параллели с теми нашими исследованиями, которые касались вырожденных случаев декомпозиции Галлаи - Эдмондса. [14]
Основным предметом наших рассмотрений будет разработка структурной теории, аналогичной той, которая связана с декомпозицией Галлаи - Эдмондса. [15]