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

A 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...

Full description

Main Author: Bulat, Mijail
Format: Artículo
Language: Español
Published: 2015
Online Access: http://revistas.ucr.ac.cr/index.php/matematica/article/view/157
http://hdl.handle.net/10669/12792
id RepoKERWA12792
recordtype dspace
spelling RepoKERWA127922017-08-08T18:50:12Z Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones Bulat, Mijail A 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. Se 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 2015-05-19T18:09:28Z 2015-05-19T18:09:28Z 2009-02-18 00:00:00 2015-05-19T18:09:28Z info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion http://revistas.ucr.ac.cr/index.php/matematica/article/view/157 http://hdl.handle.net/10669/12792 10.15517/rmta.v5i2.157 es Revista de Matemática: Teoría y Aplicaciones Vol. 5 Núm. 2 2009 87-112 application/pdf
institution Universidad de Costa Rica
collection Repositorio KERWA
language Español
description A 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.
format Artículo
author Bulat, Mijail
spellingShingle Bulat, Mijail
Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
author_sort Bulat, Mijail
title Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
title_short Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
title_full Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
title_fullStr Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
title_full_unstemmed Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
title_sort isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
publishDate 2015
url http://revistas.ucr.ac.cr/index.php/matematica/article/view/157
http://hdl.handle.net/10669/12792
_version_ 1658177853950263296
score 11.79289