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 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
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 ,, combina un conjunto de objetos con una partición de ese conjunto en dos subconjuntos: y .
- Los miembros de se denominan elementos positivos ; miembros de son los elementos negativos .
- El conjunto se llama el apoyo de.
- El conjunto firmado vacío ,, se define como el conjunto vacío combinado con una "partición" del mismo en dos conjuntos vacíos: y .
- El conjunto firmado es lo contrario de, es decir, , si y solo si y
Dado un elemento del apoyo , 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.
Axiomatizaciones
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
Dejar ser cualquier conjunto. Nos referimos acomo el terreno establecido . Dejarser una colección de conjuntos firmados , cada uno de los cuales está respaldado por un subconjunto de. Si los siguientes axiomas son válidos para, luego de manera equivalente es el conjunto de circuitos firmados para una matroide orientada en.
- (C0)
- (C1) (simétrico)
- (C2) (incomparable)
- (C3) (eliminación débil)
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:
- para todos ,
- para todos , y , hay un , tal que
- ,
- , y
- .
Axiomas de quirótopo
Dejar sea como arriba. Para cada entero no negativo, un quirótopo de rango es una función que satisfaga los siguientes axiomas:
- (B0) (no trivial) : no es idénticamente cero
- (B1) (alternando) : para cualquier permutación y , , dónde es el signo de la permutación.
- (B2) (intercambio) : Para cualquier tal que para cada , entonces también tenemos .
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 una matroide en que consiste en aquellos -subconjuntos de elementos que asigna 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 es una base. Luego se puede firmar con elementos positivos
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
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 firmadoes 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 concuerde con el sentido a 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 esos , luego es el conjunto de circuitos con signo de una matroide orientada en el conjunto de aristas del grafo dirigido.
Si consideramos el gráfico dirigido a la derecha, podemos ver que solo hay dos circuitos, a saber y . Entonces solo hay cuatro posibles circuitos con signo correspondientes a las orientaciones en sentido horario y antihorario, a saber, , , y . Estos cuatro conjuntos forman el conjunto de circuitos firmados de una matroide orientada en el conjunto.
Álgebra lineal
Si es cualquier 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 orientados, para cada circuito hay una dependencia lineal mínima
con . Entonces el circuito firmado tiene elementos positivos y elementos negativos . El conjunto de todos esos 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 .
Dado el mismo conjunto de vectores , podemos definir el mismo matroide orientado con un quirótopo . Para cualquier dejar
donde el lado derecho de la ecuación es el signo del determinante . Luego es el quirótopo del mismo matroide orientado en el set .
Arreglos de hiperplano
Una verdadera disposición de hiperplano es un conjunto finito de hiperplanos en , cada uno con 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 puntoal set firmado 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]
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
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 esta matroide de orientación dual ortogonal única, considere el quirótopo de una matroide orientada . Si consideramos una lista de elementos de como una permutación cíclica entonces definimos para ser el signo de la permutación asociada. Si Se define como
luego es el quirótopo de la única matroide ortogonal de orientación dual. [9]
Representación topológica
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 . A-pseudoesfera dimensional es una incrustación de tal que existe un homeomorfismo así que eso incrusta como un ecuador de . En este sentido, una pseudoesfera es solo una esfera domesticada (a diferencia de las esferas salvajes ). Un arreglo de pseudoesfera enes 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 cada matroide orientado de rango puede obtenerse de una disposición de pseudoesferas en . [10] Lleva el nombre de Jon Folkman y Jim Lawrence, quienes lo publicaron en 1978.
Geometría
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
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 la programación lineal-fraccionaria , [15] problemas de programación cuadrática 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
- ^ 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.
- ↑ Björner et alia, Capítulos 1-3. Bokowski, capítulos 1-4.
- ↑ 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.
- ↑ Björner et alia, Capítulo 7.9.
- ↑ Björner et alia, Capítulo 3.5
- ^ * 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 .
- ↑ Björner et alia, Capítulo 7.9
- ↑ Björner et alia, Capítulo 3.4
- ↑ Björner et alia, Capítulo 3.6
- ↑ Björner et alia, Capítulo 5.2
- ^ 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.
- ↑ Bachem y Wanka, Capítulos 1-2, 5, 7-9. Björner et alia, Capítulo 8.
- ^ Rockafellar, R. Tyrrell (1969). "Los vectores elementales de un subespacio de R norte {\ Displaystyle R ^ {N}} (1967) " (PDF) . En RC Bose ; Thomas A. Dowling (eds.). Matemáticas combinatorias y sus aplicaciones . Serie de monografías de la Universidad de Carolina del Norte en Probabilidad y Estadística. Chapel Hill, Carolina del Norte: University of North Carolina Press , págs. 104 a 127. MR 0278972 .
- ↑ Björner et alia, Capítulos 8–9. Fukuda y Terlaky. Compárese con Ziegler.
- ^ Illés, Szirmai y Terlaky (1999)
- ^ Fukuda y Terlaky (1997)
- ^ Fukuda y Terlaky (1997 , p. 385)
- ^ Fukuda y Namiki (1994 , p. 367)
- ^ Rockafellar 1984 y 1998.
- ^ 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.
- 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