Cтраница 3
Доказать, что каждый связный граф с верши-но-транзитивной группой автоморфизмов либо является факторно-критическим, либо имеет совершенное паросочетание. Указание: все вершины должны принадлежать одному и тому же классу в декомпозиции Галлаи - Эдмондса. [31]
Алгоритм Эдмондса дает нам как побочный продукт важную структурную теорему Галлаи - Эдмондса. Представляемый далее алгоритм, так сказать, обращает эту взаимосвязь и показывает, что результат Галлаи - Эдмондса может служить в качестве отправной точки для алгоритма построения паросочетаний. [32]
Множество X С V ( G) назовем экстремальным, если для него в лемме 3.3.1 выполняется равенство, т.е. если def ( G-X) def ( G) X. Заметим, что пустое множество всегда является экстремальным, как и множество A ( G) в декомпозиции Галлаи - Эдмондса. Несколько простых свойств экстремальных множеств указаны в следующей серии упражнений. [33]
Необходимость очевидна: нужно обычным способом подсчитать ребра, идущие из G - X в X. Рассмотрим декомпозицию Галлаи-Эдмондса для графа G и двудольный граф G, определенный в части ( с) структурной теоремы Галлаи - Эдмондса 3.2.1. Пусть U - множество вершин в G, являющихся сжатыми копиями тех компонент из ( D ( G)), которые не имеют совершенных 2-паросочетаний без / - С-угольников. V ( G), поскольку компонента G; является факторно-критической. [34]
Более того, в D существует / ровно одна вершина d, смежная с а. Тогда М покрывает вершину а ребром из графа G [ Ai U АЗ ], что противоречит части ( d) теоремы Галлаи - Эдмондса. [35]
В ней представлены как классические методы и алгоритмы, так и новые подходы и конструкции: NP-полнота, теоремы Бержа, Татта, Галлаи - Эдмондса и др. Книга имеет явно энциклопедический характер, отличается прикладной направленностью и требует лишь минимальной математической подготовки. [36]
Если эквипаросочетательный граф G не имеет совершенного па-росочетания, то задача становится более интересной. Пусть V ( G) D ( G) ( JA ( G) ( JC ( G) ( D, А, С) есть декомпозиция Галлаи - Эдмонд-са графа G. [37]
Объективным показателем эффективности проведения аутогенной тренировки служат результаты деятельности, а также изменения температуры кожи, частоты пульса, дыхания, давления крови, общего самочувствия. Положительный опыт самоуправления вырабатывает привычку и потребность действовать, несмотря на опасность и препятствия, разумно, в соответствии с ситуацией. Галлая за психологическим механизмом вытеснения из сознания эмоций, вызываемых опасностью. [38]
Весьма глубокий результат Эдмондса и Фалкерсона ( 1965) гласит, что любой матроид паросочетаний трансверсален. К сожалению, прямое доказательство этого факта пока не найдено. Известное нам доказательство использует структурную теорему Галлаи - Эдмондса ( теорему 3.2.1), которая будет основной темой следующего раздела. [39]
Из этой теоремы следует другая теорема, принадлежащая Дираку: если G - граф без разделяющих вершин, то либо длина максимальных простых циклов удовлетворяет неравенству k 2pri, либо граф имеет га-мильтонов цикл. Другое доказательство георемы Дирака дали Эрдеш и Галлаи; наша аргументация является небольшим усовершенствованием их метода. [40]
Было замечено, что если нас интересует, скажем, число наибольших паросочетаний, то следует решать сначала соответствующую задачу для более специального класса графов, а именно графов с совершенными паросочетаниями. Подграф C ( G) из декомпозиции Галлаи - Эдмондса является как раз таким графом, а для графов с совершенными паросочетаниями выполняется равенство: C ( G) G. Следовательно, в этом случае теорема Галлаи - Эдмондса ничего интересного нам не дает. Поэтому нужно заняться специально изучением графов, обладающих совершенными паросочетаниями, что и будет предпринято в данной и следующей главах. В настоящей главе рассматриваются двудольные графы. [41]
Заметим, что теорема 12.2.3 может служить для получения новых доказательств некоторых предыдущих результатов. Как отмечалось выше, двудольные графы являются совершенными, и поэтому, согласно теореме 12.2.3, таковы и их дополнения. Она, в свою очередь, с помощью тождеств Галлаи ( леммы 1.0.1 и 1.0.2) влечет минимаксную теорему Кенига ( теорема 1.1.1), которая гласит, что дополнения реберных графов двудольных графов являются совершенными. [42]
Пусть G - произвольный граф, содержащий или не содержащий совершенное паросочетание. Старое понятие, которое нам здесь пригодится, было введено в разд. Таким образом, множество A ( G) в декомпозиции Галлаи - Эдмондса графа G всегда является барьером. [43]
Мы также рассмотрим три других алгоритмических подхода. Два из них полиномиальные; первый - это программа, основанная на декомпозиции Галлаи - Эдмондса; второй использует весьма современный метод эллипсоидов, развитый в линейном программировании. Третий подход, предложенный Падбер-гом и Рао ( 1982), в наихудшем случае полиномиальным не является; однако на практике он, кажется, может конкурировать с алгоритмом Эдмондса. [44]
Год 1964 ознаменован появлением статьи Галл аи, содержащей один из центральных результатов этой книги ( см. гл. Получить такую декомпозицию эффективно позволяет полиномиальный алгоритм Эд-мондса для построения паросочетаний в общих графах, который появился в 1965 г. В настоящей книге мы решили называть этот важный результат структурной теоремой Галлаи - Эдмондса. [45]