Гаммоид - Gammoid

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

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

Определение

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

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

Пример

Рассмотрим униформа матроид ${ 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]

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

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

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

Отношение к поперечным матроидам

А поперечный матроид определяется из семейство наборов: его элементы являются элементами наборов, а набор ${ 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}$ не участвует ни в одном из путей). И наоборот, каждый базис трансверсального матроида, состоящий из представителя ${ displaystyle u_ {v}}$ для каждого ${ displaystyle N_ {v}}$, порождает дополнительный базис строгого гаммоида, состоящий из концов путей, образованных множеством ребер ${ displaystyle u_ {v} v}$.^[4][8]

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

Каждый гаммоид - это сокращение поперечного матроида. Гаммоиды - это наименьший класс матроидов, который включает в себя трансверсальные матроиды и замкнут в условиях двойственности и принятия несовершеннолетние.^[4][9][10]

Представимость

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

Рекомендации