En matemáticas de teoría de órdenes , un orden parcial serie-paralelo es un conjunto parcialmente ordenado construido a partir de órdenes parciales serie-paralelos más pequeños mediante dos operaciones de composición simples. [1] [2]
Los órdenes parciales serie-paralelo pueden caracterizarse como los órdenes parciales finitos N-libres; tienen una dimensión de orden de dos como máximo. [1] [3] Incluyen órdenes débiles y la relación de alcanzabilidad en árboles dirigidos y grafos serie-paralelo dirigidos . [2] [3] Los grafos de comparabilidad de los órdenes parciales serie-paralelo son cografos . [2] [4]
Los pedidos parciales en serie-paralelo se han aplicado en la programación de talleres , [5] el aprendizaje automático de secuenciación de eventos en datos de series temporales , [6] la secuenciación de transmisión de datos multimedia , [7] y la maximización del rendimiento en la programación del flujo de datos . [8]
Los órdenes parciales en serie-paralelo también se han denominado multiárboles; [4] sin embargo, ese nombre es ambiguo: los multiárboles también se refieren a órdenes parciales sin un suborden de diamante de cuatro elementos [9] y a otras estructuras formadas a partir de múltiples árboles.
Consideremos P y Q , dos conjuntos parcialmente ordenados . La composición de series de P y Q , escrita P ; Q , [7] P * Q , [2] o P ⧀ Q , [1] es el conjunto parcialmente ordenado cuyos elementos son la unión disjunta de los elementos de P y Q . En P ; Q , dos elementos x e y que pertenecen ambos a P o que pertenecen ambos a Q tienen la misma relación de orden que en P o Q respectivamente. Sin embargo, para cada par x , y donde x pertenece a P e y pertenece a Q , hay una relación de orden adicional x ≤ y en la composición de series. La composición de series es una operación asociativa : uno puede escribir P ; Q ; R como la composición de series de tres órdenes, sin ambigüedad sobre cómo combinarlos por pares, porque ambas paréntesis ( P ; Q ); R y P ; ( Q ; R ) describen el mismo orden parcial. Sin embargo, no es una operación conmutativa , porque cambiar los roles de P y Q producirá un orden parcial diferente que invierte las relaciones de orden de los pares con un elemento en P y uno en Q. [ 1]
La composición paralela de P y Q , escrita P || Q , [7] P + Q , [2] o P ⊕ Q , [1] se define de manera similar, a partir de la unión disjunta de los elementos en P y los elementos en Q , con pares de elementos que pertenecen ambos a P o ambos a Q que tienen el mismo orden que en P o Q respectivamente. En P || Q , un par x , y es incomparable siempre que x pertenece a P e y pertenece a Q . La composición paralela es tanto conmutativa como asociativa. [1]
La clase de órdenes parciales serie-paralelo es el conjunto de órdenes parciales que se pueden construir a partir de órdenes parciales de un solo elemento utilizando estas dos operaciones. Equivalentemente, es el conjunto más pequeño de órdenes parciales que incluye el orden parcial de un solo elemento y está cerrado bajo las operaciones de composición en serie y en paralelo. [1] [2]
Un orden débil es el orden parcial paralelo en serie obtenido a partir de una secuencia de operaciones de composición en la que primero se realizan todas las composiciones paralelas y luego se combinan los resultados de estas composiciones utilizando solo composiciones en serie. [2]
El orden parcial N con los cuatro elementos a , b , c y d y exactamente las tres relaciones de orden a ≤ b ≥ c ≤ d es un ejemplo de un conjunto parcial en forma de valla o en zigzag; su diagrama de Hasse tiene la forma de la letra mayúscula "N". No es serie-paralelo, porque no hay forma de dividirlo en la composición en serie o en paralelo de dos órdenes parciales más pequeños. Se dice que un orden parcial P es N-libre si no existe un conjunto de cuatro elementos en P tal que la restricción de P a esos elementos sea orden-isomorfa a N . Los órdenes parciales serie-paralelos son exactamente los órdenes parciales N-libres finitos no vacíos. [1] [2] [3]
De esto se sigue inmediatamente (aunque también se puede demostrar directamente) que cualquier restricción no vacía de un orden parcial serie-paralelo es en sí misma un orden parcial serie-paralelo. [1]
La dimensión de orden de un orden parcial P es el tamaño mínimo de un realizador de P , un conjunto de extensiones lineales de P con la propiedad de que, para cada dos elementos distintos x e y de P , x ≤ y en P si y solo si x tiene una posición anterior a y en cada extensión lineal del realizador. Los órdenes parciales serie-paralelo tienen dimensión de orden como máximo dos. Si P y Q tienen realizadores { L 1 , L 2 } y { L 3 , L 4 }, respectivamente, entonces { L 1 L 3 , L 2 L 4 } es un realizador de la composición en serie P ; Q , y { L 1 L 3 , L 4 L 2 } es un realizador de la composición paralela P || Q . [2] [3] Un orden parcial es serie-paralelo si y solo si tiene un realizador en el que una de las dos permutaciones es la identidad y la otra es una permutación separable .
Se sabe que un orden parcial P tiene dimensión de orden dos si y sólo si existe un orden conjugado Q sobre los mismos elementos, con la propiedad de que cualesquiera dos elementos distintos x e y son comparables exactamente sobre uno de estos dos órdenes. En el caso de órdenes parciales serie-paralelos, un orden conjugado que sea en sí mismo serie-paralelo puede obtenerse realizando una secuencia de operaciones de composición en el mismo orden que las que definen P sobre los mismos elementos, pero realizando una composición serie para cada composición paralela en la descomposición de P y viceversa. Más fuertemente, aunque un orden parcial puede tener muchos conjugados diferentes, cada conjugado de un orden parcial serie-paralelo debe ser en sí mismo serie-paralelo. [2]
Cualquier orden parcial puede representarse (normalmente de más de una manera) mediante un grafo acíclico dirigido en el que existe un camino desde x hasta y siempre que x e y sean elementos del orden parcial con x ≤ y . Los grafos que representan órdenes parciales serie-paralelos de esta manera se han denominado grafos serie-paralelos de vértices, y sus reducciones transitivas (los grafos de las relaciones de recubrimiento del orden parcial) se denominan grafos serie-paralelos de vértices mínimos. [3] Los árboles dirigidos y los grafos serie-paralelos (de dos terminales) son ejemplos de grafos serie-paralelos de vértices mínimos; por lo tanto, los órdenes parciales serie-paralelos pueden utilizarse para representar relaciones de alcanzabilidad en árboles dirigidos y grafos serie-paralelos. [2] [3]
El grafo de comparabilidad de un orden parcial es el grafo no dirigido con un vértice para cada elemento y una arista no dirigida para cada par de elementos distintos x , y con x ≤ y o y ≤ x . Es decir, se forma a partir de un grafo paralelo serie de vértices mínimo olvidando la orientación de cada arista. El grafo de comparabilidad de un orden parcial serie-paralelo es un cografo : las operaciones de composición serie y paralela del orden parcial dan lugar a operaciones en el grafo de comparabilidad que forman la unión disjunta de dos subgrafos o que conectan dos subgrafos por todas las aristas posibles; estas dos operaciones son las operaciones básicas a partir de las cuales se definen los cografos. A la inversa, cada cografo es el grafo de comparabilidad de un orden parcial serie-paralelo. Si un orden parcial tiene un cografo como su gráfico de comparabilidad, entonces debe ser un orden parcial serie-paralelo, porque cualquier otro tipo de orden parcial tiene un suborden N que correspondería a un camino inducido de cuatro vértices en su gráfico de comparabilidad, y tales caminos están prohibidos en los cografos. [2] [4]
La caracterización de suborden prohibido de órdenes parciales serie-paralelo se puede utilizar como base para un algoritmo que prueba si una relación binaria dada es un orden parcial serie-paralelo, en una cantidad de tiempo que es lineal en el número de pares relacionados. [2] [3] Alternativamente, si un orden parcial se describe como el orden de alcanzabilidad de un grafo acíclico dirigido , es posible probar si es un orden parcial serie-paralelo, y si es así calcular su cierre transitivo, en un tiempo proporcional al número de vértices y aristas en el cierre transitivo; queda abierto si el tiempo para reconocer órdenes de alcanzabilidad serie-paralelo se puede mejorar para que sea lineal en el tamaño del grafo de entrada. [10]
Si un orden parcial serie-paralelo se representa como un árbol de expresión que describe las operaciones de composición en serie y en paralelo que lo formaron, entonces los elementos del orden parcial pueden representarse por las hojas del árbol de expresión. Una comparación entre dos elementos cualesquiera puede realizarse algorítmicamente buscando el ancestro común más bajo de las dos hojas correspondientes; si ese ancestro es una composición en paralelo, los dos elementos son incomparables y, de lo contrario, el orden de los operandos de composición en serie determina el orden de los elementos. De esta manera, un orden parcial serie-paralelo sobre n elementos puede representarse en el espacio O ( n ) con tiempo O (1) para determinar cualquier valor de comparación. [2]
Es NP-completo probar, para dos órdenes parciales serie-paralelos P y Q dados , si P contiene una restricción isomorfa a Q. [3 ]
Aunque el problema de contar el número de extensiones lineales de un orden parcial arbitrario es #P-completo , [11] puede resolverse en tiempo polinomial para órdenes parciales serie-paralelo. Específicamente, si L ( P ) denota el número de extensiones lineales de un orden parcial P , entonces L ( P ; Q ) = L ( P ) L ( Q ) y
De modo que el número de extensiones lineales se puede calcular utilizando un árbol de expresión con la misma forma que el árbol de descomposición del orden serie-paralelo dado. [2]
Mannila y Meek (2000) utilizan órdenes parciales en serie-paralelo como modelo para las secuencias de eventos en datos de series temporales . Describen algoritmos de aprendizaje automático para inferir modelos de este tipo y demuestran su eficacia para inferir requisitos previos de cursos a partir de datos de inscripción de estudiantes y para modelar patrones de uso de navegadores web. [6]
Amer et al. (1994) sostienen que los órdenes parciales serie-paralelo son una buena opción para modelar los requisitos de secuenciación de transmisión de presentaciones multimedia . Utilizan la fórmula para calcular el número de extensiones lineales de un orden parcial serie-paralelo como base para analizar algoritmos de transmisión multimedia. [7]
Choudhary et al. (1994) utilizan órdenes parciales en serie-paralelo para modelar las dependencias de tareas en un modelo de flujo de datos de procesamiento masivo de datos para visión artificial . Demuestran que, al utilizar órdenes en serie-paralelo para este problema, es posible construir de manera eficiente un cronograma optimizado que asigna diferentes tareas a diferentes procesadores de un sistema de computación paralela para optimizar el rendimiento del sistema. [8]
Una clase de ordenamientos algo más generales que los órdenes parciales serie-paralelo es proporcionada por los árboles PQ , estructuras de datos que se han aplicado en algoritmos para probar si un grafo es planar y reconocer grafos de intervalo . [12] Un nodo P de un árbol PQ permite todos los posibles ordenamientos de sus hijos, como una composición paralela de órdenes parciales, mientras que un nodo Q requiere que los hijos ocurran en un ordenamiento lineal fijo, como una composición en serie de órdenes parciales. Sin embargo, a diferencia de los órdenes parciales serie-paralelo, los árboles PQ permiten que se invierta el ordenamiento lineal de cualquier nodo Q.
