Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones
PDF (Español (España))

Keywords

graph theory
graph isomorphism
Frobenius problem
teoría de grafos
isomorfismo de grafos
problema de Frobenius

How to Cite

Bulat, M. (1998). Isomorfismo de grafos y de funciones lógicas con algunas aplicaciones. Revista De Matemática: Teoría Y Aplicaciones, 5(2), 87–112. https://doi.org/10.15517/rmta.v5i2.157

Abstract

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.

https://doi.org/10.15517/rmta.v5i2.157
PDF (Español (España))

Comments

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Copyright (c) 1998 Mijail Bulat

Downloads

Download data is not yet available.