关于变换图同构的若干定理
Some Theorems on Isomorphism of Interchange Graphs
金晶晶1
作者信息
- 1. 福建船政交通职业学院,福建 福州 350007
- 折叠
摘要
(0,1)矩阵是矩阵论、密码学、组合数学与图论的重要研究工具,已广泛应用于图像处理、信息网络、生物网络等实际问题.自Richard A.Brualdi于1980年提出关于(0,1)矩阵变换图的Brualdi猜想以来,国内外许多组合图论专家学者致力于(0,1)矩阵变换图研究.在国内外已有研究基础上,研究变换图同构的若干定理,为Brualdi猜想提供新路径.本文首先证明在(0,1)矩阵类U(R,S)中,两个互为补矩阵类的变换图同构,两个转置矩阵的变换图同构,多次互换矩阵任意两行(或列)得到的新矩阵的变换图与原矩阵变换图同构.进而证明若两个(0,1)矩阵类的行(列)和向量在非饱和列上的元素组合相同,则这两个变换图同构.最后,提出若干有待解决的问题.
Abstract
The(0,1)matrix is a crucial research tool in the fields of matrix theory,cryptography,combinatorial mathematics,and graph theory.It has found extensive applications in image processing,information networks,biological networks,and other practical problems.Since Richard A.Brualdi proposed the Brualdi conjecture regarding(0,1)matrix interchange graphs in 1980,numerous experts and scholars in combinatorial and graph theory have dedicated themselves to studying these graphs.This paper builds upon the existing research at home and abroad to investigate theorems related to isomorphism of interchange graphs,and provides new direction for exploring the Brualdi conjecture.Within the U(R,S)of(0,1)matrices class,we proved that the interchange graphs of complementary matrices are isomorphic.The interchange graphs of two transposed matrices is isomorphic.Additionally,the interchange graphs of matrices obtained by transforming any two rows(or columns)multiple times are isomorphic to the original matrix interchange graphs.If the rows(columns)sum vectors of two(0,1)matrixs classes have the same combination of elements on unsaturated row(column),then these two interchange graphs are isomorphic.Finally,we put forward some problems remaining to be solved.
关键词
变换图/(0,1)矩阵/同构/饱和行(列)Key words
interchange graph/(0,1)matrix/isomorphism/saturated row(column)引用本文复制引用
出版年
2024
NETL
NSTL
万方数据