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

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

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

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

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

История

Первое появление ориентированных матроидов было в статье Джорджа Дж. Минти в 1966 году и ограничивалось обычными матроидами .

Впоследствии Р. Т. Рокфеллер (1969) предложил задачу обобщения концепции Минти на реальные векторные пространства. Его предложение помогло привести к разработке общей теории.

Предыстория

Основная статья: Подписанный набор

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

• набор Подписанный , $X$, объединяет набор объектов, ${\underline {X}}$, с упорядоченным двуразделением $(X^{+},X^{-})$ этого набора на два непересекающихся подмножества: $X^{+}$ и $X^{-}$.

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

• Набор ${\underline {X}}=X^{+}\cup X^{-}$ называется поддержкой ​ $X$.
• Пустой подписанный набор , $\emptyset$, определяется как пустое множество ${\underline {\emptyset }}$ в сочетании с (упорядоченным) его двуразделением на два пустых множества: $\emptyset ^{+}$ и $\emptyset ^{-}$.
• Подписанный набор $Y$ является противоположностью ​ $X$, написано $Y=-X$, если $Y^{+}=X^{-}$ и $Y^{-}=X^{+}.$

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

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

См. также: Матроид § Базисы и схемы , Аксиоматическая система и Криптоморфизм.

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

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

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

• (С0) $\emptyset \notin {\mathcal {C}}$
• (C1) (симметричный) ${\text{ For all }}X\in {\mathcal {C}},~-\!X\in {\mathcal {C}}.$
• (С2) (несравненный) ${\text{ For all }}X,Y\in {\mathcal {C}},~~{\text{ if }}{\underline {X}}\subseteq {\underline {Y}}{\text{ then }}(X=Y{\text{ or }}X=-Y).$
• (C3) (слабое исключение) ${\text{ For all }}X,Y\in {\mathcal {C}},X\neq -Y{\text{ with an }}e\in X^{+}\cap Y^{-}{\text{ there is a }}Z\in {\mathcal {C}}{\text{ such that }}$
  • $Z^{+}\subseteq (X^{+}\cup Y^{+})\setminus \{e\}{\text{ and }}$
  • $Z^{-}\subseteq (X^{-}\cup Y^{-})\setminus \{e\}.$

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

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

• $\emptyset \in {\mathcal {V}}$
• ${\mathcal {V}}=-{\mathcal {V}}$
• для всех $X,Y\in {\mathcal {V}}$, $X\circ Y\in {\mathcal {V}}$
• для всех $X,Y\in {\mathcal {V}}$, $e\in X^{+}\cap Y^{-}$и $f\in ({\underline {X}}\setminus {\underline {Y}})\cup ({\underline {Y}}\setminus {\underline {X}})\cup (X^{+}\cap Y^{+})\cup (X^{-}\cap Y^{-})$ , есть $Z\in {\mathcal {V}}$, такой, что
  • $Z^{+}\subset X^{+}\cup Y^{+}\setminus e$,
  • $Z^{-}\subset X^{-}\cup Y^{-}\setminus e$, и
  • $f\in {\underline {Z}}$.

Ковекторы . ориентированного матроида — это векторы его дуально ориентированного матроида

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

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

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

Термин «хиротоп» происходит от математического понятия киральности — понятия, абстрагированного от химии , где он используется для различения молекул, имеющих одинаковую структуру, за исключением отражения.

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

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

$C^{+}=\{x_{i}:(-1)^{i}\chi (x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{r+1})=1\}$

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

Примеры

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

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

Основная статья: Ориентированный граф

См. Также: Проточная сеть

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

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

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

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

Смотрите также: Матроид § Матроиды из линейной алгебры

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

$\sum _{i=1}^{m}\lambda _{i}v_{i}=0$

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

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

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

где правая часть уравнения — знак определителя . Затем $\chi$ является хиротопом того же ориентированного матроида на множестве $E$.

Композиции гиперплоскостей

Основная статья: Расположение гиперплоскостей

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

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

Основная статья: Выпуклый многогранник

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

Результаты

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

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

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

См. также: Матроид § Двойственность.

Точно так же, как у матроида есть уникальные двойники , у ориентированного матроида есть уникальный двойник, который часто называют «ортогональным двойником». Это означает, что основные матроиды двойственны и что косхемы подписаны так, что они «ортогональны» каждой схеме. Два множества со знаком называются ортогональными, если пересечение их носителей пусто или если ограничение их положительных элементов на пересечение и отрицательных элементов на пересечение образует два неидентичных и непротивоположных множества со знаком. Существование и уникальность дуальноориентированного матроида зависит от того, что каждая знаковая схема ортогональна каждой знаковой косхеме.

Чтобы понять, почему ортогональность необходима для уникальности, достаточно взглянуть на приведенный выше пример орграфа. Мы знаем, что для планарных графов двойственным матроиду схемы является матроид схемы планарного двойственного графа . Таким образом, существует столько различных дуальных пар ориентированных матроидов, основанных на матроиде графа, сколько существует способов ориентировать граф и, соответственно, его двойственный.

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

$\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|}),$

затем $\chi ^{*}$ является хиротопом уникального ортогонального дуально ориентированного матроида.

представление

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

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

Геометрия

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

Основная статья: Комбинаторная геометрия

См. Также: Выпуклый многогранник и зонотоп.

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

Оптимизация

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

См. также: Линейное программирование , Квадратичное программирование и Алгоритм крест-накрест.

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

Теория ориентированных матроидов привела к прорыву в комбинаторной оптимизации . В линейном программировании это был язык, на котором Роберт Г. Бланд сформулировал свое правило поворота , согласно которому симплексный алгоритм избегает циклов. Точно так же Терлаки и Чжан использовали его, чтобы доказать, что их перекрестные алгоритмы имеют конечное завершение для задач линейного программирования . Аналогичные результаты были получены в выпуклом квадратичном программировании Тоддом и Терлаки. Он был применен к дробно-линейному программированию , задачи квадратичного программирования и проблемы линейной дополнительности .

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

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

Книги

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

Статьи

• А. Бахем, А. Ванка, Теоремы разделения для ориентированных матроидов, Discrete Math. 70 (1988) 303–310.
• Бланд, Роберт Г. (1977). «Новые конечные правила поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. дои : 10.1287/moor.2.2.103 .
• Фолкман, Джон ; Лоуренс, Джим (октябрь 1978 г.). «Ориентированные матроиды» . Журнал комбинаторной теории . Серия Б. 25 (2): 199–236. дои : 10.1016/0095-8956(78)90039-4 .
• Фукуда, Комей ; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота» (PDF) . Математическое программирование, серия Б. 79 (1–3). Амстердам: Издательство Северной Голландии: 369–395. дои : 10.1007/BF02614325 . МР   1464775 . S2CID   2794181 .
• Фукуда, Комей ; Намики, Макото (март 1994 г.). «Об экстремальном поведении метода наименьшего индекса Мерти». Математическое программирование . 64 (1): 365–370. дои : 10.1007/BF01582581 . МР   1286455 . S2CID   21476636 .
• Иллес, Тибор; Ширмаи, Акос; Терлаки, Тамаш (1999). «Метод конечных перекрещиваний гиперболического программирования» . Европейский журнал операционных исследований . 114 (1): 198–214. CiteSeerX   10.1.1.36.7090 . дои : 10.1016/S0377-2217(98)00049-6 . ISSN   0377-2217 .
• Р. Тиррелл Рокафеллар (1969). Элементарные векторы подпространства $R^{n}$, в «Комбинаторной математике и ее приложениях» , RC Bose и TA Dowling (ред.), Univ. North Carolina Press, стр. 104–127.
• Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование . Серия А. 46 (1): 79–84. дои : 10.1007/BF01585729 . МР   1045573 . S2CID   33463483 .
• Терлаки, Т. (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 . S2CID   6058077 .
• Тодд, Майкл Дж. (1985). «Линейное и квадратичное программирование в ориентированных матроидах» . Журнал комбинаторной теории . Серия Б. 39 (2): 105–133. дои : 10.1016/0095-8956(85)90042-5 .
• Ван, Чжэ Минь (1987). «Конечный алгоритм без конформного исключения над ориентированным матроидным программированием». Китайские анналы математики (Шюсюэ Нянькан Б Цзи) . Серия Б. 8 (1): 120–125. ISSN   0252-9599 . МР   0886756 .

В сети

• Циглер, Гюнтер (1998). «Ориентированные матроиды сегодня» . Электронный журнал комбинаторики : DS4: 10 сентября 1998 г. дои : 10.37236/25 .
• Малькевич, Йозеф. «Ориентированные матроиды: сила объединения» . Колонка функций . Американское математическое общество . Проверено 14 сентября 2009 г.

Внешние ссылки

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