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

Matching polytope

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

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

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

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

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

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

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

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

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

  • Подмножество F ребер представляет собой соответствие в ГРАММ;
  • Для каждого узла v в V: 1E (v) · 1F ≤ 1.
  • Аграмм · 1F ≤ 1V.

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

Максимизировать 1E · Икс

При условии: Икс через {0,1}м

__________ Аграмм · Икс ≤ 1V.

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

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

Максимизировать 1E · Икс

При условии: Икс ≥ 0E

__________ Аграмм · Икс ≤ 1V.

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

Увеличить x1+ х2+ х3

При условии: x1≥0, х2≥0, х3≥0.

__________ Икс1+ х2≤1, Икс2+ х3≤1, х3+ х1≤1.

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

Многогранник имеет пять углов (крайние точки). Это точки, в которых достигается равенство в 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 - это выпуклый многогранник в р4. Углы этого многогранника: (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 - в нижнем подмножестве. Это означает, что сумма верхнего подмножества и сумма нижнего подмножества равны 1E минус вектор |E| ед. Это означает, что ряды K линейно зависимы, поэтому detK = 0.

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

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

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

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

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

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

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

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

1E · Икс = п/2.

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

Рекомендации

  1. ^ а б c d Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN 0-444-87916-1, МИСТЕР 0859549
  2. ^ "1 Двудольный совпадающий многогранник, стабильный совпадающий многогранник x1 x2 x3 Лекция 10: загрузка в феврале ppt". slideplayer.com. Получено 2020-07-17.

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