Галлая

Cтраница 2

На этом этапе легко определить разбиение множества вершин графа G на четыре класса, аналогичное разбиению Галлаи - Эдмондса. Однако оказывается, что несколько труднее вывести важные свойства этого разбиения. Впрочем, определение разбиения достаточно простое. В случае 1-паросочетания мы основываем нашу декомпозицию на том, покрывается или нет та или иная вершина всеми наибольшими паросочетаниями. [16]

Утверждения ( 2), ( 3) и ( 4) следуют непосредственно из свойств декомпозиции Галлаи - Эдмондса и того факта, что G - двудольный граф. [17]

В завершение этого раздела мы упомянем задачу ( решенную совсем недавно), для которой структурная теорема Галлаи - Эдмондса является неким естественным обрамлением. Эта задача состоит в следующем. [18]

C ( G - х) с A ( G - z)), то, по теореме Галлаи - Эдмондса, все такие ребра являются запрещенными. [19]

Идею / - фактора и близко связанную с ней проблему о поиске подграфа с заданными степенями исследовали также Оре и Галлаи в 50 - е годы и в начале 60 - х годов. [20]

Доказательство теоремы 5.5.24. Сначала заметим, что если р 1 ( G) - нечетное число, то на основании теоремы Галлаи - Эдмондса граф G, будучи вершинно транзитивным, является критическим графом. [21]

Он не столь эффективен, как алгоритм Эдмондса, но мы поместили его здесь потому, что он убедительно демонстрирует, как может структурный результат типа теоремы Галлаи - Эдмондса привести к созданию конкретного алгоритма. [22]

Тогда, в силу части ( с), A ( G - S) - Z - C ( G - S) и, по теореме Галлаи - Эдмондса, граф G - S состоит из факторно-критических компонент. Поскольку S является в графе G барьером, то должно существовать ровно 5 таких компонент. [23]

Простая цепь в графе G называется А-цепью, если ее концевые вершины принадлежат множеству Л, но ни одна из ее внутренних вершин в А не содержится. Галлаи ( 1961) решил задачу отыскания максимального числа вершинно непересекающихся А-цепей сведением ее к задаче о паросочетании. [24]

Давцер снизил это число до 4 ( причем последний результат уже является окончательным), однако пока это нигде не опубликовано. По поводу задачи Галлаи см. книгу [18] и 2 - е издание книги [24], где имеются также иные варианты этой задачи и указана дополнительная литература. [25]

Турниры с небольшим числом вершин. [26]

Селе [1] обобщил этот результат, доказав, что каждый турнир имеет нечетное число остовных путей. Другое обобщение теоремы Редей дали Галлаи и Мильгрэм [ Ц, доказавшие, что в любом направленном графе D существует набор из не более чем РО ( D) непересекающихся по вершинам путей, покрывающих множество V ( D) его вершин. [27]

Дираку: если G - граф без разделяющих вершин, то либо длина максимальных простых циклов удовлетворяет неравенству k 2ро, либо граф имеет гамнльтонов цикл. Другое доказательство теоремы Дирака дали Эрдеш и Галлаи; наша аргументация является небольшим усовершенствованием их метода. [28]

Минимальный элементарный двудольный граф с хордой х. [29]

Далмеджа и Мендельсона ( 1958, 1959) о канонической декомпозиции произвольных двудольных графов. Было показано, как можно вывести их результаты из теоремы Галлаи - Эдмондса. В частности, мы доказали, что каждый двудольный граф единственным образом разлагается на три вершин-но непересекающихся ( в совокупности) подграфа, которые, возможно, определенным способом соединяются дополнительными ребрами. Два из этих графов являются двудольными графами с положительным избытком ( о таких графах речь шла в разд. [30]

Страницы: 1 2 3 4