Ориентированный матроид (Kjnyumnjkfguudw bgmjkn;)

Перейти к навигации Перейти к поиску

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

Обозначения

[править | править код]

Ориентированное множество  — множество с заданным разбиением его элементов на два подмножества: подмножество «положительных элементов» и подмножество «отрицательных» — .

Множество называется носителем ориентированного множества .

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

Ориентированное множество является противоположным ориентированному множеству , если и .

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

[править | править код]

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

  • (C0) ,
  • (C1) , то есть для любого ориентированное подмножество тоже лежит в ,
  • (C2) для любых , если , то или ,
  • (С3) для любых , и существует такое, что и .

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

[править | править код]
Ориентированный граф

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

Например, у графа на рисунке справа два простых цикла: и . По ним можно построить четыре цикла ориентированного матроида за счёт выбора двух возможных ориентаций для каждого: , , , and .

Библиография

[править | править код]

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