Разложение Галлаи — Эдмондса — это деление вершин графа на три подмножества, которые дают информацию о структуре в графе. и независимо открыли разложение и доказали его основные свойства.
Разложение Галлаи — Эдмондса графа может быть найдено с помощью алгоритма сжатия цветков.
Свойства
Если дан граф , его разложение Галлаи — Эдмондса состоит из трёх непересекающихся множеств вершин, , и , объединение которых есть — множество всех вершин графа . Сначала вершины делятся на существенные вершины (вершины, которые покрываются каждым максимальным паросочетанием в ) и несущественные вершины (вершины, которые остаются непокрытыми по меньшей мере одним максимальным паросочетанием в ). Пусть — множество всех несущественных вершин. Существенные вершины разбиваются на , содержащее все существенные вершины, смежные хотя бы одной вершие из , и , содержащее все существенные вершины, не смежные ни одной вершине из множества .
Принято отождествлять множества , и с подграфами, порождёнными этими множествами. Например, мы говорим « компоненты », имея ввиду компоненты связности подграфа, порождённого множеством .
Разложение Галлаи — Эдмондса имеет следующие свойства:
Компоненты являются фактор-критическими графами — каждая компонента имеет нечётное число вершин, и при удалении любой из этих вершин оставшиеся вершины имеют совершенное паросочетание: паросочетание, которое покрывает все вершины, кроме одной. В частности, каждая компонента имеет почти совершенное паросочетание, которое покрывает все вершины, кроме одной. Подграф, порождённый , имеет совершенное паросочетание. Любое непустое подмножество имеет окрестность в поменьшей мере компонентах . Любое максимальное паросочетание в имеет следующую структуру: оно состоит из почти совершенного паросочетания каждой компоненты , совершенного паросочетания и рёбер, соединяющих все вершины из с различными компонентами . Если имеет компонент, то число рёбер в любом максимальном паросочетании в равно .
Построение
Разложение Галлаи — Эдмондса графа может быть найдено, хотя и не очень эффективно, начав с любого алгоритма поиска максимального паросочетания. По определению, вершина принадлежит тогда и только тогда, когда, когда граф (полученный из удалением ) имеет максимальное паросочетание того же размера, что и . Следовательно, мы можем определить путём вычисления максимального паросочетания в и в для каждой вершины . Дополнение может быть разбито на и непосредственно из определения.
Один из конкретных методов поиска максимального паросочетания в графе — это алгоритм Эдмондса сжатия цветков, и обработка, выполняемая этим алгоритмом, позволяет найти разложение Галлаи — Эдмондса напрямую.
Чтобы найти максимальное паросочетание в графе , алгоритм сжатия цветков начинает с небольшого паросочетания и проходит через несколько итераций, в которых он увеличивает размер паросочетания на одно ребро. Разложение Галлаи — Эдмондса можно получить из работы алгоритма сжатия цветков на последней итерации, когда у алгоритма есть максимальное паросочетание , которое алгоритм не может увеличить.
На каждой итерации алгоритм сжатия цветков проходит от графа к графам меньшего размера путём стягивания подграфов, называемых «цветками» в отдельные вершины. Когда это происходит на последней итерации, цветки обладают особым свойством:
Все вершины цветка являются несущественными вершинами большего графа. Вершина, образованная стягиванием цветка, является несущественной вершиной меньшего графа.
Первое свойство следует из алгоритма — любая вершина цветка является конечной точкой чередующегося пути, который начинается с вершины, не покрытой паросочетанием. Второе свойство следует из первого с помощью следующей леммы.
Пусть — граф, — паросочетание в , а —цикл длиной , содержащий рёбер из и не имеющий общих вершин с остальными ребрами . Построим новый граф из , стянув цикл в одну вершину. Тогда является максимальным паросочетанием в тогда и только тогда, когда является максимальным паросочетанием в .
Из леммы следует также, что когда цветок сжимается, множество несущественных вершин вне цветка остаётся тем же.
Когда каждый цветок сжимается алгоритмом, в результате получаем меньший граф , максимальное паросочетание в того же размера, что и , и чередующийся лес в относительно . В разложение Галлаи — Эдмондса имеет краткое описание. Вершины в классифицируются на внутренние (вершины на нечётном расстоянии в от корня) и внешних вершин (вершины на чётном расстоянии в от корня). — это в точности множество внутренних вершин, а — в точности множество внешних вершин. Вершины , не находящиеся в , образуют .
Сжатие цветков сохраняет несущественные вершины. Поэтому можно найти из , взяв все вершины , которые были сжаты как часть цветка, а также все вершины из . Вершины в и никогда не сжимаются; и .
Обобщения
Разложение Галлаи — Эдмондса является обобщением разложения Далмейджа — Мендельсона из двудольных графов до графов общего вида.
Расширение теоремы о разложении Галлаи — Эдмондса на мультирёберные паросочетания представлено в работе Катаржуны Палух «Capacitated Rank-Maximal Matchings».
Примечания
Категория:Алгоритмы на графах Категория:Паросочетания