В теории графов , то соответствующий многогранник данного графа является геометрический объект , представляющий возможные паросочетания в графе . Это выпуклый многогранник, каждому углу которого соответствует паросочетание. Это имеет большое теоретическое значение в теории согласования. [1] : 273–285
Предварительные мероприятия
Векторы и матрицы заболеваемости
Пусть G = ( V , E ) граф с n = | V | узлов и m = | E | края.
Для каждого подмножества 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 , является н - матрицу с размерностью м матрица , в которой каждая строка v является частота вектор 1 Е (В) . Другими словами, каждый элемент v , e в матрице равен 1, если узел v смежен с ребром e , и 0 в противном случае.
Ниже приведены три примера матриц инцидентности: треугольный граф (цикл длины 3), квадратный граф (цикл длины 4) и полный граф с 4 вершинами.
Линейные программы
Для каждого подмножества F ребер скалярное произведение 1 E (v) · 1 F представляет количество ребер в F , смежных с v . Следовательно, следующие утверждения эквивалентны:
- Подмножество ребер F представляет соответствие в G;
- Для каждого узла v в V : 1 E (v) · 1 F ≤ 1.
- G · 1 F ≤ 1 V .
Мощность множества F ребер является скалярное произведение 1 Е · 1 F . Следовательно, максимальное соответствие мощности в G задается следующей целочисленной линейной программой :
Увеличить 1 E · x
При условии: x в {0,1} м
__________ G · х ≤ 1 V .
Многогранник с дробным соответствием
Дробно соответствие многогранник графа G , обозначается ВМП ( G ), является многогранник определяется релаксации указанной выше линейной программы, в которой каждый х может представлять собой фракцию , а не только целое число:
Увеличить 1 E · x
При условии: x ≥ 0 E
__________ G · х ≤ 1 V .
Это линейная программа . Он имеет m ограничений "не менее-0" и n ограничений "менее одного". Множество его допустимых решений представляет собой выпуклый многогранник . Каждая точка в этом многограннике является дробным соответствием . Например, в треугольном графе 3 ребра, а соответствующая линейная программа имеет следующие 6 ограничений:
Увеличить x 1 + x 2 + x 3
При условии: x 1 ≥0, x 2 ≥0, x 3 ≥0 .
__________ x 1 + x 2 ≤1 , x 2 + x 3 ≤1, x 3 + x 1 ≤1.
Этот набор неравенств представляет собой многогранник в R 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 - выпуклый многогранник в R 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 углов представляет собой соответствие размера 2, что является максимальным соответствием. Обратите внимание, что в этом случае все углы имеют целочисленные координаты.
Целочисленный согласующий многогранник
Интегральное соответствие многогранник (обычно называемый просто соответствующий многогранник ) графа G , обозначается MP ( G ), является многогранник , чьи углы инцидентности векторы интегральных паросочетаниях в G.
MP ( G ) всегда содержится в FMP ( G ). В приведенных выше примерах:
- MP треугольного графа строго содержится в его FMP, так как MP не содержит нецелого угла (1/2, 1/2, 1/2).
- МП четырехтактного графа идентичен его FMP, так как все углы FMP являются целыми.
Соответствующие многогранники в двудольном графе
Приведенный выше пример является частным случаем следующей общей теоремы: [1] : 274
G является двудольным графом тогда и только тогда, когда MP ( G ) = FMP ( G ) тогда и только тогда, когда все углы FMP ( G ) имеют только целые координаты.
Эту теорему можно доказать несколькими способами.
Доказательство с использованием матриц
Когда G является двудольным, его матрица инцидентности G является полностью унимодулярная - каждый квадратный подматрицы из этого имеет определитель 0, +1 или 1. Доказательство проведем индукцией по к - размер подматрицы (который мы обозначим через K ). База k = 1 следует из определения A G - каждый элемент в ней равен 0 или 1. Для k > 1 возможны несколько случаев:
- Если в K есть столбец, состоящий только из нулей, то det K = 0.
- Если K имеет столбец с единственной единицей, то det K можно развернуть вокруг этого столбца, и он равен +1 или -1, умноженный на определитель матрицы ( k - 1) на ( k - 1), что по индукции предположение равно 0, +1 или -1.
- В противном случае в каждом столбце K есть две единицы. Поскольку граф двудольный, строки можно разделить на два подмножества, так что в каждом столбце одна единица находится в верхнем подмножестве, а другая 1 - в нижнем подмножестве. Это означает, что сумма верхнего подмножества и сумма нижнего подмножества равны 1 E минус вектор | E | единицы. Это означает, что строки K линейно зависимы, поэтому det K = 0.
Например, в 4-цикле (который является двудольным) det A G = 1. Напротив, в 3-цикле (который не является двудольным) det A G = 2.
Каждый угол FMP ( G ) удовлетворяет набору из m линейно независимых неравенств с равенством. Поэтому, чтобы вычислить координаты угловых мы должны решить систему уравнений , определенных квадратной подматрицы A G . По правилу Крамера решением является рациональное число, знаменатель которого является определителем этой подматрицы. Этот определитель должен быть на +1 или -1; поэтому решение - целочисленный вектор. Следовательно, все угловые координаты целые.
В соответствии с n ограничениями «меньше единицы» координаты углов равны 0 или 1; Таким образом , каждый угол является частота вектор интегрального согласования в G . Следовательно, FMP ( G ) = MP ( G ).
Грани совпадающего многогранника
Грань многогранника является множество ее точек, удовлетворяющих существенное неравенство , определяющее многогранника с равенством. Если многогранник d -мерен, то его грани ( d - 1) -мерны. Для любого графа G фасеты MP ( G ) задаются следующими неравенствами: [1] : 275–279
- х ≥ 0 E
- 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 Очевидно, что ПМП ( G ) содержится в MP ( G ) ; Фактически PMP (G) - это грань MP ( G ), определяемая равенством:
1 E · х = п / 2.
Смотрите также
Рекомендации
- ^ a b c d Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту 0859549
- ^ "1 Двудольный совпадающий многогранник, стабильный совпадающий многогранник x1 x2 x3 Лекция 10: загрузка в феврале ppt" . slideplayer.com . Проверено 17 июля 2020 .