Войти
В теории графов, то соответствующий многогранник данного графа является геометрический объект, представляющий возможные паросочетания в графе. Это выпуклый многогранник, каждому углу которого соответствует паросочетание. Это имеет большое теоретическое значение в теории согласования.
Пусть 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 ребер является скалярное произведение 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). Первый угол (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, что является максимальным соответствием. Обратите внимание, что в этом случае все углы имеют целые координаты.
Интегральное соответствие многогранник (обычно называемый просто соответствующий многогранник) графа G, обозначается MP ( G), является многогранник, чьи углы инцидентности векторы интегральных паросочетаниях в G.
MP ( G) всегда содержится в FMP ( G). В приведенных выше примерах:
Приведенный выше пример является частным случаем следующей общей теоремы:
G является двудольным графом тогда и только тогда, когда MP ( G) = FMP ( G) тогда и только тогда, когда все углы FMP ( G) имеют только целые координаты.
Эту теорему можно доказать несколькими способами.
Когда G является двудольным, его матрица инцидентности G является полностью унимодулярная - каждый квадратный подматрицы из этого имеет определитель 0, +1 или 1. Доказательство проведем индукцией по к - размер подматрицы (который мы обозначим через K). База k = 1 следует из определения A G - каждый элемент в ней равен 0 или 1. Для k gt; 1 возможны несколько случаев:
Например, в 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) задаются следующими неравенствами:
Идеальное соответствие многогранник графа G, обозначается PMP ( G), является многогранник, чьи углы инцидентности векторы интегральных совершенных паросочетаниях в G. Очевидно, что ПМП ( G) содержится в MP ( G); Фактически PMP (G) - это грань MP ( G), определяемая равенством:
1 E х = п / 2.
