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

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

Full description

Bibliographic Details
Main Author:	Bulat, Mijail
Format:	Online
Language:	spa
Published:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 1998
Online Access:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/157

id	RMTA157
record_format	ojs
spelling	RMTA1572021-10-26T15:17:38Z Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones Bulat, Mijail graph theory graph isomorphism Frobenius problem teoría de grafos isomorfismo de grafos problema de Frobenius 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. 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 1998-08-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/157 10.15517/rmta.v5i2.157 Revista de Matemática: Teoría y Aplicaciones; Vol. 5 No. 2 (1998): Revista de Matemática: Teoría y Aplicaciones; 87-112 Revista de Matemática: Teoría y Aplicaciones; Vol. 5 Núm. 2 (1998): Revista de Matemática: Teoría y Aplicaciones; 87-112 Revista de Matemática; Vol. 5 N.º 2 (1998): Revista de Matemática: Teoría y Aplicaciones; 87-112 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/157/137 Derechos de autor 1998 Mijail Bulat https://creativecommons.org/licenses/by-nc-sa/4.0
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Bulat, Mijail
spellingShingle	Bulat, Mijail Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
author_facet	Bulat, Mijail
author_sort	Bulat, Mijail
description	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.
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
title_alt	Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	1998
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/157
work_keys_str_mv	AT bulatmijail isomorfismodegrafosydefuncioneslogicasconalgunasaplicaciones
_version_	1811744053209858048

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

Similar Items