Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones

dc.creatorBulat, Mijail
dc.date.accessioned2015-05-19T18:09:28Z
dc.date.available2015-05-19T18:09:28Z
dc.date.issued2009-02-18 00:00:00
dc.date.updated2015-05-19T18:09:28Z
dc.description.abstractA method to solve the isomorphism problem for graphs is suggested, which significantly decreases the number of variants to be checked. Based on the substitution of two successions, the necessary and sufficient conditions are given for the existence of the isomorphism. The method is applicable to any graphs (directed, undirected, weighted etc.) and hypergraphs. With some modifications it can be applied for solving isomorphism problem for logical functions. Some applications are considered:   1. search for hamiltonian cycles (paths)   2. solutions of the Frobenius problem for strongly equivalent matrices,   3. conding inside states of the finite automate.Keywords: graph theory, graph isomorphism, Frobenius problem.
dc.description.abstractSe propone un método de solución del problema de isomorfismo para grafos que permite reducir esencialmente el sondeo de variantes durante el proceso de solución. En la base de dos sucesiones de sustituciones se dan las condiciones necesarias y suficientes de la existencia de isomorfismo. El método se aplica para cualesquiera grafos (dirigidos, no – dirigidos, pesados y etc.) e hipergrafos. Con algunas modificaciones se usa para resolver el mismo problema para funciones lógicas. Se examinan unas aplicaciones:   1. la búsqueda de los ciclos (cadenas) hamiltonianos,   2. la solución del problema de Frobenius para matrices equivalentes,   3. la codificación de los estados interiores de la máquina finita.Palabras clave: teoría de grafos, isomorfismo de grafos, problema de Frobenius
dc.format.extent87-112
dc.identifier.citationhttp://revistas.ucr.ac.cr/index.php/matematica/article/view/157
dc.identifier.doi10.15517/rmta.v5i2.157
dc.identifier.issn
dc.identifier.urihttps://hdl.handle.net/10669/12792
dc.language.rfc3066es
dc.relation.ispartofRevista de Matemática: Teoría y Aplicaciones Vol. 5 Núm. 2 2009
dc.titleIsomorfismo de grafos y de funciones lógicas con algunas aplicaciones
dc.titleIsomorfismo de grafos y de funciones lógicas con algunas aplicaciones
dc.typeartículo original

Archivos

Bloque original
Mostrando 1 - 1 de 1
Cargando...
Miniatura
Nombre:
157-368-1-PB.pdf
Tamaño:
344.75 KB
Formato:
Adobe Portable Document Format
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
2.37 KB
Formato:
Item-specific license agreed upon to submission
Descripción: