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

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

ОбозначенияПравить

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

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

Пустое ориентированное множество $\mathrm{\varnothing <!--\; \varnothing \; -->}$$\emptyset$  — ориентированное множество с носителем $\underset{\_<!--\; \_\; -->}{\mathrm{\varnothing <!--\; \varnothing \; -->}}$${\underline {\emptyset }}$  (соответственно, с пустым множеством «положительных» элементов и пустым множеством «отрицательных»).

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

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

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

• (C0) $\mathrm{\varnothing <!--\; \varnothing \; -->}\notin <!--\; \notin \; -->\mathcal{C}$$\emptyset \notin {\mathcal {C}}$ ,
• (C1) $\mathcal{C}=-<!--\; -\; -->\mathcal{C}$${\mathcal {C}}=-{\mathcal {C}}$ ,
• (C2) для любых $X,Y\in <!--\; \in \; -->\mathcal{C}$$X,Y\in {\mathcal {C}}$ , если $\underset{\_<!--\; \_\; -->}{X}\subseteq <!--\; \subseteq \; -->\underset{\_<!--\; \_\; -->}{Y}$${\underline {X}}\subseteq {\underline {Y}}$ , то $X=Y$$X=Y$  или $X=-<!--\; -\; -->Y$$X=-Y$ ,
• (С3) для любых $X,Y\in <!--\; \in \; -->\mathcal{C},X\ne <!--\; \ne \; -->-<!--\; -\; -->Y$$X,Y\in {\mathcal {C}},X\neq -Y$ , и $e\in <!--\; \in \; -->X^{+}\cap <!--\; \cap \; -->Y^{-<!--\; -\; -->}$$e\in X^{+}\cap Y^{-}$  существует $Z\in <!--\; \in \; -->\mathcal{C}$$Z\in {\mathcal {C}}$  такое, что $Z^{+}\subseteq <!--\; \subseteq \; -->(X^{+}\cup <!--\; \cup \; -->Y^{+})\mathrm{\setminus <!--\; \setminus \; -->}\{e\}$$Z^{+}\subseteq (X^{+}\cup Y^{+})\backslash \{e\}$  и $Z^{-<!--\; -\; -->}\subseteq <!--\; \subseteq \; -->(X^{-<!--\; -\; -->}\cup <!--\; \cup \; -->Y^{-<!--\; -\; -->})\mathrm{\setminus <!--\; \setminus \; -->}\{e\}$$Z^{-}\subseteq (X^{-}\cup Y^{-})\backslash \{e\}$ .

БиблиографияПравить

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