Alguns Resultados em Espessura de Grafos
Autores
|
6261 |
414,413,2845
|
|
|
6262 |
414,413,2845
|
|
|
6263 |
414,413,2845
|
Informações:
Publicações do PESC
Este trabalho descreve dois conceitos importantes relativos à espessura de um grafo. A espessura de um grafo G = (V, E) é o número mínimo de subgrafos planares necessários para decompor o grafo G. O primeiro conceito mostra uma fórmula para a espessura de um grafo completo Kn, em função do número n de vértices, exibindo os passos da decomposição deste grafo. O segundo conceito apresenta uma prova da NP-completude do problema de decisão de espessura, mesmo considerando k = 2, onde k é o tamanho da espessura de um grafo G.
This work describes two important signification about thickness of graphs. The tickness of a graph G = (V, E) is the minimum number of planar subgraphs needed to decompose the graph G. The first shows a formula for thickness of a complete graph Kn, showing the steps of decomposition this graph. The second shows a proof of the NP completeness of the decision problem THICKNESS, even k = 2, where k is the size of thickness of the graph G.