гаммоидный

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

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

Определение

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

— Строгий гаммоид это гаммоид, в котором множество $T$ целевых вершин состоит из каждой вершины в $G$. Таким образом, гаммоид — это ограничение строгого гаммоида на подмножество его элементов.

Пример

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

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

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

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

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

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

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

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

Как простое следствие теоремы Инглтона-Пиффа, каждый гаммоид является сжатием трансверсального матроида. Гаммоиды — наименьший класс матроидов, включающий трансверсальные матроиды, замкнутый относительно двойственности и принимающий миноры .

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

Неверно, что каждый гаммоид регулярен , т. е. представим в любом поле. В частности, однородный матроид $U{}_{4}^{2}$ не является бинарным матроидом и, в более общем смысле, $n$-точечная линия $U{}_{n}^{2}$ могут быть представлены только в полях с $n-1$ или более элементов. Однако каждый гаммоид может быть представлен почти над любым конечным полем . Точнее, гаммаид с набором элементов $S$ может быть представлено в каждом поле, имеющем хотя бы $2^{|S|}$ элементы.