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

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

Предварительные мероприятия

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

Позволять грамм = (V, E) - граф с п = |V| узлы и м = |E| края.

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

Для каждого узла v в V, множество ребер в E рядом с v обозначается E(v). Следовательно, вектор 1_{E (V)} это 1-к-м вектор в каком элементе е равно 1, если край е примыкает к v, и 0 в противном случае. В матрица инцидентности графа, обозначаемого А_грамм, является п-к-м матрица, в которой каждая строка v является вектором инцидентности 1_{E (V)}. Другими словами, каждый элемент v,е в матрице 1, если узел v примыкает к краю е, и 0 в противном случае.

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

{ displaystyle { 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 ребер представляет собой соответствие в ГРАММ;
Для каждого узла v в V: 1_{E (v)} · 1_F ≤ 1.
А_грамм · 1_F ≤ 1_V.

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

Максимизировать 1_E · Икс
При условии: Икс через {0,1}^м
__________ А_грамм · Икс ≤ 1_V.

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

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

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

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

Увеличить x₁+ х₂+ х₃
При условии: x₁≥0, х₂≥0, х₃≥0_.
__________ Икс₁+ х₂≤1, Икс₂+ х₃≤1, х₃+ х₁≤1.

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

Многогранник имеет пять углов (крайние точки ). Это точки, в которых достигается равенство в 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 ребра. Соответствующий LP имеет 4 + 4 = 8 ограничений. FMP - это выпуклый многогранник в р⁴. Углы этого многогранника: (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, что является максимальным соответствием. Обратите внимание, что в этом случае все углы имеют целочисленные координаты.

Интегральный согласованный многогранник

В интегральный согласованный многогранник (обычно называется просто соответствующий многогранник) графа грамм, обозначенный MP (грамм), является многогранником, углами которого являются векторы инцидентности целочисленных паросочетаний в ГРАММ.

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

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

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

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

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

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

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

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

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

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

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

Посредством п ограничения "меньше единицы", координаты угла равны 0 или 1; поэтому каждый угол - это вектор инцидентности интегрального согласования в грамм. Следовательно, FMP (грамм) = МП (грамм).

Грани совпадающего многогранника

А грань многогранника - множество его точек, удовлетворяющих существенному определяющему неравенству многогранника с равенством. Если многогранник d-мерный, то его грани (d - 1) -мерный. Для любого графика грамм, грани МП (грамм) задаются следующими неравенствами:^[1]^:275–279

Икс ≥ 0_E
1_E(v) · Икс ≤ 1 (где v - такая неизолированная вершина, что если v есть только один сосед ты, тогда {ты,v} - связная компонента группы G, и если v имеет ровно двух соседей, то они не смежные).
1_E(S) · Икс ≤ (|S| - 1) / 2 (где S охватывает 2-х соединенный фактор критичный подграф.)

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

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

1_E · Икс = п/2.

Смотрите также

Устойчивый согласующий многогранник

внешняя ссылка

[lp-1] а ^б ^c ^d Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN 0-444-87916-1, МИСТЕР 0859549

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

[1]

[2]