弦二部图的概念格表示

doi:10.3969/j.issn.0372-2112.2013.07.022

电子学报 ›› 2013, Vol. 41 ›› Issue (7): 1384-1388.DOI: 10.3969/j.issn.0372-2112.2013.07.022

弦二部图的概念格表示

李立峰^1,2, 刘三阳¹, 罗清君³

1. 西安电子科技大学理学院数学系, 陕西西安 710126;
2. 西安邮电大学理学院, 陕西西安 710121;
3. 西安财经学院理学院, 陕西西安 710068

收稿日期:2011-07-27 修回日期:2012-11-20 出版日期:2013-07-25
- 作者简介:
- 李立峰 男,1980年生于西安市长安区,西安电子科技大学博士生,西安邮电大学理学院讲师.主要从事概念格理论的研究.E-mail:hlw12-12@sohu.com
- 基金资助:
- 中央高校基本科研业务费专项资金 (No.K50511700008); 陕西省教育厅自然科学专项基金 (No.11JK1051,No.2013JK1098,No.2013JK1130,No.2013JK1182)

Representing Chordal Bipartite Graph Using Concept Lattice Theory

LI Li-feng^1,2, LIU San-yang¹, LUO Qing-jun³

1. Department of Mathematics, School of Science, Xidian University, Xi'an, Shaanxi 710126, China;
2. School of Science, Xi'an University of Posts and Telecommunications, Xi'an, Shaanxi 710121, China;
3. School of Science, Xi’an University of Finance and Economics, Xi'an, Shaanxi 710068, China

Received:2011-07-27 Revised:2012-11-20 Online:2013-07-25 Published:2013-07-25
- Supported by:
- Fundamental Research Funds for the Central Universities (No.K50511700008); Natural Science Foundation of Education Department of Shaanxi Province (No.11JK1051, No.2013JK1098, No.2013JK1130, No.2013JK1182)

摘要/Abstract

摘要： 本文首先讨论了二部图中双单纯边与概念格中概念之间的对应关系;其次研究了弦二部图和约简的形式背景的若干性质;最后将概念格中元素的消除理论应用于二部图的研究,给出了弦二部图的概念格刻画.结果表明,一个二部图是弦二部图当且仅当对应的概念格中有一个∨∧—不可约元的完美消除序列.

关键词: 知识推理, 约简形式背景, 概念格, 弦二部图, 边完美消除序列

Abstract: In this paper,the relation between bisimplicial edges in a bipartite graph and their corresponding concepts are discussed,and some properties of reduced contexts and chordal bipartite graphs are investigated.Then,we apply the element elimination for a concept lattice to bipartite graph theory,and obtain a representation of chordal bipartite graphs.More precisely,we show that a bipartite graph is chordal bipartite graph if and only if there is a join and meet irreducible element elimination ordering with respect to its corresponding concept lattice.

Key words: reduced context, concept lattice, chordal bipartite graph, perfect edge without vertex elimination ordering

中图分类号:

TP18

李立峰, 刘三阳, 罗清君. 弦二部图的概念格表示[J]. 电子学报, 2013, 41(7): 1384-1388.

LI Li-feng, LIU San-yang, LUO Qing-jun . Representing Chordal Bipartite Graph Using Concept Lattice Theory[J]. Acta Electronica Sinica, 2013, 41(7): 1384-1388.

参考文献

[1] R Wille.Restructuring Lattice Theory:An Approach Based on Hierarchies of Concept[M].R Ivan Rival(ED.),Ordered Sets,Reidel,Dordecht.Boston,1982.445-470.
[2] B Ganter,R Wille.Formal Concept Analysis: Mathematical Foundations[M].Springer-Verlag,Berlin,1999.
[3] 张文修,魏玲,祁建军.概念格的属性约简理论与方法[J].中国科学,E辑2005,35(6):628-639. Zhang Wenxiu,Wei Ling,Qi Jianjun.Attribute reduction theory and approach to concept lattice[J].Science in China(Series E)2005,35(6):628-639.(in Chinese)
[4] L Wei,J J Qi,W X Zhang.Attribute reduction theory of concept lattice based on decision formal contexts[J].Science in China Series F,2008,51(7):910-923.
[5] L F Li,J K Zhang.Attribute reduction in fuzzy concept lattices based on the T implication[J].Knowledge-Based Systems,2010,23(6):497-503.
[6] 李立峰,张东晓.概念格在二值命题逻辑命题集约简中的应用[J].电子学报,2007,35(8):1538-1542. Li-Lifeng,Zhang-Dongxiao.The application of concept lattice theory in the reduction of the proposition set in two-valued propo sitional logic[J].Acta Electronica Sinica,2007,35(8):1538-1542.(in Chinese)
[7] J Amilhastre,M C Vilarem,P Janssen.Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs[J].Discrete Applied Mathematics,1998,86:125-144.
[8] A Berry,A Sigayret.Representing a concept lattice by a graph[J].Discrete Applied Mathematics,2004,144(1-2):27-42.
[9] A Berry,R M McConnell,A Sigayret,J P Spinrad.Very fast instances for concept generation[J].LNCS,2006,3874:119-129.
[10] A Berry,E SanJuanb,A Sigayret.Generalized domination in closure systems[J].Discrete Applied Mathematics,2006,154:1064-1084.
[11] A Brandstadt.Special Graph Classes-A Survey[M].Schrif- tenreihe des Fachbereichs Mathematik,Universitat Duisburg,1991.
[12] T Kloksap,D Kratsch.Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph[J].Information Processing Letters,1995,55:11-16.

弦二部图的概念格表示

Representing Chordal Bipartite Graph Using Concept Lattice Theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

[1]	智慧来, 张丽, 李金海. 旁观者视角下粒的多层次描述[J]. 电子学报, 2022, 50(11): 2568-2574.
[2]	米允龙, 李金海, 刘文奇, 林晶. MapReduce框架下的粒概念认知学习系统研究[J]. 电子学报, 2018, 46(2): 289-297.
[3]	郭晓波, 赵书良, 王长宾, 陈敏. 一种新的面向普通用户的多值属性关联规则可视化挖掘方法[J]. 电子学报, 2015, 43(2): 344-352.
[4]	翟岩慧, 李德玉, 曲开社. 决策蕴涵规范基[J]. 电子学报, 2015, 43(1): 18-23.
[5]	张磊, 张宏莉, 韩道军, 沈夏炯. 基于概念格的RBAC模型中角色最小化问题的理论与算法[J]. 电子学报, 2014, 42(12): 2371-2378.
[6]	智慧来. 面向异构数据分析的形式概念分析扩展模型[J]. 电子学报, 2013, 41(12): 2451-2455.
[7]	杨丽, 徐扬. 基于逻辑合取的语言真值概念格合并算法[J]. 电子学报, 2013, 41(11): 2149-2155.
[8]	智慧来;智东杰;刘宗田. 概念格合并原理与算法[J]. 电子学报, 2010, 38(2): 455-459.
[9]	谢鸿波;吴远成;刘一静;周明天. 一种安全协议的组合分析模型研究[J]. 电子学报, 2008, 36(11): 2262-2267.
[10]	李立峰;张东晓. 概念格在二值命题逻辑命题集约简中的应用[J]. 电子学报, 2007, 35(8): 1538-1542.
[11]	强宇, 刘宗田, 林炜, 时百胜, 李云. 模糊概念格在知识发现的应用及一种构造算法[J]. 电子学报, 2005, 33(2): 350-353.
[12]	李云;刘宗田;陈 ;徐晓华;程伟. 多概念格的横向合并算法[J]. 电子学报, 2004, 32(11): 1849-1854.