首页 | 本学科首页   官方微博 | 高级检索  
     检索      

布尔矩阵的可实现问题及其与色数问题的关系
引用本文:王学平,杨雁.布尔矩阵的可实现问题及其与色数问题的关系[J].高校应用数学学报(A辑),2010,25(1).
作者姓名:王学平  杨雁
作者单位:1. 四川师范大学数学与软件科学学院,四川成都,610066
2. 西南石油大学理学院,四川成都,610500
基金项目:国家自然科学基金,四川省青年基金 
摘    要:讨论了布尔矩阵的可实现问题及其与色数问题的关系.首先给出布尔矩阵可实现的一些充要条件,讨论可实现布尔矩阵的性质,其次证明可实现布尔矩阵的容度等于该矩阵所生成的图的色数;简单图的邻接矩阵的对偶阵是可实现的,且其容度就是简单图的色数的一个上界.

关 键 词:可实现布尔矩阵  容度  简单图  色数

Realizable problems of Boolean matrices and the relations between realizable Boolean matrices and chromatic number of graphs
WANG Xue-ping,YANG Yan.Realizable problems of Boolean matrices and the relations between realizable Boolean matrices and chromatic number of graphs[J].Applied Mathematics A Journal of Chinese Universities,2010,25(1).
Authors:WANG Xue-ping  YANG Yan
Abstract:The realizable problems of Boolean matrices and the relations between realizable Boolean matrices and the chromatic number of graphs are discussed. This paper first gives some necessary and sufficient conditions that Boolean matrices are realizable, investigates the properties of realizable Boolean matrices, then proves that the content of a realizable Boolean matrix is the chromatic number of graph which is generated by the realizable Boolean matrix, and shows that the dual matrix of adjacency matrix of a simple graph is realizable and its content is an upper bound for the chromatic number of the same graph.
Keywords:realizable Boolean matrix  content  simple graph  chromatic number
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号