Minimização de Modelos de Grafos 2-Dir Puros
Autores
|
2026 |
413,863,416
|
|
|
2027 |
413,863,416
|
|
|
6469 |
413,863,416
|
Informações:
Publicações do PESC
Nesta tese consideramos a classe dos gratos 2-DIR PUROS, também conhecidos na literatura como grafos de interseção em grade. Sejam I e J famílias finitas de segmentos horizontais e verticais no plano, onde segmentos na mesma direção não se interceptam. O grafo de interseção G de I U J é conhecido como grafo 2-DIR PURO. É claro que G é um grato bipartido G = (L, N), onde os conjuntos L e N correspondem aos segmentos de I e J, respectivamente.
O primeiro resultado desta tese é um Teorema de Caracterização para grafos 2-DIR PUROS através de uma ordenação apropriada dos vértices em cada conjunto da bipartição. Esta caracterização induz a definição de modelo de grade: um modelo de interseção de segmentos sobre a grade formada pelas interseções das retas x = i, i = 1,...,s e y = k, k = 1,...,r. Mostramos que todo grafo 2-DIR PURO G = (L, N) de grau mínimo 2 com |L |= r e | N |= s tem um modelo sobre a grade s x r.
A seguir, tratamos do problema de minimização de modelos de grade, isto é, obtenção de modelos onde a soma dos comprimentos dos segmentos que representam os vértices é mínima. Mostramos que este problema, na sua versão de decisão, é N P-completo.
Finalmente, apresentaremos um modelo de programação inteira mista que reconhece se um determinado grafo G bipartido pertence ou não à classe de grafos 2-DIR PUROS e minimiza seu modelo de grade, se existir.
This thesis considers the class of PURE-2-DIR graphs, also known in the literature as grid intersection graphs. Let I and J be finite families of horizontal and vertical linear segments in the plane, such that no two horizontal or vertical segments intersect. The intersection graph G of I U J is called a PURE-2-DIR graph. It is clear that G is a bipartite graph G = (W,U), where the sets W and U correspond to the segments in I and J, respectively.
The first result of this thesis is a Characterization Theorem for PURE-2-DIR graphs in terms of orderings in each partition of the vertex set. This characterization induces the definition of grid model: a intersection model of segments placed on the grid formed by the intersections of the lines x = i, i = 1,...,s e y = k, k = 1,...,r. It is shown that every PURE-2-DIR G = (L, N) of minimum degree two with |L |= r and | N |= s has a model on the grid s x r.
Next, we deal with the problem of minimizing grid models, that is, obtaining models where the sum of the lenghts of the segments representing the vertices is minimum. It is shown that this problem, in its decision version, is NP-complete.
Finally, it is presented a mixed integer programming model that recognizes whether a given bipartite graph G belongs or not to the classe of PURE-2-DIR graphs, and minimizes its grid model, if it exists.