Tesis de Licenciatura

Permanent URI for this collection

Now showing 1 - 1 of 1

Cómputo de la anchura arbórea de un grafo
(2016-01) Arachi Merced, Oscar Rafael; ARACHI MERCED, OSCAR RAFAEL; 901921; GUILLEN GALVAN, CARLOS; 78563
En esta tesis se presentan los conceptos y resultados necesarios para computar la anchura arbórea de un grafo a través de uno de sus árboles de descomposición. Puesto que el concepto de anchura arbórea inicialmente es dado sobre la familia de todos los ´arboles de descomposición del grafo, se presentan resultados de la posibilidad de realizar este computo sobre cualquier elemento de dicha familia. También, se muestra un algoritmo de parámetro fijo tratable (PFT) junto con su implementación en Java. Finalmente, se muestran relaciones de tratabilidad con la posibilidad de expresar una propiedad grafica en lenguaje de lógica monádica de segundo orden y la condición adicional de que la anchura arbórea del grafo sea acotada.”