Эйлеров матроид

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

Примеры

В форме матроида $U{}_{n}^{r}$ , схемы представляют собой наборы ровно $r+1$ элементы. Следовательно, однородный матроид эйлеров тогда и только тогда, когда $r+1$ является делителем $n$ . Например, $n$ -точечные линии $U{}_{n}^{2}$ эйлеровы тогда и только тогда, когда $n$ делится на три.

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

Связь с эйлеровыми графами

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

Определение эйлерова графа, приведенное выше, допускает несвязные графы, поэтому не каждый такой граф имеет эйлеров обход. Уайльд (1975) отмечает, что графы, имеющие эйлеровы обходы, могут быть охарактеризованы альтернативным способом, который обобщается на матроиды: граф $G$ имеет эйлеров тур тогда и только тогда, когда его можно составить из какого-либо другого графа $H$ и цикл $C$ в $H$ , сжимая края $H$ которые не принадлежат $C$ . В сжатом графе $C$ обычно перестает быть простым циклом и вместо этого становится туром Эйлера. Аналогично Уайльд рассматривает матроиды, которые могут быть образованы из матроида большего размера путем сжатия элементов, не принадлежащих какой-либо конкретной схеме. Он показывает, что это свойство тривиально для общих матроидов (оно означает только, что каждый элемент принадлежит хотя бы одной схеме), но может использоваться для характеристики эйлеровых матроидов среди бинарных матроидов , матроидов, представимых над GF(2) :бинарный матроид является эйлеровым тогда и только тогда, когда он является сжатием другого бинарного матроида на схему. ^[2]

Двойственность с двудольными матроидами

Для плоских графов свойства эйлерова и двудольности двойственны: планарный граф является эйлеровым тогда и только тогда, когда его двойственный граф двудольный. Как показал Уэлш, эта двойственность распространяется на бинарные матроиды: бинарный матроид является эйлеровым тогда и только тогда, когда его двойственный матроид является двудольным матроидом , матроидом, в котором каждая схема имеет четную мощность. ^[1]^[3]

Для матроидов, которые не являются бинарными, двойственность между эйлеровыми и двудольными матроидами может нарушиться. Например, универсальный матроид $U{}_{6}^{2}$ является эйлеровым, но его двойственное $U{}_{6}^{4}$ не является двудольным, так как его схемы имеют размер пять. Самодуальный однородный матроид $U{}_{6}^{3}$ является двудольным, но не эйлеровым.

Альтернативные характеристики

Из-за соответствия между эйлеровыми и двудольными матроидами среди бинарных матроидов, бинарные матроиды, которые являются эйлеровыми, могут быть охарактеризованы альтернативными способами. Характеристика Уайльда (1975) является одним из примеров; еще два заключаются в том, что двоичный матроид является эйлеровым тогда и только тогда, когда каждый элемент принадлежит нечетному числу схем, тогда и только тогда, когда весь матроид имеет нечетное число разбиений на схемы. ^[4] Ловас и Сересс (1993) собрали несколько дополнительных характеристик эйлеровых бинарных матроидов, на основе которых они вывели алгоритм полиномиального времени для проверки того, является ли бинарный матроид эйлеровым. ^[5]

Вычислительная сложность

Любой алгоритм, проверяющий, является ли данный матроид эйлеровым, при наличии доступа к матроиду через оракул независимости , должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занимать полиномиальное время. В частности, трудно выделить однородный матроид на множестве $2n$ элементы со всеми циклами размера $n+1$ , из матроида мощения , который отличается от однородного матроида наличием двух дополнительных циклов размера $n$ . Матроид дорожного покрытия является эйлеровым, а матроид однородного — нет. Любой алгоритм оракула, примененный к однородному матроиду, должен ${\tbinom {2n}{n}}/2$ запросы, экспоненциальное число, чтобы убедиться, что входные данные не являются экземпляром матроида дорожного покрытия. ^[6]

Эйлерово расширение

Если $M$ является бинарным матроидом, не являющимся эйлеровым, то он имеет уникальное эйлерово расширение — бинарный матроид ${\bar {M}}$ чьи элементы являются элементами $M$ вместе с одним дополнительным элементом $e$ , такой, что ограничение ${\bar {M}}$ к элементам $M$ изоморфен $M$ . Двойник ${\bar {M}}$ представляет собой двудольный матроид, образованный из двойственного $M$ добавив $e$ для каждой нечетной цепи. ^[7]

Ссылки

^ Перейти обратно: ^а ^б Уэлш, DJA (1969), «Эйлер и двудольные матроиды», Journal of Combinatorial Theory , 6 : 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR 0237368 .
^ Уайльд, П.Дж. (1975), «Теорема Эйлера о схеме для бинарных матроидов», Журнал комбинаторной теории , серия B, 18 : 260–264, doi : 10.1016/0095-8956(75)90051-9 , MR 0384577 .
^ Харари, Фрэнк ; Уэлш, Доминик (1969), «Матроиды против графов», «Многие аспекты теории графов» (Proc. Conf., Western Mich. Univ., Каламазу, Мичиган, 1968) , Конспекты лекций по математике, том. 110, Берлин: Springer, стр. 155–170, doi : 10.1007/BFb0060114 , MR 0263666 .
^ Шикаре, М.М. (2001), «Новые характеристики эйлеровых и двудольных бинарных матроидов» (PDF) , Indian Journal of Pure and Applied Mathematics , 32 (2): 215–219, MR 1820861 , заархивировано из оригинала (PDF) в 2015 г. -07-06 , получено 28 августа 2012 г.
^ Ловас, Ласло ; Сересс, Акос (1993), «Коциклическая решетка бинарных матроидов», European Journal of Combinatorics , 14 (3): 241–250, doi : 10.1006/eujc.1993.1027 , MR 1215334 .
^ Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .
^ Себё, Андраш (1990), «Кографическая многопоточная проблема: эпилог», Многогранная комбинаторика (Морристаун, Нью-Джерси, 1989) , DIMACS Ser. Дискретная математика. Теория. Вычислить. наук., вып. 1, Провиденс, Род-Айленд: Амер. Математика. Соц., стр. 203–234, МР 1105128 .

[w69-1] Перейти обратно: ^а ^б Уэлш, DJA (1969), «Эйлер и двудольные матроиды», Journal of Combinatorial Theory , 6 : 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR 0237368 .

[2] Уайльд, П.Дж. (1975), «Теорема Эйлера о схеме для бинарных матроидов», Журнал комбинаторной теории , серия B, 18 : 260–264, doi : 10.1016/0095-8956(75)90051-9 , MR 0384577 .

[3] Харари, Фрэнк ; Уэлш, Доминик (1969), «Матроиды против графов», «Многие аспекты теории графов» (Proc. Conf., Western Mich. Univ., Каламазу, Мичиган, 1968) , Конспекты лекций по математике, том. 110, Берлин: Springer, стр. 155–170, doi : 10.1007/BFb0060114 , MR 0263666 .

[4] Шикаре, М.М. (2001), «Новые характеристики эйлеровых и двудольных бинарных матроидов» (PDF) , Indian Journal of Pure and Applied Mathematics , 32 (2): 215–219, MR 1820861 , заархивировано из оригинала (PDF) в 2015 г. -07-06 , получено 28 августа 2012 г.

[5] Ловас, Ласло ; Сересс, Акос (1993), «Коциклическая решетка бинарных матроидов», European Journal of Combinatorics , 14 (3): 241–250, doi : 10.1006/eujc.1993.1027 , MR 1215334 .

[6] Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .

[7] Себё, Андраш (1990), «Кографическая многопоточная проблема: эпилог», Многогранная комбинаторика (Морристаун, Нью-Джерси, 1989) , DIMACS Ser. Дискретная математика. Теория. Вычислить. наук., вып. 1, Провиденс, Род-Айленд: Амер. Математика. Соц., стр. 203–234, МР 1105128 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]