Ориентированный матроид

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

Ориентированное множество ${\displaystyle X}$ — множество ${\displaystyle {\underline {X}}}$ с заданным разбиением его элементов на два подмножества: подмножество «положительных элементов» ${\displaystyle X^{+}}$и подмножество «отрицательных» — ${\displaystyle X^{-}}$.

Множество ${\displaystyle {\underline {X}}=X^{+}\cup X^{-}}$называется носителем ориентированного множества ${\displaystyle X}$.

Пустое ориентированное множество ${\displaystyle \emptyset }$ — ориентированное множество с носителем ${\displaystyle {\underline {\emptyset }}}$ (соответственно, с пустым множеством «положительных» элементов и пустым множеством «отрицательных»).

Ориентированное множество ${\displaystyle Y}$ является противоположным ориентированному множеству ${\displaystyle X}$, если ${\displaystyle Y^{+}=X^{-}}$и ${\displaystyle Y^{-}=X^{+}}$.

Множество ${\displaystyle {\mathcal {C}}}$ ориентированных подмножеств множества ${\displaystyle E}$ будет являться набором циклов ориентированного матроида, если выполняются следующие аксиомы:

• (C0) ${\displaystyle \emptyset \notin {\mathcal {C}}}$,
• (C1) ${\displaystyle {\mathcal {C}}=-{\mathcal {C}}}$, то есть для любого ${\displaystyle X\in {\mathcal {C}}}$ ориентированное подмножество ${\displaystyle -X}$ тоже лежит в ${\displaystyle {\mathcal {C}}}$,
• (C2) для любых ${\displaystyle X,Y\in {\mathcal {C}}}$, если ${\displaystyle {\underline {X}}\subseteq {\underline {Y}}}$, то ${\displaystyle X=Y}$ или ${\displaystyle X=-Y}$,
• (С3) для любых ${\displaystyle X,Y\in {\mathcal {C}},X\neq -Y}$, и ${\displaystyle e\in X^{+}\cap Y^{-}}$ существует ${\displaystyle Z\in {\mathcal {C}}}$ такое, что ${\displaystyle Z^{+}\subseteq (X^{+}\cup Y^{+})\backslash \{e\}}$ и ${\displaystyle Z^{-}\subseteq (X^{-}\cup Y^{-})\backslash \{e\}}$.

По данному ориентированному графу можно построить матроид циклов графа, забыв ориентированную структуру. Циклами полученного матроида будут простые циклы исходного графа. Тогда по каждому такому циклу можно построить ориентированное подмножество ${\displaystyle X}$ множества рёбер графа следующим образом: обойти цикл в каком-либо направлении, взять рёбра, ориентация которых совпадает с направлением обхода, в множество ${\displaystyle X^{+}}$, а остальные, соответственно, в ${\displaystyle X^{-}}$.

Например, у графа на рисунке справа два простых цикла: ${\displaystyle \{(1,2),(1,3),(3,2)\}}$ и ${\displaystyle \{(3,4),(4,3)\}}$. По ним можно построить четыре цикла ориентированного матроида за счёт выбора двух возможных ориентаций для каждого: ${\displaystyle \{(1,2),-(1,3),-(3,2)\}}$, ${\displaystyle \{-(1,2),(1,3),(3,2)\}}$, ${\displaystyle \{(3,4),(4,3)\}}$, and ${\displaystyle \{-(3,4),-(4,3)\}}$.

Björner, A., Las Vergnas, M., Sturmfels, B., White, N., & Ziegler, G. M. (1999). Oriented matroids (No. 46). Cambridge University Press