Sobre o Número de Saltos em Ordens Parciais
Autores
|
4900 |
2194,6,413
|
|
|
4901 |
2194,6,413
|
|
|
4902 |
2194,6,413
|
Informações:
Publicações do PESC
O problema do número de saltos de uma extensão linear é muito relevante na teoria de ordens e escalonamento de tarefas. Nesta tese trataremos de uma generalização do mesmo.
Seja $\\\\mathcal{P}=(X,P)$ uma ordem parcial finita. Definimos o conceito de extensões arbóreas mínimas e minimais de uma ordem $\\\\mathcal{P}=(X,P)$ e o número de saltos arbóreos de uma ordem $P$. Tratamos o problema de encontrar a extensão arbórea $\\\\mathcal{A}$ de uma ordem $P$ obtida adicionando um número mínimo de novas relações ao diagrama de Hasse de $P$. Além disso enunciamos o problema de encontrar extensões arbóreas que possuam um número total de saltos arbóreos mínimo. Demonstramos que determinar o número mínimo de saltos arbóreos da ordem $P$ é um problema $NP-$completo e conjecturamos que o problema de encontrar o número mínimo de saltos arbóreos totais que estende uma ordem $P$ a uma ordem arbórea também seja $NP-$completo.
Resolvemos o problema do número de saltos arbóreos para algumas classes de ordens: ordens livre de $N$, série paralelo, bipartidas e obtemos um resultado para os reticulados.
Mostramos que os elementos maximais de uma ordem $P$ livre de $N$ são preservados nas suas extensões arbóreas mínimas, e também verificamos a existência de uma extensão arbórea minimal, de uma ordem $P$ qualquer, que preserva os elementos maximais.
The jump number problem of a linear extension is very important in order theory and scheduling. In this thesis, we give a generalization for this problem.
Let $\\\\mathcal{P}=(X,P)$ be a partial order. We define minimum and minimals arboreal extensions of an order $\\\\mathcal{P}=(X,P)$ and the arboreal jump number of a order $P$. We study the problem of finding the arboreal extension $\\\\mathcal{A}$ of an order $P$ that has a minimum number of new relations added to the Hasse diagram of $P$. Moreover, we state the problem of finding the arboreal extensions that has the minimum number of arboreal jumps. We show that the determination of a minimum number of new relations added to the Hasse diagram of an order $P$, aiming to transform it into an arboreal extension, is an $NP-$complete problem and we conjecture that the problem of finding the minimum total number of jumps that extends an order $P$ to an arboreal order is also $NP-$complete.
We solve the problem of the arboreal jump number for some order classes: $N$-free orders, parallel series orders, bipartite orders and we obtain a result for the lattices.
We show that the maximal elements of an $N-$free order $P$ are preserved in its minimum arboreal extensions, and we also show the existence of a minimal arboreal extension of any order $P$ that preserves the maximal elements.