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