Hipergrafos Direcionados
Autores
2049 |
303,877,876
|
|
2050 |
303,877,876
|
|
2051 |
303,877,876
|
Informações:
Publicações do PESC
Este trabalho trata de hipergrafos direcionados, que são uma generalização de grafos direcionados. É feita uma reestruturação da teoria dos hipergrafos direcionados, que até então era formada por conceitos isolados e muitas vezes divergentes.
O conceito de planaridade de grafos é estendido para hipergrafos direcionados de uma forma bastante simples e direta, relacionando a planaridade de um hipergrafo direcionado com a planaridade de um grafo construído a partir do hipergrafo.
A classe dos hipergrafos redutíveis é apresentada como uma generalização dos grafos redutíveis. Para chegarmos nesta generalização, partimos das idéias originais de redutibilidade, usando o conceito de intervalos.
Com o objetivo de modelar o fluxo de controle de programas paralelos, a classe dos hipergrafos Serial-Paralelo-Disjunção é apresentada. É provado que um hipergrafo desta classe é redutível e apresentamos uma solução polinomial para o problema de encontrar um conjunto de vértices de realimentação (feedback vertex set) quando restrito a esta classe.
This work studies directed hypergraphs, that generalize the concept of directed graphs (digraphs). The theoretical concepts about directed hypergraphs are organized in a well structured framework.
The concept of directed hypergraph planarity is presented based on the well known concept of graph planarity.
The class of reducible directed hypergraphs is presented as a generalization of reducible flow graphs. In arder to obtain such generalizaton the original ideas of contraction of intervals were used.
To model the contra flow of parallel programs, the class of Serial-Paralell-Disjunction hypergraphs are presented and proved to be reducible. A polinomial solution to the feedback vertex set problem when restricted to such class is presented.