WikiDer > Ориентированный матроид - Википедия

Теория ориентированного матроида допускает комбинаторный подход к теорема о максимальном потоке и минимальном отсечении. Сеть со значением потока, равным пропускной способности отрезка s-t

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

Все ориентированные матроиды имеют основную матроид. Таким образом, результаты об обычных матроидах могут быть применены к ориентированным матроидам. Тем не менее разговаривать ложно; некоторые матроиды не могут стать ориентированными матроидами ориентирование базовая структура (например, схемы или независимые наборы).^[4]Различие между матроидами и ориентированными матроидами обсуждается ниже.

Матроиды часто используются в таких областях, как теория размерности и алгоритмы.Из-за того, что ориентированный матроид включает дополнительные сведения о ориентированный характер структуры, ее полезность распространяется на несколько областей, включая геометрия и оптимизация.

Фон

Чтобы абстрагироваться от понятия ориентация на краях графа к множествам нужна способность задавать «направление» элементам множества. Это достигается следующим образом: подписанные наборы.

• А подписанный набор, ${ displaystyle X}$, объединяет набор объектов ${ displaystyle { underline {X}}}$ с разделением этого набора на два подмножества: ${ displaystyle X ^ {+}}$ и ${ Displaystyle X ^ {-}}$.

Члены ${ displaystyle X ^ {+}}$ называются положительные элементы; Члены ${ Displaystyle X ^ {-}}$ являются отрицательные элементы.

• Набор ${ displaystyle { underline {X}} = X ^ {+} чашка X ^ {-}}$ называется поддерживать из ${ displaystyle X}$.
• В пустой подписанный набор, ${ displaystyle emptyset}$, определяется как пустое множество ${ displaystyle { underline { emptyset}}}$ в сочетании с «разделением» его на два пустых набора: ${ Displaystyle emptyset ^ {+}}$ и ${ Displaystyle emptyset ^ {-}}$.
• Подписанный набор ${ displaystyle Y}$ это противоположный из ${ displaystyle X}$, т.е. ${ Displaystyle Y = -X}$, если и только если ${ Displaystyle Y ^ {+} = X ^ {-}}$ и ${ Displaystyle Y ^ {-} = X ^ {+}}$

Учитывая элемент опоры ${ displaystyle x}$, напишем ${ displaystyle x}$ для положительного элемента и ${ displaystyle -x}$ для отрицательного элемента. Таким образом, подписанный набор просто добавляет отрицательные знаки к выделенным элементам. Это будет иметь смысл как «направление» только тогда, когда мы будем рассматривать ориентацию более крупных структур. Тогда знак каждого элемента будет кодировать его направление относительно этой ориентации.

Аксиоматизации

Как и у обычных матроидов, несколько эквивалентных системы аксиом существовать. (Такие структуры, которые обладают множеством эквивалентных аксиоматизаций, называются криптоморфный.)

Аксиомы схемы

Позволять ${ displaystyle E}$ быть любым набором. Мы ссылаемся на ${ displaystyle E}$ как набор земли. Позволять ${ Displaystyle { mathcal {C}}}$ быть собранием подписанные наборы, каждый из которых поддержанный подмножеством ${ displaystyle E}$.Если для ${ Displaystyle { mathcal {C}}}$, то эквивалентно ${ Displaystyle { mathcal {C}}}$ это набор подписанные схемыдля ориентированный матроид на ${ displaystyle E}$.

• (C0) ${ Displaystyle emptyset notin { mathcal {C}}}$
• (C1) (симметричный) ${ displaystyle { text {Для всех}} X in { mathcal {C}}, ~ - ! X in { mathcal {C}}.}$
• (C2) (несравненный) ${ displaystyle { text {For all}} X, Y in { mathcal {C}}, ~~ { text {if}} { underline {X}} substeq { underline {Y}} { text {then}} (X = Y { text {или}} X = -Y).}$
• (C3) (слабое исключение) ${ displaystyle { text {Для всех}} X, Y in { mathcal {C}}, X neq -Y { text {с символом}} e in X ^ {+} cap Y ^ { -} { text {есть}} Z in { mathcal {C}} { text {такой, что}}}$
  • ${ Displaystyle Z ^ {+} substeq (X ^ {+} чашка Y ^ {+}) setminus {e } { text {and}}}$
  • ${ displaystyle Z ^ {-} substeq (X ^ {-} cup Y ^ {-}) setminus {e }.}$

Векторные аксиомы

В сочинение подписанных наборов ${ displaystyle X}$ и ${ displaystyle Y}$ это подписанный набор ${ Displaystyle X circ Y}$ определяется ${ displaystyle { underline {X circ Y}} = { underline {X}} cup { underline {Y}}}$, ${ displaystyle (X circ Y) ^ {+} = X ^ {+} cup left (Y ^ {+} setminus X ^ {-} right)}$, и ${ displaystyle (X circ Y) ^ {-} = X ^ {-} cup left (Y ^ {-} setminus X ^ {+} right)}$. В векторов ориентированного матроида - это композиции схем. Векторы ${ Displaystyle { mathcal {V}}}$ ориентированного матроида удовлетворяют следующим аксиомам:

• ${ displaystyle emptyset in { mathcal {V}}}$
• ${ Displaystyle { mathcal {V}} = - { mathcal {V}}}$
• для всех ${ displaystyle X, Y in { mathcal {V}}}$, ${ displaystyle X circ Y in { mathcal {V}}}$
• для всех ${ displaystyle X, Y in { mathcal {V}}}$, ${ displaystyle e in X ^ {+} cap Y ^ {-}}$и ${ displaystyle f in ({ underline {X}} setminus { underline {Y}}) cup ({ underline {Y}} setminus { underline {X}}) cup (X ^ { +} cap Y ^ {+}) cup (X ^ {-} cap Y ^ {-})}$ , Существует ${ Displaystyle Z in { mathcal {V}}}$, так что
  • ${ Displaystyle Z ^ {+} подмножество X ^ {+} чашка Y ^ {+} setminus e}$,
  • ${ displaystyle Z ^ {-} subset X ^ {-} cup Y ^ {-} setminus e}$, и
  • ${ displaystyle f in { underline {Z}}}$.

Аксиомы хиротопа

Позволять ${ displaystyle E}$ быть как указано выше. Для каждого неотрицательного целого числа ${ displaystyle r}$, а хиротоп ранга ${ displaystyle r}$ это функция ${ Displaystyle чи двоеточие E ^ {r} to {- 1,0,1 }}$ который удовлетворяет следующим аксиомам:

• (B0) (нетривиально): ${ displaystyle chi}$ не тождественно нулю
• (B1) (попеременно): Для любого перестановка ${ displaystyle sigma}$ и ${ displaystyle x_ {1}, dots, x_ {r} in E}$, ${ displaystyle chi left (x _ { sigma (1)}, dots, x _ { sigma (r)} right) = operatorname {sgn} ( sigma) chi left (x_ {1} , точки, x_ {r} right)}$, куда ${ displaystyle operatorname {sgn} ( sigma)}$ это знак перестановки.
• (БИ 2) (обмен): Для любого ${ displaystyle x_ {1}, dots, x_ {r}, y_ {1}, dots, y_ {r} in E}$ такой, что ${ displaystyle chi (y_ {i}, x_ {2}, dots, x_ {r}) chi (y_ {1}, dots, y_ {i-1}, x_ {1}, y_ {i +1}, точки, y_ {r}) geq 0}$ для каждого ${ displaystyle i}$, то мы также имеем ${ displaystyle chi left (x_ {1}, dots, x_ {r} right) chi left (y_ {1}, dots, y_ {r} right) geq 0}$.

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

Эквивалентность

Каждый хиротоп ранга ${ displaystyle r}$ рождает набор баз матроида на ${ displaystyle E}$ состоящий из тех ${ displaystyle r}$-элементные подмножества, которые ${ displaystyle chi}$ присваивает ненулевое значение.^[5] После этого хиротоп может подписать цепи этого матроида. Если ${ displaystyle C}$ - схема описываемого матроида, то ${ displaystyle C subset {x_ {1}, dots, x_ {r}, x_ {r + 1} }}$ куда ${ displaystyle {x_ {1}, dots, x_ {r} }}$ это основа. потом ${ displaystyle C}$ может быть подписан положительными элементами

${ displaystyle C ^ {+} = {x_ {i}: (- 1) ^ {i} chi (x_ {1}, dots, x_ {i-1}, x_ {i + 1}, точки, x_ {r + 1}) = 1 }}$

а отрицательные элементы дополняют. Таким образом, хиротоп дает начало ориентированные базы ориентированного матроида. В этом смысле (B0) - непустая аксиома для базисов, а (B2) - свойство обмена базисами.

Примеры

Ориентированные матроиды часто вводятся (например, Бахема и Керна) как абстракция для ориентированных графов или систем линейных неравенств. Ниже приведены явные конструкции.

Направленные графы

Учитывая диграф, мы определяем схему со знаком из стандарта схема графа следующим способом. Поддержка подписанной схемы ${ displaystyle textstyle { underline {X}}}$ - стандартный набор ребер минимального цикла. Идем по циклу по часовой стрелке или против часовой стрелки, присваивая те ребра, ориентация которых совпадает с направлением, положительным элементам ${ displaystyle textstyle X ^ {+}}$ и те ребра, ориентация которых не совпадает с направлением на отрицательные элементы ${ displaystyle textstyle X ^ {-}}$. Если ${ displaystyle textstyle { mathcal {C}}}$ это набор всех таких ${ displaystyle textstyle X}$, тогда ${ displaystyle textstyle { mathcal {C}}}$ - множество знаковых схем ориентированного матроида на множестве ребер ориентированного графа.

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

Если мы рассмотрим ориентированный граф справа, то мы увидим, что есть только две схемы, а именно ${ Displaystyle textstyle {(1,2), (1,3), (3,2) }}$ и ${ Displaystyle textstyle {(3,4), (4,3) }}$. Тогда есть только четыре возможных схемы со знаком, соответствующие ориентации по часовой стрелке и против часовой стрелки, а именно ${ Displaystyle textstyle {(1,2), - (1,3), - (3,2) }}$, ${ Displaystyle textstyle {- (1,2), (1,3), (3,2) }}$, ${ Displaystyle textstyle {(3,4), (4,3) }}$, и ${ Displaystyle textstyle {- (3,4), - (4,3) }}$. Эти четыре набора образуют набор знаковых схем ориентированного матроида на множестве ${ Displaystyle textstyle {(1,2), (1,3), (3,2), (3,4), (4,3) }}$.

Линейная алгебра

Если ${ displaystyle textstyle E}$ любое конечное подмножество ${ displaystyle textstyle mathbb {R} ^ {n}}$, то множество минимальных линейно зависимых множеств образует схемное множество матроида на ${ displaystyle textstyle E}$. Чтобы распространить эту конструкцию на ориентированные матроиды, для каждой схемы ${ displaystyle textstyle {v_ {1}, dots, v_ {m} }}$ существует минимальная линейная зависимость

${ Displaystyle сумма _ {я = 1} ^ {м} лямбда _ {я} v_ {я} = 0}$

с ${ displaystyle textstyle lambda _ {i} in mathbb {R}}$. Тогда подписанная схема ${ displaystyle textstyle X = {X ^ {+}, X ^ {-} }}$ имеет положительные элементы ${ displaystyle textstyle X ^ {+} = {v_ {i}: lambda _ {i}> 0 }}$ и отрицательные элементы ${ displaystyle textstyle X ^ {-} = {v_ {i}: lambda _ {i} <0 }}$. Набор всего такого ${ displaystyle textstyle X}$ формирует множество знаковых схем ориентированного матроида на ${ displaystyle textstyle E}$. Реализуемые таким образом ориентированные матроиды называются представимый.

Учитывая тот же набор векторов ${ displaystyle E}$, мы можем определить такой же ориентированный матроид с хиротопом ${ displaystyle chi: E ^ {r} rightarrow {- 1,0,1 }}$. Для любого ${ displaystyle x_ {1}, dots, x_ {r} in E}$ позволять

${ displaystyle chi (x_ {1}, dots, x_ {r}) = operatorname {sgn} ( det (x_ {1}, dots, x_ {r}))}$

где правая часть уравнения - знак детерминант. потом ${ displaystyle chi}$ - хиротоп того же ориентированного матроида на множестве ${ displaystyle E}$.

Гиперплоскости

Настоящая гиперплоскость ${ Displaystyle { mathcal {A}} = {H_ {1}, ldots, H_ {n} }}$ конечное множество гиперплоскостей в ${ Displaystyle mathbb {R} ^ {d}}$, каждый из которых содержит начало координат. Выбирая одну сторону каждой гиперплоскости в качестве положительной стороны, мы получаем расположение полупространств. Компоновка полупространства разбивает окружающее пространство на конечный набор ячеек, каждая из которых определяется тем, с какой стороны каждой гиперплоскости она приземляется. То есть назначить каждую точку ${ Displaystyle х в mathbb {R} ^ {d}}$к подписанному набору ${ Displaystyle X = (X ^ {+}, X ^ {-})}$с ${ Displaystyle я в Х ^ {+}}$ если ${ displaystyle x}$ находится на положительной стороне ${ displaystyle H_ {i}}$и ${ displaystyle i in X ^ {-}}$если ${ displaystyle x}$ находится на отрицательной стороне ${ displaystyle H_ {i}}$. Этот набор наборов со знаком определяет набор ковекторов ориентированного матроида, которые являются векторами дуально ориентированного матроида.^[6]

Выпуклый многогранник

Гюнтер М. Циглер вводит ориентированные матроиды через выпуклые многогранники.

Полученные результаты

Ориентируемость

Стандартный матроид называется ориентируемый если его схемы являются опорами схем со знаком некоторого ориентированного матроида. Известно, что все реальные представимые матроиды ориентируемы. Также известно, что класс ориентируемых матроидов замкнут относительно взятия несовершеннолетние, однако список запрещенные несовершеннолетние для ориентируемых матроидов бесконечно.^[7] В этом смысле ориентированные матроиды представляют собой гораздо более строгую формализацию, чем обычные матроиды.

Двойственность

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

Чтобы увидеть явную конструкцию этого уникального ортогонального дуально ориентированного матроида, рассмотрим хиротоп ориентированного матроида ${ displaystyle chi: E ^ {r} rightarrow {- 1,0,1 }}$. Если рассматривать список элементов ${ displaystyle x_ {1}, dots, x_ {k} in E}$ как циклическую перестановку, то определим ${ displaystyle operatorname {sgn} (x_ {1}, dots, x_ {k})}$ быть знаком соответствующей перестановки. Если ${ displaystyle chi ^ {*}: E ^ {| E | -r} rightarrow {- 1,0,1 }}$ определяется как

${ displaystyle chi ^ {*} (x_ {1}, dots, x_ {r}) mapsto chi (x_ {r + 1}, dots, x_ {| E |}) operatorname {sgn} (x_ {1}, dots, x_ {r}, x_ {r + 1}, dots, x_ {| E |}),}$

тогда ${ displaystyle chi ^ {*}}$ является хиротопом единственного ортогонального дуально ориентированного матроида.^[9]

Топологическое представление

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

Не все ориентированные матроиды представимы, то есть не все имеют реализации в виде точечных конфигураций или, что эквивалентно, конфигураций гиперплоскостей. Однако в некотором смысле все ориентированные матроиды близки к реализации в виде гиперплоскостей. В частности, Теорема о топологическом представлении Фолкмана – Лоуренса утверждает, что любой ориентированный матроид имеет реализацию как расположение псевдосфер. А ${ displaystyle d}$-размерный псевдосфера это вложение ${ displaystyle e: S ^ {d} hookrightarrow S ^ {d + 1}}$ такой, что существует гомеоморфизм ${ displaystyle h: S ^ {d + 1} rightarrow S ^ {d + 1}}$ так что ${ displaystyle h circ e}$ встраивает ${ Displaystyle S ^ {d}}$ как экватор ${ Displaystyle S ^ {d + 1}}$. В этом смысле псевдосфера - это просто приручить сфера (в отличие от дикие сферы). А расположение псевдосферы в ${ Displaystyle S ^ {d}}$ представляет собой набор псевдосфер, пересекающихся по псевдосферам. Наконец, теорема Фолкмана Лоуренса о топологическом представлении утверждает, что каждый ориентированный матроид ранга ${ displaystyle d + 1}$ можно получить из расположения псевдосферы в ${ Displaystyle S ^ {d}}$.^[10] Он назван в честь Джон Фолкман и Джим Лоуренс, опубликовавший ее в 1978 году.

Геометрия

Зонотоп, представляющий собой сумму отрезков Минковского, является фундаментальной моделью для ориентированных матроидов. Шестнадцать темно-красных точек (справа) образуют сумму Минковского четырех невыпуклых множеств (слева), каждое из которых состоит из пары красных точек. Их выпуклые корпуса (заштрихованные розовым) содержат знаки плюса (+): правый знак плюс - это сумма левых знаков плюс.

Теория ориентированных матроидов повлияла на развитие комбинаторная геометрия, особенно теория выпуклые многогранники, зонотопы, и конфигураций векторов (расположение гиперплоскостей).^[11] Многие результаты -Теорема Каратеодори, Теорема Хелли, Теорема Радона, то Теорема Хана – Банаха, то Теорема Крейна – Мильмана, то лемма Фаркаша- можно сформулировать с использованием соответствующих ориентированных матроидов.^[12]

Оптимизация

В выпуклой геометрии симплекс-алгоритм линейного программирования интерпретируется как отслеживание пути по вершинам выпуклого многогранника. Теория ориентированных матроидов изучает комбинаторные инварианты, которые обнаруживаются в знаковых паттернах матриц, которые появляются как основы обмена поворотных алгоритмов.

Инициатором разработки системы аксиом для ориентированных матроидов стал А. Р. Тиррелл Рокафеллар описать шаблоны знаков матриц, возникающих в результате операций поворота симплексного алгоритма Данцига; Рокафеллар был вдохновлен Альберт В. Такерисследования таких знаковых узоров в «Таблицах Такера».^[13]

Теория ориентированных матроидов привела к прорывам в комбинаторная оптимизация. В линейное программирование, это был язык, на котором Роберт Дж. Бланд сформулировал свой правило поворота, по которому симплексный алгоритм избегает циклов. Точно так же его использовали Терлаки и Чжан, чтобы доказать, что их перекрестные алгоритмы иметь конечное прекращение для линейное программирование проблемы. Аналогичные результаты были получены в выпуклом квадратичное программирование Тодда и Терлаки.^[14] Он был применен к дробно-линейное программирование,^[15] квадратичное программирование проблемы и задачи линейной дополнительности.^[16][17][18]

Вне комбинаторная оптимизация, Теория ОМ также появляется в выпуклая минимизация в теории «монотропного программирования» Рокафеллара и связанных с ней понятиях «усиленного спуска».^[19] По аналогии, матроид теория повлияла на развитие комбинаторных алгоритмов, в частности жадный алгоритм.^[20] В более общем плане жадный полезен для изучения конечного завершения алгоритмов.

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

дальнейшее чтение

Книги

• Бахем, Ахим; Керн, Уолтер (1992). Двойственность линейного программирования: введение в ориентированные матроиды. Universitext. Springer-Verlag. Дои:10.1007/978-3-642-58152-6. ISBN 978-3-540-55417-2. МИСТЕР 1230380.
• Бьёрнер, Андерс; Лас Вергнас, Мишель; Штурмфельс, Бернд; Белый, Нил; Циглер, Гюнтер (1999). Ориентированные матроиды. Энциклопедия математики и ее приложений. 46 (2-е изд.). Издательство Кембриджского университета. ISBN 978-0-521-77750-6. Zbl 0944.52006.
• Боковски, Юрген (2006). Вычислительно-ориентированные матроиды. Классы эквивалентности матриц в естественных рамках. Издательство Кембриджского университета. ISBN 978-0-521-84930-2. Zbl 1120.52011.
• Лоулер, Юджин (2001). Комбинаторная оптимизация: сети и матроиды. Дувр. ISBN 978-0-486-41453-9. Zbl 1058.90057.
• Эвар Д. Неринг и Альберт В. Такер, 1993, Линейные программы и связанные с ними задачи, Academic Press. (элементарно)
• Рокафеллар, Р. Тиррелл (1984). Сетевые потоки и монотропная оптимизация. Wiley-Interscience. переиздано Athena Scientific из Димитрий Берцекас, 1998.
• Циглер, Гюнтер М. (1994). Лекции по многогранникам. Нью-Йорк: Springer-Verlag.
• Рихтер-Геберт, Юрген; Циглер, Гюнтер М. (1997). «Ориентированные матроиды». В Гудман, Джейкоб Э.; О'Рурк, Джозеф (ред.). Справочник по дискретной и вычислительной геометрии. Бока-Ратон: CRC Press. стр.111–132.

Статьи

• А. Бахем, А. Ванка, Теоремы разделения для ориентированных матроидов, Дискретная математика. 70 (1988) 303—310.
• Роберт Дж. Бланд, Новые правила конечного поворота для симплекс-метода, Математика. Опер. Res. 2 (1977) 103–107.
• Фолкман, Джон; Лоуренс, Джим (Октябрь 1978 г.). «Ориентированные матроиды». J. Combin. Теория Сер. B. 25 (2): 199–236. Дои:10.1016/0095-8956(78)90039-4.
• Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота». Математическое программирование, серия B. 79 (1–3). Амстердам: Издательство Северной Голландии, стр. 369–395. Дои:10.1007 / BF02614325. МИСТЕР 1464775.
• Фукуда, Комей; Намики, Макото (март 1994). «Об экстремальном поведении метода наименьшего индекса Мурти». Математическое программирование. 64 (1): 365–370. Дои:10.1007 / BF01582581. МИСТЕР 1286455.
• Иллеш, Тибор; Сирмаи, Акос; Терлаки, Тамаш (1999). «Метод конечных крестовин для гиперболического программирования». Европейский журнал операционных исследований. 114 (1): 198–214. CiteSeerX 10.1.1.36.7090. Дои:10.1016 / S0377-2217 (98) 00049-6. ISSN 0377-2217.
• Р. Тиррелл Рокафеллар. Элементарные векторы подпространства ${ displaystyle R ^ {n}}$, в Комбинаторная математика и ее приложения, Р. К. Бозе и Т. А. Доулинг (ред.), Univ. of North Carolina Press, 1969, 104–127.
• Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование. Серия А. 46 (1): 79–84. Дои:10.1007 / BF01585729. МИСТЕР 1045573.
• Терлаки, Т. (1985). «Конвергентный крест-накрест». Оптимизация: журнал математического программирования и исследования операций. 16 (5): 683–690. Дои:10.1080/02331938508843067. ISSN 0233-1934. МИСТЕР 0798939.
• Терлаки, Тамаш (1987). «Метод конечных крестовин для ориентированных матроидов». Журнал комбинаторной теории. Серия Б. 42 (3): 319–327. Дои:10.1016/0095-8956(87)90049-9. ISSN 0095-8956. МИСТЕР 0888684.
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Правила поворота для линейного программирования: обзор последних теоретических разработок». Анналы исследований операций. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. Дои:10.1007 / BF02096264. ISSN 0254-5330. МИСТЕР 1260019.
• Майкл Дж. Тодд, Линейное и квадратичное программирование в ориентированных матроидах, J. Combin. Теория Сер. B 39 (1985) 105—133.
• Ван, Чжэ Минь (1987). "Конечный алгоритм без конформного исключения над ориентированным матроидным программированием". Китайские анналы математики (Shuxue Niankan B Ji). Серия Б. 8 (1): 120–125. ISSN 0252-9599. МИСТЕР 0886756.

В интернете

• Циглер, Гюнтер (1998). «Ориентированные матроиды сегодня». Электронный журнал комбинаторики.
• Малькевич, Иосиф. «Ориентированные матроиды: сила объединения». Столбец функций. Американское математическое общество. Получено 2009-09-14.

внешняя ссылка

• Комей Фукуда (ETH Zentrum, Цюрих) с публикации включая Ориентированное программирование на матроиде (Кандидатская диссертация 1982 г.)
• Тамаш Терлаки (Университет Лихай) с публикации