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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

Любой алгоритм, который проверяет, является ли данный матроид эйлеровым, при условии доступа к матроиду через оракул независимости, должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занимать полиномиальное время.^[6]

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

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

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