Matroide orientado

La teoría de la matroide orientada permite un enfoque combinatorio del teorema de flujo máximo y corte mínimo . Una red con el valor de caudal igual a la capacidad de un corte st.

Una matroide orientada es una estructura matemática que abstrae las propiedades de gráficos dirigidos , arreglos vectoriales sobre campos ordenados y arreglos hiperplanos sobre campos ordenados . ^[1] En comparación, una matriz ordinaria (es decir, no orientada) abstrae las propiedades de dependencia que son comunes tanto a los gráficos , que no están necesariamente dirigidos , como a las disposiciones de los vectores sobre los campos , que no están necesariamente ordenados . ^{[2] [3]}

Todas las matroides orientadas tienen una matroide subyacente . Por lo tanto, los resultados en matroides ordinarios se pueden aplicar a matroides orientados. Sin embargo, lo contrario es falso; algunos matroides no pueden convertirse en matroides orientados orientando una estructura subyacente (por ejemplo, circuitos o conjuntos independientes). ^[4] La distinción entre matroides y matroides orientados se analiza más adelante.

Los matroides suelen ser útiles en áreas como la teoría de dimensiones y los algoritmos . Debido a la inclusión de una matriz orientada de detalles adicionales sobre la naturaleza orientada de una estructura, su utilidad se extiende aún más a varias áreas, incluida la geometría y la optimización .

Fondo

Artículo principal: Conjunto firmado

Para abstraer el concepto de orientación en los bordes de un gráfico a conjuntos, se necesita la capacidad de asignar "dirección" a los elementos de un conjunto. La forma en que esto se logra es con la siguiente definición de conjuntos firmados .

• Un conjunto firmado , y combina un conjunto de objetos, con una partición de ese conjunto en dos subconjuntos: y .${\displaystyle X}$${\displaystyle {\underline {X}}}$${\displaystyle X^{+}}$${\displaystyle X^{-}}$

Los miembros de se denominan elementos positivos ; los miembros de son los elementos negativos .${\displaystyle X^{+}}$${\displaystyle X^{-}}$

• El conjunto se llama soporte de .${\displaystyle {\underline {X}}=X^{+}\cup X^{-}}$${\displaystyle X}$
• El conjunto firmado vacío , , se define como el conjunto vacío combinado con una "partición" de la misma en dos conjuntos vacíos: y .${\displaystyle \emptyset }$${\displaystyle {\underline {\emptyset }}}$${\displaystyle \emptyset ^{+}}$${\displaystyle \emptyset ^{-}}$
• El conjunto con signo es el opuesto de , es decir , si y solo si y${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y=-X}$${\displaystyle Y^{+}=X^{-}}$${\displaystyle Y^{-}=X^{+}}$

Dado un elemento del soporte , escribiremos para un elemento positivo y para un elemento negativo. De esta manera, un conjunto con signo simplemente agrega signos negativos a los elementos distinguidos. Esto tendrá sentido como una "dirección" sólo cuando consideremos las orientaciones de estructuras más grandes. Entonces, el signo de cada elemento codificará su dirección relativa a esta orientación.${\displaystyle x}$${\displaystyle x}$${\displaystyle -x}$

Axiomatizaciones

Ver también: Matroid § Bases y circuitos , Sistema axiomático y Criptomorfismo

Como las matroides ordinarias, existen varios sistemas equivalentes de axiomas . (Las estructuras que poseen múltiples axiomatizaciones equivalentes se denominan criptomórficas ).

Axiomas de circuito

Sea cualquier conjunto. Nos referimos a que el conjunto del suelo . Sea una colección de conjuntos firmados , cada uno de los cuales está respaldado por un subconjunto de . Si los siguientes axiomas para , a continuación, de forma equivalente es el conjunto de circuitos firmados para un matroide orientado sobre .${\displaystyle E}$${\displaystyle E}$${\displaystyle {\mathcal {C}}}$${\displaystyle E}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle E}$

• (C0) ${\displaystyle \emptyset \notin {\mathcal {C}}}$
• (C1) (simétrico) ${\displaystyle {\text{ For all }}X\in {\mathcal {C}},~-\!X\in {\mathcal {C}}.}$
• (C2) (incomparable) ${\displaystyle {\text{ For all }}X,Y\in {\mathcal {C}},~~{\text{ if }}{\underline {X}}\subseteq {\underline {Y}}{\text{ then }}(X=Y{\text{ or }}X=-Y).}$
• (C3) (eliminación débil) ${\displaystyle {\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 }}}$
  • ${\displaystyle Z^{+}\subseteq (X^{+}\cup Y^{+})\setminus \{e\}{\text{ and }}}$
  • ${\displaystyle Z^{-}\subseteq (X^{-}\cup Y^{-})\setminus \{e\}.}$

Axiomas vectoriales

La composición de conjuntos firmados y es el conjunto firmado definido por , y . Los vectores de un matroide orientado son las composiciones de circuitos. Los vectores de una matroide orientada satisfacen los siguientes axiomas:${\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}}}$
• para todos ,${\displaystyle X,Y\in {\mathcal {V}}}$${\displaystyle X\circ Y\in {\mathcal {V}}}$
• para todos , y , hay un , tal que${\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^{+}\subset X^{+}\cup Y^{+}\setminus e}$,
  • ${\displaystyle Z^{-}\subset X^{-}\cup Y^{-}\setminus e}$, y
  • ${\displaystyle f\in {\underline {Z}}}$.

Axiomas de quirótopo

Sea como arriba. Para cada entero no negativo , un quirótopo de rango es una función que satisface los siguientes axiomas:${\displaystyle E}$${\displaystyle r}$${\displaystyle r}$${\displaystyle \chi \colon E^{r}\to \{-1,0,1\}}$

• (B0) (no trivial) : no es idénticamente cero${\displaystyle \chi }$
• (B1) (alternativamente) : Para cualquier permutación y , donde es el signo de la permutación.${\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},\dots ,x_{r}\right)}$${\displaystyle \operatorname {sgn} (\sigma )}$
• (B2) (intercambio) : Para cualquiera tal que para cada uno , entonces también tenemos .${\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},\dots ,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}$

El término quirótopo se deriva de la noción matemática de quiralidad , que es un concepto abstraído de la química , donde se usa para distinguir moléculas que tienen la misma estructura excepto por una reflexión.

Equivalencia

Cada quirótopo de rango da lugar a un conjunto de bases de un matroide que consiste en esos subconjuntos de elementos que asignan un valor distinto de cero. ^[5] El quirótopo puede entonces firmar los circuitos de ese matroide. Si es un circuito del matroide descrito, entonces, ¿ dónde está la base? Luego se puede firmar con elementos positivos.${\displaystyle r}$${\displaystyle E}$${\displaystyle r}$${\displaystyle \chi }$${\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},\dots ,x_{r+1})=1\}}$

y elementos negativos el complemento. Así, un quirótopo da lugar a las bases orientadas de un matroide orientado. En este sentido, (B0) es el axioma no vacío para las bases y (B2) es la propiedad de intercambio de la base.

Ejemplos de

Las matroides orientadas a menudo se introducen (por ejemplo, Bachem y Kern) como una abstracción para gráficos dirigidos o sistemas de desigualdades lineales. A continuación se muestran las construcciones explícitas.

Gráficos dirigidos

Artículo principal: Gráfico dirigido

Ver también: Red de flujo

Dado un dígrafo , definimos un circuito con signo a partir del circuito estándar del gráfico mediante el siguiente método. El soporte del circuito firmado es el conjunto estándar de aristas en un ciclo mínimo. Seguimos el ciclo en sentido horario o antihorario asignando aquellos bordes cuya orientación coincide con la dirección de los elementos positivos y aquellos bordes cuya orientación no coincide con la dirección de los elementos negativos . Si es el conjunto de todos ellos , entonces es el conjunto de circuitos con signo de una matroide orientada en el conjunto de aristas del grafo dirigido.${\displaystyle \textstyle {\underline {X}}}$${\displaystyle \textstyle X^{+}}$${\displaystyle \textstyle X^{-}}$${\displaystyle \textstyle {\mathcal {C}}}$${\displaystyle \textstyle X}$${\displaystyle \textstyle {\mathcal {C}}}$

Un gráfico dirigido

Si consideramos el gráfico dirigido a la derecha, podemos ver que solo hay dos circuitos, a saber y . A continuación, sólo hay cuatro posibles circuitos firmados correspondientes a las agujas del reloj y en sentido antihorario orientaciones, a saber , , , y . Estos cuatro conjuntos forman el conjunto de circuitos firmados de una matroide orientada en el conjunto .${\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)\}}$

Álgebra lineal

Ver también: Matroide § Matroides del álgebra lineal

Si es un subconjunto finito de , entonces el conjunto de conjuntos mínimos linealmente dependientes forma el conjunto de circuitos de una matroide en . Para extender esta construcción a las matroides orientadas, para cada circuito hay una dependencia lineal mínima.${\displaystyle \textstyle E}$${\displaystyle \textstyle \mathbb {R} ^{n}}$${\displaystyle \textstyle E}$${\displaystyle \textstyle \{v_{1},\dots ,v_{m}\}}$

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

con . Entonces, el circuito con signo tiene elementos positivos y elementos negativos . El conjunto de todos estos forma el conjunto de circuitos firmados de una matroide orientada . Las matroides orientadas que se pueden realizar de esta manera se denominan representables .${\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}$

Dado el mismo conjunto de vectores , podemos definir el mismo matroide orientado con un quirótopo . Para cualquier deja${\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}))}$

donde el lado derecho de la ecuación es el signo del determinante . Luego está el quirótopo del mismo matroide orientado en el set .${\displaystyle \chi }$${\displaystyle E}$

Arreglos de hiperplano

Artículo principal: Disposición de hiperplanos.

Una disposición de hiperplano real es un conjunto finito de hiperplanos en , cada uno de los cuales contiene el origen. Al elegir un lado de cada hiperplano para que sea el lado positivo, obtenemos una disposición de medios espacios. Una disposición de medio espacio descompone el espacio ambiental en una colección finita de células, cada una definida por el lado de cada hiperplano en el que aterriza. Es decir, asigne cada punto al conjunto con signo con si está en el lado positivo de y si está en el lado negativo de . Esta colección de conjuntos firmados define el conjunto de covectores de la matroide orientada, que son los vectores de la matroide de orientación dual. ^[6]${\displaystyle {\mathcal {A}}=\{H_{1},\ldots ,H_{n}\}}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle x\in \mathbb {R} ^{d}}$${\displaystyle X=(X^{+},X^{-})}$${\displaystyle i\in X^{+}}$${\displaystyle x}$${\displaystyle H_{i}}$${\displaystyle i\in X^{-}}$${\displaystyle x}$${\displaystyle H_{i}}$

Politopo convexo

Artículo principal: politopo convexo

Günter M. Ziegler introduce matroides orientados a través de politopos convexos.

Resultados

Orientabilidad

Una matroide estándar se llama orientable si sus circuitos son los soportes de circuitos con signo de alguna matroide orientada. Se sabe que todas las matroides reales representables son orientables. También se sabe que la clase de matroides orientables está cerrada para menores de edad , sin embargo se sabe que la lista de menores prohibidos para matroides orientables es infinita. ^[7] En este sentido, las matroides orientadas son una formalización mucho más estricta que las matroides regulares.

Dualidad

Ver también: Matroid § Dualidad

Al igual que las matroides tienen un doble único , las matroides orientadas tienen un doble ortogonal único . Lo que esto significa es que las matroides subyacentes son duales y que los cocircuitos están firmados para que sean ortogonales a cada circuito. Se dice que dos conjuntos con signo son ortogonales si la intersección de sus soportes está vacía o si la restricción de sus elementos positivos a la intersección y los elementos negativos a la intersección forman dos conjuntos con signo no idénticos y no opuestos. La existencia y unicidad de la matriz de orientación dual depende del hecho de que cada circuito con signo es ortogonal a cada cocircuito con signo. ^[8] Para ver por qué la ortogonalidad es necesaria para la unicidad, basta con mirar el ejemplo del dígrafo anterior. Sabemos que para gráficas planas, el dual de la matroide del circuito es la matroide del circuito del dual planar de la gráfica . Por lo tanto, hay tantas matroides orientadas diferentes que son duales como formas de orientar un gráfico y su dual.

Para ver la construcción explícita de este matroide de orientación dual ortogonal único, considere el quirótopo de un matroide orientado . Si consideramos una lista de elementos de como una permutación cíclica, la definimos como el signo de la permutación asociada. Si se define como${\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|}),}$

luego es el quirótopo de la única matroide ortogonal de orientación dual. ^[9]${\displaystyle \chi ^{*}}$

Representación topológica

Este es un ejemplo de una disposición de pseudolina que es distinta de cualquier disposición de línea.

No todas las matroides orientadas son representables, es decir, no todas tienen realizaciones como configuraciones de puntos o, de manera equivalente, arreglos de hiperplanos. Sin embargo, en cierto sentido, todas las matroides orientadas se acercan a darse cuenta de que son arreglos de hiperplanos. En particular, el teorema de representación topológica de Folkman-Lawrence establece que cualquier matroide orientado tiene una realización como una disposición de pseudoesferas . Una pseudoesfera dimensional es una incrustación de tal que existe un homeomorfismo de manera que incrusta como un ecuador de . En este sentido, una pseudoesfera es solo una esfera domesticada (a diferencia de las esferas salvajes ). A${\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}}$La disposición de la pseudoesfera${\displaystyle S^{d}}$ es una colección de pseudoesferas que se cruzan a lo largo de las pseudoesferas. Finalmente, el teorema de representación topológica de Folkman Lawrence establece que cada matroide orientado de rango se puede obtener a partir de una disposición de pseudoesferas en . ^[10] Lleva el nombre de Jon Folkman y Jim Lawrence , quienes lo publicaron en 1978.${\displaystyle d+1}$${\displaystyle S^{d}}$

Geometría

Un zonotopo, que es una suma de segmentos de línea de Minkowski, es un modelo fundamental para las matroides orientadas. Los dieciséis puntos rojo oscuro (a la derecha) forman la suma de Minkowski de los cuatro conjuntos no convexos (a la izquierda), cada uno de los cuales consta de un par de puntos rojos. Sus cascos convexos (sombreados en rosa) contienen signos más (+): el signo más de la derecha es la suma de los signos más de la izquierda.

Artículo principal: geometría combinatoria

Ver también: politopo convexo y zonotopo

La teoría de las matroides orientadas ha influido en el desarrollo de la geometría combinatoria , especialmente la teoría de politopos convexos , zonótopos y de configuraciones de vectores ( arreglos de hiperplanos ). ^[11] Muchos Resultados teorema de Carathéodory , el teorema de Helly , el teorema de Radon , el teorema de Hahn-Banach , el teorema de Krein-Milman , el lema de Farkas -puede ser formulado utilizando matroides orientada apropiados. ^[12]

Mejoramiento

En geometría convexa, el algoritmo simplex para programación lineal se interpreta como trazar una ruta a lo largo de los vértices de un poliedro convexo. La teoría matroide orientada estudia las invariantes combinatorias que se revelan en los patrones de signos de las matrices que aparecen como bases de intercambio de algoritmos pivotantes.

Ver también: programación lineal , programación cuadrática y algoritmo Criss-cross

El desarrollo de un sistema de axiomas para matroides orientados fue iniciado por R. Tyrrell Rockafellar para describir los patrones de signos de las matrices que surgen a través de las operaciones pivotantes del algoritmo simplex de Dantzig; Rockafellar se inspiró en los estudios de Albert W. Tucker de tales patrones de signos en "Tucker tableaux".^[13]

La teoría de las matroides orientadas ha dado lugar a avances en la optimización combinatoria . En programación lineal , fue el lenguaje en el que Robert G. Bland formuló su regla pivotante , mediante la cual el algoritmo simplex evita los ciclos. De manera similar, fue utilizado por Terlaky y Zhang para demostrar que sus algoritmos entrecruzados tienen terminación finita para problemas de programación lineal . Todd y Terlaky obtuvieron resultados similares en la programación cuadrática convexa . ^[14] Se ha aplicado a programación lineal-fraccional , ^[15] programación cuadráticaproblemas y problemas de complementariedad lineal . ^{[16] [17] [18]}

Fuera de la optimización combinatoria , la teoría OM también aparece en la minimización convexa en la teoría de Rockafellar de "programación monotrópica" y las nociones relacionadas de "ascendencia fortificada". ^[19] De manera similar, la teoría matroide ha influido en el desarrollo de algoritmos combinatorios, particularmente el algoritmo codicioso . ^[20] De manera más general, un greedoid es útil para estudiar la terminación finita de algoritmos.

Referencias

1. R. Tyrrell Rockafellar 1969. Anders Björner y otros, Capítulos 1-3. Jürgen Bokowski, Capítulo 1. Günter M. Ziegler , Capítulo 7.
2. Björner et alia, Capítulos 1-3. Bokowski, capítulos 1-4.
3. Debido a que las matroides y las matroides orientadas son abstracciones de otras abstracciones matemáticas, casi todos los libros relevantes están escritos para científicos matemáticos y no para el público en general. Para aprender acerca de las matroides orientadas, una buena preparación es estudiar el libro de texto sobre optimización lineal de Nering y Tucker, que está impregnado de ideas de matroides orientadas, y luego pasar a las conferencias de Ziegler sobre politopos.
4. Björner et alia, Capítulo 7.9.
5. Björner et alia, Capítulo 3.5
6. * Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). Matroides orientadas . Enciclopedia de las matemáticas y sus aplicaciones. 46 (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-77750-6. OCLC  776950824 . Zbl  0944.52006 .
7. Björner et alia, Capítulo 7.9
8. Björner et alia, Capítulo 3.4
9. Björner et alia, Capítulo 3.6
10. Björner et alia, Capítulo 5.2
11. Bachem y Kern, Capítulos 1-2 y 4-9. Björner et alia, Capítulos 1-8. Ziegler, Capítulo 7-8. Bokowski, capítulos 7-10.
12. Bachem y Wanka, Capítulos 1-2, 5, 7-9. Björner et alia, Capítulo 8.
13. Rockafellar, R. Tyrrell (1969). "Los vectores elementales de un subespacio de (1967)" (PDF) . En RC Bose ; Thomas A. Dowling (eds.). Matemática combinatoria y sus aplicaciones . Serie de monografías de probabilidad y estadística de la Universidad de Carolina del Norte. Chapel Hill, Carolina del Norte: Prensa de la Universidad de Carolina del Norte. págs. 104-127. Señor 0278972 . R N {\displaystyle R^{N}}  
14. Björner et alia, Capítulos 8–9. Fukuda y Terlaky. Compárese con Ziegler.
15. Illés, Szirmai y Terlaky (1999)
16. Fukuda y Terlaky (1997)
17. Fukuda y Terlaky (1997 , p. 385)
18. Fukuda y Namiki (1994 , p. 367)
19. Rockafellar 1984 y 1998.
20. Lawler. Rockafellar 1984 y 1998.

Otras lecturas

Libros

• Bachem, Achim; Kern, Walter (1992). Dualidad de programación lineal: una introducción a las matroides orientadas . Universitext. Springer-Verlag. doi : 10.1007 / 978-3-642-58152-6 . ISBN 978-3-540-55417-2. Señor  1230380 .
• Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter (1999). Matroides orientadas . Enciclopedia de las matemáticas y sus aplicaciones. 46 (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-77750-6. Zbl  0944.52006 .
• Bokowski, Jürgen (2006). Matroides orientados a la computación. Clases de equivalencia de matrices dentro de un marco natural . Prensa de la Universidad de Cambridge . ISBN 978-0-521-84930-2. Zbl  1120.52011 .
• Lawler, Eugene (2001). Optimización combinatoria: redes y matroides . Dover. ISBN 978-0-486-41453-9. Zbl  1058.90057 .
• Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press. (elemental)
• Rockafellar, R. Tyrrell (1984). Flujos de red y optimización monotrópica . Wiley-Interscience.republicado por Athena Scientific de Dimitri Bertsekas , 1998.
• Ziegler, Günter M. (1994). Conferencias sobre politopos . Nueva York: Springer-Verlag.
• Richter-Gebert, Jürgen; Ziegler, Günter M. (1997). "Matroides orientadas". En Goodman, Jacob E .; O'Rourke, Joseph (eds.). Manual de geometría discreta y computacional . Boca Ratón: CRC Press. págs.  111-132 .

Artículos

• A. Bachem, A. Wanka, Teoremas de separación para matroides orientados, Matemáticas discretas. 70 (1988) 303-310.
• Robert G. Bland , Nuevas reglas de pivote finito para el método simplex, Math. Oper. Res. 2 (1977) 103–107.
• Folkman, Jon ; Lawrence, Jim (octubre de 1978). "Matroides orientadas" . J. Combin. Teoría Ser. B . 25 (2): 199–236. doi : 10.1016 / 0095-8956 (78) 90039-4 .
• Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote". Programación Matemática, Serie B . Amsterdam: North-Holland Publishing Co. 79 (1–3): 369–395. doi : 10.1007 / BF02614325 . Señor  1464775 .
• Fukuda, Komei ; Namiki, Makoto (marzo de 1994). "Sobre comportamientos extremos del método de índice mínimo de Murty". Programación matemática . 64 (1): 365–370. doi : 10.1007 / BF01582581 . Señor  1286455 .
• Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "El método entrecruzado finito para la programación hiperbólica" . Revista europea de investigación operativa . 114 (1): 198-214. CiteSeerX  10.1.1.36.7090 . doi : 10.1016 / S0377-2217 (98) 00049-6 . ISSN  0377-2217 .
• R. Tyrrell Rockafellar . Los vectores elementales de un subespacio de , en Matemáticas combinatorias y sus aplicaciones , RC Bose y TA Dowling (eds.), Univ. of North Carolina Press, 1969, 104-127.${\displaystyle R^{n}}$
• Roos, C. (1990). "Un ejemplo exponencial de la regla pivotante de Terlaky para el método simplex cruzado". Programación matemática . Serie A. 46 (1): 79–84. doi : 10.1007 / BF01585729 . Señor  1045573 .
• Terlaky, T. (1985). "Un método cruzado convergente". Optimización: una revista de programación matemática e investigación de operaciones . 16 (5): 683–690. doi : 10.1080 / 02331938508843067 . ISSN  0233-1934 . Señor  0798939 .
• Terlaky, Tamás (1987). "Un método entrecruzado finito para matroides orientados" . Revista de teoría combinatoria . Serie B 42 (3): 319–327. doi : 10.1016 / 0095-8956 (87) 90049-9 . ISSN  0095-8956 . Señor  0888684 .
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para la programación lineal: una encuesta sobre los desarrollos teóricos recientes". Anales de investigación operativa . 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . doi : 10.1007 / BF02096264 . ISSN  0254-5330 . Señor  1260019 .
• Michael J. Todd, Programación lineal y cuadrática en matroides orientadas, J. Combin. Teoría Ser. B 39 (1985) 105-133.
• Wang, Zhe Min (1987). "Un algoritmo libre de eliminación conforme finito sobre programación matroide orientada". Anales chinos de matemáticas (Shuxue Niankan B Ji) . Serie B. 8 (1): 120-125. ISSN  0252-9599 . Señor  0886756 .

En la red

• Ziegler, Günter (1998). "Matroides orientadas hoy" . La Revista Electrónica de Combinatoria .
• Malkevitch, Joseph. "Matroides orientadas: el poder de la unificación" . Columna de características . Sociedad Matemática Estadounidense . Consultado el 14 de septiembre de 2009 .

enlaces externos

• Komei Fukuda (ETH Zentrum, Zurich) con publicaciones que incluyen programación matroide orientada (tesis doctoral de 1982)
• Tamás Terlaky (Lehigh University) con publicaciones