matroide orientada

Abstracción del álgebra lineal ordenada

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

Una matroide orientada es una estructura matemática que abstrae las propiedades de gráficos dirigidos , disposiciones vectoriales sobre campos ordenados y disposiciones de hiperplanos sobre campos ordenados . ^{[1] En comparación, una} matroide 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 vectores sobre campos , que no están necesariamente ordenados . ^{[2] [3]}

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

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

Historia

La primera aparición de matroides orientadas fue en un artículo de 1966 de George J. Minty y se limitó a matroides regulares . ^[5]

Posteriormente, RT Rockefellar (1969) sugirió el problema de generalizar el concepto de Minty a espacios vectoriales reales. Su propuesta ayudó a conducir al desarrollo de la teoría general.

Fondo

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 con signo .

• Un conjunto con signo , combina un conjunto de objetos, con una bipartición ordenada de ese conjunto en dos subconjuntos disjuntos: y . ${\displaystyle X}$ ${\displaystyle {\underline {X}}}$ ${\displaystyle (X^{+},X^{-})}$ ${\displaystyle X^{+}}$ ${\displaystyle X^{-}}$

Los miembros de se llaman 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 vacío con signo , , se define como el conjunto vacío combinado con una bipartición (ordenada) del mismo en dos conjuntos vacíos: y . ${\displaystyle \emptyset }$ ${\displaystyle {\underline {\emptyset }}}$ ${\displaystyle \emptyset ^{+}}$ ${\displaystyle \emptyset ^{-}}$
• El conjunto firmado es el opuesto de , escrito , 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 elementos distinguidos. Esto tendrá sentido como "dirección" sólo cuando consideremos orientaciones de estructuras más grandes. Entonces el signo de cada elemento codificará su dirección con respecto a esta orientación. ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle -x}$

Axiomatizaciones

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

Axiomas del circuito

Sea cualquier conjunto. Nos referimos como conjunto de terreno . Sea una colección de conjuntos con signo , cada uno de los cuales está respaldado por un subconjunto de . Si los siguientes axiomas son válidos para , entonces de manera equivalente el conjunto de circuitos con signo para una matroide orientada es . ${\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 con signo y es el conjunto con signo definido por , y . Los vectores de una matroide orientada 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 , existe 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}}}$.

Los covectores de una matroide orientada son los vectores de su matroide orientada dual.

Axiomas del quirótopo

Sea como arriba. Para cada número 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) (alternando) : Para cualquier permutación y , , donde está 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 cualquier 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 utiliza para distinguir moléculas que tienen la misma estructura excepto por un reflejo.

Equivalencia

Cada quirótopo de rango da lugar a un conjunto de bases de una matroide que consta de subconjuntos de elementos a los que se asigna un valor distinto de cero. ^[6] El quirótopo puede entonces firmar los circuitos de esa matroide. Si es un circuito de la matroide descrita, 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 una matroide orientada. En este sentido, (B0) es el axioma no vacío de las bases y (B2) es la propiedad de intercambio de las bases.

Ejemplos

Las matroides orientadas se introducen a menudo (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.

Grafos dirigidos

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 aquellas aristas cuya orientación concuerda con la dirección a los elementos positivos y aquellas aristas cuya orientación no coincide con la dirección a los elementos negativos . Si es el conjunto de todos esos , entonces es el conjunto de circuitos con signo de una matroide orientada en el conjunto de aristas del gráfico 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 la gráfica dirigida de la derecha, podemos ver que solo hay dos circuitos, a saber y . Entonces sólo hay cuatro posibles circuitos con signo correspondientes a orientaciones en sentido horario y antihorario, a saber , , y . Estos cuatro conjuntos forman el conjunto de circuitos con signo 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

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 matroides orientadas, para cada circuito existe 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 con signo de una matroide orientada en . 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 la misma matroide orientada con un quirótopo . para cualquier alquiler ${\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 quirotopo de la misma matroide orientada en el set . ${\displaystyle \chi }$ ${\displaystyle E}$

Arreglos de hiperplano

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 como lado positivo, obtenemos una disposición de semiespacios. Una disposición de medio espacio divide el espacio ambiental en una colección finita de celdas, cada una definida por el lado de cada hiperplano en el que aterriza. Es decir, asigne cada punto al conjunto firmado con if está en el lado positivo de y if está en el lado negativo de . Esta colección de conjuntos con signo define el conjunto de covectores de la matroide orientada, que son los vectores de la matroide orientada dual. ^[7] ${\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

Günter M. Ziegler introduce matroides orientadas mediante politopos convexos.

Resultados

Orientabilidad

Una matroide estándar se llama orientable si sus circuitos son 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. ^[8] En este sentido, las matroides orientadas son una formalización mucho más estricta que las matroides regulares.

Dualidad

Así como una matroide tiene duales únicos , una matroide orientada tiene un dual único, a menudo llamado "dual ortogonal". Lo que esto significa es que las matroides subyacentes son duales y que los cocircuitos están firmados de manera 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 elementos negativos a la intersección forman dos conjuntos con signos no idénticos y no opuestos. La existencia y unicidad de la matroide de doble orientación depende del hecho de que cada circuito con signo es ortogonal a cada cocircuito con signo. ^[9]

Para ver por qué la ortogonalidad es necesaria para la unicidad, sólo hay que mirar el ejemplo del dígrafo anterior. Sabemos que para gráficos planos el dual del circuito matroide es el circuito matroide del gráfico dual plano . Por lo tanto, hay tantos pares duales diferentes de matroides orientadas basadas en la matroide del gráfico como formas de orientar el gráfico y, de manera correspondiente, su dual.

Para ver la construcción explícita de esta matroide ortogonal dual orientada única, considere el quirótopo de una matroide orientada . Si consideramos una lista de elementos como una permutación cíclica, entonces 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|}),}$

entonces es el quirotopo de la única matroide ortogonal de doble orientación. ^[10] ${\displaystyle \chi ^{*}}$

Representación topológica

Este es un ejemplo de disposición de pseudolínea 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, disposiciones de hiperplanos. Sin embargo, en cierto sentido, todas las matroides orientadas se acercan a darse cuenta de que son disposiciones de hiperplano. En particular, el teorema de representación topológica de Folkman-Lawrence establece que cualquier matroide orientada tiene una realización como una disposición de pseudoesferas . Una pseudoesfera -dimensional es una incrustación de tal que existe un homeomorfismo de modo que se incrusta como un ecuador de . En este sentido, una pseudoesfera es simplemente una esfera mansa (a diferencia de las esferas salvajes ). Una disposición de pseudoesferas es una colección de pseudoesferas que se cruzan a lo largo de pseudoesferas. Finalmente, el teorema de representación topológica de Folkman-Lawrence establece que toda matroide de rango orientada se puede obtener a partir de una disposición de pseudoesfera en . ^[11] Lleva el nombre de Jon Folkman y Jim Lawrence, quienes lo publicaron en 1978. ${\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}}$

Geometría

Un zonotopo, que es una suma de Minkowski de segmentos de línea, es un modelo fundamental para matroides orientadas. Los dieciséis puntos de color 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 derecho es la suma de los signos más izquierdos.

La teoría de las matroides orientadas ha influido en el desarrollo de la geometría combinatoria , especialmente la teoría de los politopos convexos , los zonotopos y las configuraciones de vectores (equivalentemente, disposiciones de hiperplanos ). ^[12] Muchos resultados ( el teorema de Carathéodory , el teorema de Helly , el teorema de Radón , el teorema de Hahn-Banach , el teorema de Krein-Milman , el lema de Farkas ) se pueden formular utilizando matroides orientadas apropiadas. ^[13]

Mejoramiento

En geometría convexa, el algoritmo simplex para programación lineal se interpreta como trazar un camino 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.

R. Tyrrell Rockafellar inició el desarrollo de un sistema de axiomas para matroides orientadas para describir los patrones de signos de las matrices que surgen a través de las operaciones de pivote del algoritmo simplex de Dantzig; Rockafellar se inspiró en los estudios de Albert W. Tucker sobre tales patrones de signos en "Tucker tableaux". ^[14]

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 de pivote , mediante la cual el algoritmo simplex evita ciclos. De manera similar, Terlaky y Zhang lo utilizaron para demostrar que sus algoritmos entrecruzados tienen terminación finita para problemas de programación lineal . Todd y Terlaky obtuvieron resultados similares en programación cuadrática convexa. ^[15] Se ha aplicado a la programación lineal-fraccional , ^{[16] a problemas} de programación cuadrática y a problemas de complementariedad lineal . ^{[17] [18] [19]}

Fuera de la optimización combinatoria , la teoría matroide orientada también aparece en la minimización convexa en la teoría de la "programación monotrópica" de Rockafellar y nociones relacionadas de "descendencia fortificada". ^[20] De manera similar, la teoría matroide ha influido en el desarrollo de algoritmos combinatorios, particularmente el algoritmo codicioso . ^[21] 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 y otros, 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 sobre matroides orientadas, una buena preparación es estudiar el libro de texto sobre optimización lineal de Nering y Tucker, que está lleno de ideas de matroides orientadas, y luego continuar con las conferencias de Ziegler sobre politopos.
4. Björner y otros, Capítulo 7.9.
5. GJ Minty (1966), Sobre los fundamentos axiomáticos de las teorías de gráficos lineales dirigidos, redes eléctricas y programación de redes. J. Matemáticas. Mec. 15: 485–520. Reimpreso en DR Fulkerson, ed., Graph Theory , MAA Study No. 12, Mathematical Association of America.
6. Björner y otros, Capítulo 3.5
7. * Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; Blanco, Neil; Ziegler, Gunter (1999). Matroides orientadas . Enciclopedia de Matemáticas y sus aplicaciones. vol. 46 (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-77750-6. OCLC  776950824. Zbl  0944.52006.
8. Björner y otros, Capítulo 7.9
9. Björner y otros, Capítulo 3.4
10. Björner y otros, Capítulo 3.6
11. Björner y otros, Capítulo 5.2
12. Bachem y Kern, capítulos 1 a 2 y 4 a 9. Björner y otros, capítulos 1 a 8. Ziegler, capítulos 7-8. Bokowski, capítulos 7 a 10.
13. Bachem y Wanka, capítulos 1 a 2, 5, 7 a 9. Björner y otros, capítulo 8.
14. Rockafellar, R. Tyrrell (1969). "Los vectores elementales de un subespacio de R N {\displaystyle R^{N}} (1967)" (PDF) . En RC Bosé ; Thomas A. Dowling (eds.). Matemática Combinatoria y sus Aplicaciones . Serie de monografías sobre 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.
15. Björner y otros, capítulos 8-9. Fukuda y Terlaky. Compárese con Ziegler.
16. Illés, Szirmai y Terlaky (1999)
17. Fukuda y Terlaky (1997)
18. Fukuda y Terlaky (1997, pág.385)
19. Fukuda y Namiki (1994, pág.367)
20. Rockafellar 1984 y 1998.
21. Leyler. Rockafellar 1984 y 1998.

Otras lecturas

Libros

• Bachem, Aquim; Kern, Walter (1992). Dualidad de programación lineal: una introducción a las matroides orientadas . Texto universitario. 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 ; Blanco, Neil; Ziegler, Gunter (1999). Matroides orientadas . Enciclopedia de Matemáticas y sus aplicaciones. vol. 46 (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-77750-6. Zbl  0944.52006.
• Bokowski, Jürgen (2006). Matroides orientadas computacionalmente. Clases de equivalencia de matrices en un marco natural . Prensa de la Universidad de Cambridge . ISBN 978-0-521-84930-2. Zbl  1120.52011.
• Lawler, Eugenio (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. ISBN 9780849385247.

Artículos

• A. Bachem, A. Wanka, Teoremas de separación para matroides orientadas, Matemáticas discretas. 70 (1988) 303–310.
• Suave, Robert G. (1977). "Nuevas reglas de pivote finito para el método simplex". Matemáticas de la Investigación de Operaciones . 2 (2): 103–107. doi :10.1287/moor.2.2.103.
• Folkman, Jon ; Lawrence, Jim (octubre de 1978). "Matroides orientadas". Revista de teoría combinatoria . Serie 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" (PDF) . Programación Matemática, Serie B. 79 (1-3). Ámsterdam: North-Holland Publishing Co.: 369–395. doi :10.1007/BF02614325. SEÑOR  1464775. S2CID  2794181.
• Fukuda, Komei ; Namiki, Makoto (marzo de 1994). "Sobre comportamientos extremos del método de mínimo índice de Murty". Programación Matemática . 64 (1): 365–370. doi :10.1007/BF01582581. SEÑOR  1286455. S2CID  21476636.
• 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 (1969). Los vectores elementales de un subespacio de , en Combinatorial Mathematics and its Applications , RC Bose y TA Dowling (eds.), Univ. de North Carolina Press, págs. 104-127. ${\displaystyle R^{n}}$
• Roos, C. (1990). "Un ejemplo exponencial de la regla pivotante de Terlaky para el método simplex entrecruzado". Programación Matemática . Serie A. 46 (1): 79–84. doi :10.1007/BF01585729. SEÑOR  1045573. S2CID  33463483.
• 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 orientadas". 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: un estudio sobre desarrollos teóricos recientes". Anales de investigación de operaciones . 46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . doi :10.1007/BF02096264. ISSN  0254-5330. SEÑOR  1260019. S2CID  6058077.
• Todd, Michael J. (1985). "Programación lineal y cuadrática en matroides orientadas". Revista de teoría combinatoria . Serie B. 39 (2): 105–133. doi : 10.1016/0095-8956(85)90042-5 .
• Wang, Zhe Min (1987). "Un algoritmo finito libre de eliminación conforme 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, Gunter (1998). "Matroides orientadas hoy". The Electronic Journal of Combinatorics : DS4: 10 de septiembre de 1998. doi :10.37236/25.
• Malkevitch, José. "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