Соответствующий многогранник

В теории графов данного совпадающий многогранник графа — это геометрический объект, представляющий возможные паросочетания в графе . Это выпуклый многогранник, каждый из углов которого соответствует паросочетанию. Это имеет большое теоретическое значение в теории сопоставления. ^[1]^{: 273–285}

Предварительные сведения

Векторы заболеваемости и матрицы

Пусть G = ( V , E ) — граф с n = | В | узлы и m = | Е | края.

Для каждого подмножества U вершин его вектор инцидентности 1 _U представляет собой вектор размера n , в котором элемент v равен 1, если узел v находится в U , и 0 в противном случае. Аналогично, для каждого подмножества F ребер его вектор инцидентности 1 _F представляет собой вектор размера m , в котором элемент e равен 1, если ребро e находится в F, и 0 в противном случае.

Для каждого узла v в V набор ребер в E, смежных с v, обозначается E ( v ). Следовательно, каждый вектор 1 _E(v) представляет собой вектор размером 1 на m , в котором элемент e равен 1, если ребро e смежно с v, и 0 в противном случае. Матрица инцидентности графа, обозначаемая A _G , представляет собой n матрицу размером x m , в которой каждая строка v представляет собой вектор инцидентности 1 _E(V) . Другими словами, каждый элемент v , e в матрице равен 1, если узел v примыкает к ребру e , и 0 в противном случае.

Ниже приведены три примера матриц инцидентности: треугольный граф (цикл длины 3), квадратный граф (цикл длины 4) и полный граф на 4 вершинах.

{\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\\\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0&1&0\\0&1&1&0&0&1\\0&0&1&1&1&0\\1&0&0&1&0&1\\\end{pmatrix}}

Линейные программы

Для каждого подмножества F ребер скалярное произведение 1 _E(v) · 1 _F представляет количество ребер в F , смежных с v . Следовательно, следующие утверждения эквивалентны:

Подмножество F ребер представляет паросочетание в G;
Для каждого узла v в V : 1 _E(v) · 1 _F ≤ 1.
А _г · 1 _F ≤ 1 _В .

Мощность множества F ребер равна скалярному произведению 1 _E · 1 _F _. Следовательно, паросочетание максимальной мощности в G задается следующей целочисленной линейной программой :

Максимизировать 1 _E · x
Зависит от: x в {0,1} ^м
__________ А _Г · x ≤ 1 _В .

Многогранник дробного соответствия

Многогранник дробного соответствия графа G , обозначаемый FMP( G ), представляет собой многогранник, определенный путем релаксации приведенной выше линейной программы, в которой каждый x может быть дробью, а не просто целым числом:

Максимизировать 1 _E · x
При условии: x ≥ 0 _E
__________ А _Г · x ≤ 1 _В .

Это линейная программа . Он имеет m ограничений «по крайней мере 0» и n ограничений «меньше единицы». Множество его допустимых решений представляет собой выпуклый многогранник . Каждая точка в этом многограннике является дробным паросочетанием . Например, в графе треугольника имеется 3 ребра, а соответствующая линейная программа имеет следующие 6 ограничений:

Максимизировать х ₁ + х ₂ + х ₃
При условии: x ₁ ≥0, x ₂ ≥0, x ₃ ≥0 _.
__________ x ₁ +x ₂ ≤1 , x ₂ +x ₃ ≤1, x ₃ +x ₁ ≤1.

Этот набор неравенств представляет собой многогранник в R ³ - трехмерное евклидово пространство.

Многогранник имеет пять углов ( крайних точек ). Это точки, которые достигают равенства в 3 из 6 определяющих неравенств. Углы: (0,0,0), (1,0,0), (0,1,0), (0,0,1) и (1/2,1/2,1/2). ^[2] Первый угол (0,0,0) представляет собой тривиальное (пустое) паросочетание. Следующие три угла (1,0,0), (0,1,0), (0,0,1) представляют три совпадения размера 1. Пятый угол (1/2,1/2,1/2 ) не представляет собой сопоставление — оно представляет собой дробное сопоставление , в котором каждое ребро находится «наполовину внутри, наполовину снаружи». Обратите внимание, что это самое большое дробное паросочетание в этом графе — его вес равен 3/2, в отличие от трех целых паросочетаний, размер которых равен всего 1.

Другой пример: в 4-цикле 4 ребра. Соответствующий ЛП имеет 4+4=8 ограничений. FMP — выпуклый многогранник в R ⁴. Углы этого многогранника равны (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0 ,0,1), (1,0,1,0), (0,1,0,1). Каждый из двух последних углов представляет совпадение размера 2, что является максимальным совпадением. Обратите внимание, что в этом случае все углы имеют целочисленные координаты.

Целочисленный совпадающий многогранник

Целочисленный многогранник паросочетания (обычно называемый просто многогранником согласования ) графа G , обозначаемый MP( G ), представляет собой многогранник, углы которого являются векторами инцидентности целочисленных паросочетаний в G.

MP( G ) всегда содержится в FMP( G ). В приведенных выше примерах:

МП треугольного графа строго содержится в его FMP, поскольку МП не содержит нецелого угла (1/2, 1/2, 1/2).
МП 4-циклового графа идентичен его FMP, поскольку все углы FMP целые.

Соответствующие многогранники в двудольном графе

Приведенный выше пример является частным случаем следующей общей теоремы: ^[1]^: 274

G является двудольным графом тогда и только тогда, когда MP( G ) = FMP( G ) тогда и только тогда, когда все углы FMP( G ) имеют только целочисленные координаты.

Эту теорему можно доказать несколькими способами.

Доказательство с использованием матриц

Когда G двудольная, ее матрица инцидентности A _G - полностью унимодулярна каждая ее квадратная подматрица имеет определитель 0, +1 или -1. Доказательство проводится индукцией по k — размеру подматрицы (которую мы обозначим через K ). База k определения AG _{= 1 следует из} — каждый элемент в ней равен либо 0, либо 1. Для k >1 существует несколько случаев:

Если в K есть столбец, состоящий только из нулей, то det K = 0.
Если K имеет столбец с единственной единицей, то det K можно разложить вокруг этого столбца, и он будет равен либо +1, либо -1 умноженному на определитель матрицы ( k - 1) на ( k - 1), что по индукции предположение равно 0 или +1 или -1.
В противном случае каждый столбец в K имеет две единицы. Поскольку граф двудольный, строки можно разделить на два подмножества, так что в каждом столбце одна единица находится в верхнем подмножестве, а другая 1 — в нижнем подмножестве. Это означает, что сумма верхнего подмножества и сумма нижнего подмножества равны 1 _E минус вектор | Е | те. Это означает, что строки K линейно зависимы, поэтому det K = 0.

Например, в 4-цикле (который является двудольным) det A _G = 1. Напротив, в 3-цикле (который не является двудольным) det A _G = 2.

Каждый угол FMP( G ) удовлетворяет набору из m линейно независимых неравенств с равенством. нам нужно решить систему уравнений, заданную квадратной подматрицей AG _{Следовательно, чтобы вычислить угловые координаты ,} . По правилу Крамера решением является рациональное число, в котором знаменателем является определитель этой подматрицы. Этот определитель должен быть равен +1 или -1; следовательно, решение представляет собой целочисленный вектор. Поэтому все угловые координаты являются целыми числами.

В соответствии с n ограничениями «меньше единицы» угловые координаты равны либо 0, либо 1; поэтому каждый угол является вектором инцидентности интегрального паросочетания в G . Следовательно, FMP( G ) = MP( G ).

Грани соответствующего многогранника

Фасета многогранника - это набор его точек, которые удовлетворяют существенному определяющему неравенству многогранника с равенством. Если многогранник d -мерен, то его грани ( d − 1)-мерны. Для любого графа G фасеты MP( G ) задаются следующими неравенствами: ^[1]^{: 275–279}

х ≥ 0 _Е
1 _{E ( v )} · x ≤ 1 (где v — неизолированная вершина такая, что, если v имеет только одного соседа u , то { u , v } — компонент связности G, и если v имеет ровно два соседа, тогда они не соседние).
1 _{E ( S )} · x ≤ (| S | − 1)/2 (где S охватывает 2-связный фактор-критический подграф.)

Идеально совпадающий многогранник

Многогранник идеального паросочетания графа G , обозначаемый PMP( G ), — это многогранник, углы которого являются векторами инцидентности целочисленных совершенных паросочетаний в G. ^[1]^: 274 Очевидно, PMP( G ) содержится в MP( G ); Фактически PMP(G) — это грань MP( G ), определяемая равенством:

1 _Е · х = n /2.

Эдмондс ^[3] доказал, что для любого графа G PMP(G) можно описать следующими ограничениями:

1 _E(v) · x = 1 для всех v в V (- ровно одно ребро, смежное с v, находится в паросочетании)
1 _E(W) · x ≥ 1 для любого подмножества W из V такого, что |W| нечетное (- хотя бы одно ребро должно соединять W с V\W). Эти ограничения называются ограничениями нечетного разреза .
х ≥ 0 _Е

Используя эту характеристику и лемму Фаркаша , можно получить хорошую характеристику графов, имеющих идеальное паросочетание. ^[4]^: 206 Решая алгоритмические задачи на выпуклых множествах , можно найти идеальное паросочетание минимального веса. ^[4]^: 206--208

См. также

Стабильный совпадающий многогранник

Ссылки

^ Jump up to: ^а ^б ^с ^д Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549
^ «1 двудольный совпадающий многогранник, устойчивый совпадающий многогранник x1 x2 x3, лекция 10: загрузка ppt за февраль» . Slideplayer.com . Проверено 17 июля 2020 г.
^ Эдмондс, Джек (январь 1965 г.). «Максимальное совпадение и многогранник с 0,1-вершинами» (PDF) . Журнал исследований Национального бюро стандартов, раздел B. 69B (1 и 2): 125. doi : 10.6028/jres.069B.013 . ISSN 0022-4340 .
^ Jump up to: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

Внешние ссылки

[lp-1] Jump up to: ^а ^б ^с ^д Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 МР 0859549

[2] «1 двудольный совпадающий многогранник, устойчивый совпадающий многогранник x1 x2 x3, лекция 10: загрузка ppt за февраль» . Slideplayer.com . Проверено 17 июля 2020 г.

[3] Эдмондс, Джек (январь 1965 г.). «Максимальное совпадение и многогранник с 0,1-вершинами» (PDF) . Журнал исследований Национального бюро стандартов, раздел B. 69B (1 и 2): 125. doi : 10.6028/jres.069B.013 . ISSN 0022-4340 .

[:0-4] Jump up to: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[1]

[2]

[3]

[4]