Гаммоид

Абстракция непересекающихся путей в ориентированных графах

В теории матроидов , области математики, гаммоид — это определенный вид матроида, описывающий наборы вершин , которые могут быть достигнуты с помощью вершинно-непересекающихся путей в ориентированном графе .

Понятие гаммоида было введено и показано, что это матроид, Хейзелом Перфектом  (1968), на основе соображений, связанных с теоремой Менгера, характеризующей препятствия к существованию систем непересекающихся путей. ^[1] Гаммоиды получили свое название от Пима (1969) ^[2] и были более подробно изучены Мейсоном (1972). ^[3]

Определение

Пусть будет направленным графом, будет набором начальных вершин и будет набором конечных вершин (не обязательно не пересекающихся с ). Гаммоид, полученный из этих данных, имеет в качестве своего набора элементов. Подмножество из является независимым в, если существует набор вершинно-непересекающихся путей, все начальные точки которых принадлежат и чьи конечные точки точно . ^[4] ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle \Gamma }$ ${\displaystyle T}$ ${\displaystyle I}$ ${\displaystyle T}$ ${\displaystyle \Gamma }$ ${\displaystyle S}$ ${\displaystyle I}$

Строгий гаммоид — это гаммоид, в котором множество конечных вершин состоит из каждой вершины в . Таким образом, гаммоид — это ограничение строгого гаммоида на подмножество его элементов. ^{[4] [5]} ${\displaystyle T}$ ${\displaystyle G}$

Пример

Рассмотрим равномерный матроид на множестве элементов, в котором каждое множество из или меньшего числа элементов является независимым. Одним из способов представления этого матроида как гаммоида было бы формирование полного двудольного графа с множеством вершин с одной стороны двудольного разбиения, с множеством вершин с другой стороны двудольного разбиения, и с каждым ребром, направленным от к В этом графе подмножество является множеством конечных точек множества непересекающихся путей тогда и только тогда, когда оно имеет или меньше вершин, иначе не хватит вершин для начала путей. Специальная структура этого графа показывает, что равномерный матроид является трансверсальным матроидом , а также гаммоидом. ^[6] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle K_{r,n}}$ ${\displaystyle S}$ ${\displaystyle r}$ ${\displaystyle T}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle T.}$ ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle S}$

В качестве альтернативы тот же однородный матроид может быть представлен как гаммоид на меньшем графе, только с вершинами, выбрав подмножество вершин и соединив каждую из выбранных вершин с каждой другой вершиной в графе. Опять же, подмножество вершин графа может быть конечными точками непересекающихся путей тогда и только тогда, когда оно имеет или меньше вершин, потому что в противном случае не будет достаточно вершин, которые могут быть началами путей. В этом графе каждая вершина соответствует элементу матроида, показывая, что однородный матроид является строгим гаммоидом. ^[7] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle r}$ ${\displaystyle r}$

Теорема Менгера и ранг гаммоида

Ранг множества в гаммоиде определяется из графа и подмножеств вершин и , по определению, является максимальным числом вершинно-непересекающихся путей из в . По теореме Менгера он также равен минимальной мощности множества , пересекающего каждый путь из в . ^[4] ${\displaystyle X\subset T}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle X}$

Связь с трансверсальными матроидами

Трансверсальный матроид определяется из семейства множеств : его элементы являются элементами множеств, и множество этих элементов является независимым всякий раз, когда существует однозначное соответствие элементов непересекающимся множествам, их содержащим, называемое системой различных представителей . Эквивалентно, трансверсальный матроид может быть представлен специальным видом гаммоида, определяемого из направленного двудольного графа , который имеет вершину в для каждого множества, вершину в для каждого элемента и ребро из каждого множества к каждому элементу, содержащемуся в нем. ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle (S,T,E)}$ ${\displaystyle S}$ ${\displaystyle T}$

Менее тривиально, строгие гаммоиды являются в точности двойственными матроидами трансверсальных матроидов. Чтобы увидеть, что каждый строгий гаммоид является двойственным трансверсальному матроиду, пусть будет строгим гаммоидом, определенным из ориентированного графа и начального множества вершин , и рассмотрим трансверсальный матроид для семейства множеств для каждой вершины , где вершина принадлежит , если она равна или имеет ребро в . Любой базис строгого гаммоида, состоящий из конечных точек некоторого множества непересекающихся путей из , является дополнением базиса трансверсального матроида, сопоставляя каждую вершину таким образом, что является ребром пути (или самим собой, если не участвует ни в одном из путей). Обратно, каждый базис трансверсального матроида, состоящий из представителя для каждого , порождает дополнительный базис строгого гаммоида, состоящий из конечных точек путей, образованных множеством ребер . Этот результат принадлежит Инглтону и Пиффу. ^{[4] [8]} ${\displaystyle \gamma }$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle N_{v}}$ ${\displaystyle v\in V(G)\setminus S}$ ${\displaystyle u}$ ${\displaystyle N_{v}}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle |S|}$ ${\displaystyle S}$ ${\displaystyle N_{v}}$ ${\displaystyle u}$ ${\displaystyle uv}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u_{v}}$ ${\displaystyle N_{v}}$ ${\displaystyle u_{v}v}$

Чтобы увидеть, наоборот, что каждый трансверсальный матроид является двойственным строгому гаммоиду, найдите подсемейство множеств, определяющих матроид, такое, что подсемейство имеет систему различных представителей и определяет тот же самый матроид. Сформируйте граф, вершинами которого является объединение множеств, и который имеет ребро к представительному элементу каждого множества из других членов того же множества. Тогда множества, сформированные, как указано выше, для каждого представительного элемента, являются в точности множествами, определяющими исходный трансверсальный матроид, поэтому строгий гаммоид, образованный этим графом и множеством представительных элементов, является двойственным данному трансверсальному матроиду. ^{[4] [8]} ${\displaystyle N_{v}}$ ${\displaystyle v}$

Как простое следствие теоремы Инглтона-Пиффа, каждый гаммоид является контракцией трансверсального матроида. Гаммоиды являются наименьшим классом матроидов, который включает трансверсальные матроиды и замкнут относительно дуальности и взятия миноров . ^{[4] [9] [10]}

Репрезентативность

Неверно, что каждый гаммоид является регулярным , т.е. представимым над каждым полем. В частности, равномерный матроид не является бинарным матроидом, и, в более общем случае, линия -точек может быть представлена ​​только над полями с или более элементами. Однако каждый гаммоид может быть представлен над почти каждым конечным полем . ^{[3] [4]} Более конкретно, гаммоид с множеством элементов может быть представлен над каждым полем , которое имеет по крайней мере элементы. ^{[4] [11] [12]} ${\displaystyle U{}_{4}^{2}}$ ${\displaystyle n}$ ${\displaystyle U{}_{n}^{2}}$ ${\displaystyle n-1}$ ${\displaystyle S}$ ${\displaystyle 2^{|S|}}$

Ссылки

1. Perfect, Hazel (1968), «Применение теоремы Менгера о графе», Журнал математического анализа и приложений , 22 : 96–111, doi : 10.1016/0022-247X(68)90163-7 , MR  0224494.
2. Pym, JS (1969), «Связывание множеств в графах», Журнал Лондонского математического общества , s1-44 (1): 542–550, doi :10.1112/jlms/s1-44.1.542.
3. Mason, JH (1972), «О классе матроидов, возникающих из путей в графах», Труды Лондонского математического общества , Третья серия, 25 (1): 55–74, doi :10.1112/plms/s3-25.1.55, MR  0311496.
4. Schrijver, Alexander (2003), Комбинаторная оптимизация: многогранники и эффективность. Том B: Матроиды, деревья, стабильные множества, алгоритмы и комбинаторика, том 24, Берлин: Springer-Verlag, стр. 659–661, ISBN 3-540-44389-4, г-н  1956925.
5. Оксли 2006, стр. 100
6. Оксли, Джеймс Г. (2006), Теория матроидов , Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 48–49, ISBN 9780199202508.
7. Оксли (2006), стр. 100.
8. Инглтон, AW; Пифф, MJ (1973), "Гаммоиды и трансверсальные матроиды", Журнал комбинаторной теории , Серия B, 15 : 51–68, doi : 10.1016/0095-8956(73)90031-2 , MR  0329936.
9. Оксли 2006, стр. 115
10. Валлийский, DJA (2010), Теория Матроидов, Courier Dover Publications, стр. 222–223, ISBN 9780486474397.
11. Аткин, AOL (1972), «Замечание о статье Пиффа и Уэлша», Журнал комбинаторной теории , Серия B, 13 (2): 179–182, doi : 10.1016/0095-8956(72)90053-6 , MR  0316281.
12. Линдстрём, Бернт (1973), «О векторных представлениях индуцированных матроидов», Бюллетень Лондонского математического общества , 5 : 85–90, doi :10.1112/blms/5.1.85, MR  0335313.