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

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

Обозначения

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

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

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

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

Определение в терминах циклов

См. также: Матроид § Определение в терминах циклов

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

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

Примеры

Ориентированные графы

Ориентированный граф

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

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