Implementación de un Método para generar Coberturas de Aristas en Grafos Simples

Publicación:
Entidad Editora:
Editor Técnico:
ISSN:
Ejemplar/Número:

Cateoría:
Páginas:
Colección:
Fecha de inicio:
Periodicidad:

Programación Matemática y Software
Universidad Autónoma del Estado de Morelos
Dr.Marco Antonio Cruz Chávez
2007-3283
Volumen 9, Número 1 /Febrero del 2017
Periodo Febrero-Mayo 2017
Artículo de Investigación
11-19
Computación
Febrero del 2017
Cuatrimestral

L. E. Sierra-Alva, J. Raymundo Marcial-Romero, J. A. Hernández, Guillermo de Ita

Cerro de Coatepec s/n, Ciudad Universitaria, Facultad de Ingeniería, UAEM, 50100, Toluca, Estado de México, México.

Avenida San Claudio y 14 sur, Ciudad Universitaria, Facultad de Ciencias de la Computación, BUAP, 72592, Puebla, México.

Recibido:31 de julio de 2015  Aceptado:18 de febrero de 2016 Publicado en línea: 28 de febrero de 2017

Resumen: En este artículo se presenta un algoritmo para contar las coberturas de aristas de un grafo. El algoritmo, implementado en el lenguaje de programación C++, consiste en dividir el grafo original en subgrafos que cumplan con la propiedad de no tener cíclicos intersectados (ciclos compartidos). Cada subgrafo constituye un nodo de un árbol de subgrafos en donde las hojas del árbol son grafos sin ciclos intersectados. Por lo tanto, el conteo de coberturas se puede realizar sobre las hojas del árbol.

Palabras claves: Cobertura de Aristas, Teoría de Grafos, Problemas #P

Abstract: In this article we present an algorithm for counting edge covers of graphs. The algorithm, implemented in the C language, divides the input graph into subgraphs until no intersected cycles are presented (shared cycles). Each subgraph constitutes a node of a tree where the leaves are su subgraphs without intersected cycles. Hence, the edge covers counting is carry on on the leaves of the tree.

Keywords: Maxwell equations, finite volume, code Saturn, and Salome