Гаммоид

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

Концепция гаммоида была введена и показана как матроид Хейзел Перфект  ( 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}$

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

Пример

Рассмотрим равномерный матроид на множестве элементов, в котором каждый набор из или меньшее количество элементов является независимым. Один из способов , чтобы представить этот матроид как gammoid бы , чтобы сформировать полный двудольный граф с набором из вершин на одной стороне двудольности, с набором из вершин на другой стороне двудольности, и с каждым ребром , направленным от до . В этом графе подмножеством является набор конечных точек набора непересекающихся путей тогда и только тогда, когда он имеет или меньше вершин, иначе в нем не будет достаточно вершин, чтобы начать пути. Специальная структура этого графа показывает, что равномерный матроид является трансверсальным матроидом${\ 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}$а также быть гаммоидом. ^[6]

В качестве альтернативы, тот же равномерное матроидом может быть представлена в виде gammoid на меньшем графике, только с вершинами, путем выбора подмножества из вершин и соединения каждого из выбранных вершин каждой другой вершины в графе. Опять же, подмножество вершин графа может быть конечными точками непересекающихся путей тогда и только тогда, когда оно имеет или меньше вершин, потому что в противном случае не будет достаточно вершин, которые могут быть началом путей. В этом графе каждая вершина соответствует элементу матроида, показывая, что равномерный матроид является строгим гаммоидом. ^[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}$

Менее тривиально строгие гаммоиды - это в точности двойственные матроиды трансверсальных матроидов. Чтобы увидеть, что каждый строгий гаммоид двойственен трансверсальному матроиду, пусть будет строгий гаммоид, определенный из ориентированного графа и начального набора вершин , и рассмотрим трансверсальный матроид для семейства множеств для каждой вершины , где вершина принадлежит, если она равна или у него есть преимущество . Любой базис строгого гаммоида, состоящий из конечных точек некоторого набора непересекающихся путей из , является дополнением базиса трансверсального матроида, сопоставляя каждую вершину , которая является ребром пути (или самим собой, если${\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}$не участвует ни в одном из путей). И наоборот, каждый базис трансверсального матроида, состоящий из представителя каждого , порождает дополнительный базис строгого гаммоида, состоящий из концов путей, образованных множеством ребер . Это результат Обри Инглтона и Майка Пиффа . ^{[4] [8]}${\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|}}$

использованная литература