Jump to content

гаммоидный

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

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

Определение

[ редактировать ]

Позволять быть ориентированным графом, быть набором начальных вершин, и быть набором конечных вершин (не обязательно не пересекающихся с ). Гаммоид полученные на основе этих данных, как набор его элементов. Подмножество из является независимым в если существует набор непересекающихся по вершинам путей, все начальные точки которых принадлежат и чьи конечные точки в точности . [4]

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

Рассмотрим однородный матроид на наборе элементы, в которых каждый набор или меньшее количество элементов является независимым. Один из способов представить этот матроид в виде гаммоида — сформировать полный двудольный граф. с набором из вершины на одной стороне бираздела с множеством из вершины на другой стороне бираздела, и каждое ребро направлено от к На этом графике подмножество является множеством конечных точек множества непересекающихся путей тогда и только тогда, когда оно имеет или меньше вершин, иначе в чтобы начать пути. Особая структура этого графа показывает, что однородный матроид является трансверсальным матроидом, а также гаммоидом. [6]

Как вариант, тот же форменный матроид можно представить в виде гаммоида на меньшем графе, имея только вершины, выбрав подмножество из вершины и соединяя каждую из выбранных вершин с любой другой вершиной графа. Опять же, подмножество вершин графа может быть конечными точками непересекающихся путей тогда и только тогда, когда оно имеет или меньше вершин, потому что в противном случае не хватит вершин, которые могут быть началами путей. В этом графе каждая вершина соответствует элементу матроида, показывая, что однородный матроид является строгим гамоидом. [7]

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

[ редактировать ]

Ранг набора в гаммоиде, определенном из графа и подмножества вершин и это, по определению, максимальное количество непересекающихся по вершинам путей из к . По теореме Менгера оно также равно минимальной мощности множества. который пересекает каждый путь из к . [4]

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

[ редактировать ]

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

Менее тривиально то, что строгие гаммоиды - это в точности двойственные матроиды трансверсальных матроидов. Чтобы убедиться в том, что каждый строгий гаммоид двойственен трансверсальному матроиду, пусть быть строгим гаммоидом, определенным из ориентированного графа и начальный набор вершин и рассмотрим трансверсальный матроид семейства множеств для каждой вершины , где вершина принадлежит если оно равно или у него есть преимущество . Любой базис строгого гаммоида, состоящий из концов некоторого множества непересекающиеся пути из , является дополнением базиса трансверсального матроида, соответствующего каждому до вершины такой, что является ребром пути (или сам, если не участвует ни в одном из путей). Обратно, каждый базис трансверсального матроида, состоящий из представителя для каждого , порождает дополнительный базис строгого гаммоида, состоящий из концов путей, образованных множеством ребер . Этот результат принадлежит Инглтону и Пиффу . [4] [8]

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

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

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

[ редактировать ]

Неверно, что каждый гаммоид регулярен , т. е. представим в любом поле. В частности, однородный матроид не является бинарным матроидом и, в более общем смысле, -точечная линия могут быть представлены только в полях с или более элементов. Однако каждый гаммоид может быть представлен почти над любым конечным полем . [3] [4] Точнее, гаммаид с набором элементов может быть представлено в каждом поле, имеющем хотя бы элементы. [4] [11] [12]

  1. ^ Перфект, Хейзел (1968), «Применение теоремы Менгера о графике», Journal of Mathematical Analysis and Applications , 22 : 96–111, doi : 10.1016/0022-247X(68)90163-7 , MR   0224494 .
  2. ^ Пим, Дж. С. (1969), «Связывание множеств в графах», Журнал Лондонского математического общества , s1-44 (1): 542–550, doi : 10.1112/jlms/s1-44.1.542 .
  3. ^ Jump up to: а б Мейсон, Дж. Х. (1972), «О классе матроидов, возникающих из путей в графах», Труды Лондонского математического общества , третья серия, 25 (1): 55–74, doi : 10.1112/plms/s3-25.1.55 , МР   0311496 .
  4. ^ Jump up to: а б с д и ж г час Шрийвер, Александр (2003), Комбинаторная оптимизация: многогранники и эффективность. Том. B: Матроиды, деревья, устойчивые множества , алгоритмы и комбинаторика, том. 24, Берлин: Springer-Verlag, стр. 659–661, ISBN.  3-540-44389-4 , МР   1956925 .
  5. ^ Оксли 2006 , с. 100
  6. ^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Oxford University Press, стр. 48–49, ISBN.  9780199202508 .
  7. ^ Оксли (2006) , с. 100.
  8. ^ Jump up to: а б Инглтон, штат Аризона; Пифф, 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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 15f48e2cfcaa9e34031599f242c7ff73__1720173060
URL1:https://arc.ask3.ru/arc/aa/15/73/15f48e2cfcaa9e34031599f242c7ff73.html
Заголовок, (Title) документа по адресу, URL1:
Gammoid - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)