[1]毛华,史明.利用二元拟阵Kn图的一种建格方法[J].智能系统学报,2017,12(03):333-340.[doi:10.11992/tis.201704022]
 MAO Hua,SHI Ming.A constructive method of lattice using the Kn diagram of binary matroid[J].CAAI Transactions on Intelligent Systems,2017,12(03):333-340.[doi:10.11992/tis.201704022]
点击复制

利用二元拟阵Kn图的一种建格方法(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第12卷
期数:
2017年03期
页码:
333-340
栏目:
出版日期:
2017-06-25

文章信息/Info

Title:
A constructive method of lattice using the Kn diagram of binary matroid
作者:
毛华 史明
河北大学 数学与信息科学学院, 河北 保定 071002
Author(s):
MAO Hua SHI Ming
School of Mathematics and Information Science, Hebei University, Baoding 071002, China
关键词:
二元拟阵标准矩阵表示Kn二部图图论概念格形式背景Hasse示图
Keywords:
binary matroidstandard matrix representativeKn diagrambipartite graphgraph theoryconcept latticeformal contextHasse diagram
分类号:
TP18
DOI:
10.11992/tis.201704022
摘要:
由于交通网络纷繁复杂,难以直观分析和直接处理。若出行者根据自己喜好和习惯决定出行策略,则需对出行方案有清楚的了解。针对此问题,建立交通网络图——Kn模型,对具有带环路和重边路的复杂网络结构图,可以完全转化为Kn图处理。通过概念格理论,得到Hasse示图,方便人们对某些属性条件方案的提取,便于后续工作处理。对Kn图进行研究之后发现,在特定的多个属性影响下,会形成一个三角形圈,于是结合拟阵中二元拟阵的标准矩阵的定义,挖掘出一种特殊形式背景。根据这种形式背景的特殊性,给出基于二元拟阵的Kn图的概念格算法。结合生活中的例子,验证该算法可行性。由于模型具有这种普遍性,所有结果可推广到具有类似形式背景的其他领域研究中。
Abstract:
Because of the complexity of traffic networks, it is difficult to directly analyze and deal with them. If some travelers wish to determine their travel strategy based on their preferences and habits, they should have a clear understanding of their travel plan. To address this problem, a traffic network, Kn model, was established in this study. It was used to elucidate how to transfer complex networks comprising loops or multiple edges to the Kn diagram. With the assistance of formal concept analysis, the corresponding Hasse diagram of the Kn model was provided. The Hasse diagram facilitates travelers to extract some attributes under certain preconditions, after which the travelers can easily continue their work. Hence, the study of the Kn diagram revealed that a triangle circle would form under some effects of specific multiple attributes. Thus, combining with the standard definition of the matrix for binary matroids, a special formal context was obtained. According to the particularity of the formal context, an algorithm was proposed based on the binary matroids for the Kn diagram. Utilizing an example, the feasibility of the proposed method was proven. Because the model is universal, the discussions of this research can be extended to other fields with similar formal context.

参考文献/References:

[1] 左锋. 经济学视野中大城市经济圈的形成与发展—论中国三大城市经济圈的现状及其发展[J]. 华东师范大学学报:哲学社会科学版, 2002, 34(5): 89-95.ZUO Feng. The formation and development of a metropolitan economic circle in the perspec-tive of economics[J]. Journal of east cluna normal university:philosophy and social sciences, 2002, 34(5): 89-95.
[2] 胡一竑. 基于复杂网络的交通网络复杂性研究[D]. 上海:复旦大学, 2008: 1-121.HU Yihong. Analysis of complex transportation networks[D].Shanghai: Fudan University, 2008: 1-121.
[3] 刘佳. 复杂网络中最短路径问题的优化算法研究[D]. 太原: 太原科技大学, 2007: 1-30.LIU Jia. Research on the algorithm for shortest path problem in complicated network[D]. Taiyuan: Taiyuan University of Science and Technology, 2007: 1-30.
[4] 严寒冰, 刘迎春. 基于GIS的城市道路网最短路径算法探讨[J]. 计算机学报, 2000, 23(2): 210-215.YAN Hanbing, LIU Yingchun. A new algorithm for finding shortcut in a city’s road net based on GIS technology[J]. Chinese journal of computers, 2000, 23(2): 210-215.
[5] 谢政, 李建平. 网络算法与复杂性理论[M]. 北京:国防科技大学出版社, 1995: 120-140.
[6] LAM W H K, LI Zhichun, HUANG Haijun, et al. Modeling time-dependent travel choice problems in road networks with multiple user classes and multiple parking facilities[J]. Transportation research part B: methodological, 2006, 40(5): 368-395.
[7] GAO Song, Chabini I. Optimal routing policy problems in stochastic time-dependent networks[J]. Transportation research parB: methodological, 2006, 40(2): 93-122.
[8] 于德新, 杨薇, 杨兆升. 重大灾害条件下基于 GIS的最短路径改进算法[J]. 交通运输工程学报, 2011, 11(4): 123-126.YU Dexin, YANG Wei, YANG Zhaosheng. Shortest path improved algorithm based on GIS under large-scale disaster[J]. Journal of traffic and transportation engineering, 2011, 11(4): 123-126.
[9] 陈京荣. 交通网络路径选择及应用研究[D]. 兰州: 兰州交通大学, 2009: 1-43.CHEN Jingrong. Research on route choice and its application in traffic networks[D]. Lanzhou: Lanzhou Jiaotong University, 2009: 1-43.
[10] GANTER B, Wille R. Formal concept analysis: mathematical foundations[M]. New York: Springer, 1999.
[11] 王树禾. 图论[M]. 北京: 科学出版社, 2009.
[12] BONDY JA. Graph theory[M]. Berlin: Springer Press, 2008.
[13] 刘桂珍,陈庆华. 拟阵[M]. 长沙: 国防科技大学出版社, 1994.
[14] 吉庆兵. 二元拟阵码及其对偶码[J]. 重庆师范学院学报:自然科学版, 2001, 18(4): 48-50.JI Qingbing. Binary matroid codes and their dual codes [J]. Journal of Chongqing normal university:natural science edition, 2001, 18(4): 48-50.
[15] 马对霞, 林姿琼, 祝峰. 拟阵在网络安全中应用[J]. 小型微型计算机系统, 2015, 36(8): 1858-1860.MA Duixia, LIN Ziqiong, ZHU Feng. Application of matroids on network security[J]. Journal of Chinese computer systems, 2015, 36(8): 1858-1860.
[16] 毛华. 拟阵与概念格的关系[J]. 数学进展, 2006, 35(3): 361-365.MAO Hua. The relation between matroid and concept Lattice[J]. Advances in mathematics, 2006, 35(3): 361-365.
[17] 毛华, 李斌. 等价关系约束属性的形式概念分析[J]. 计算机工程与应用, 2010, 46 (36): 158-160.Mao Hua, LI Bin. Formal concept analysis of attributes by equivalent relation[J]. Computer engineering applications, 2010, 46(36): 158-160.
[18] 李立峰, 刘三阳, 罗清君. 弦二部图的概念格表示[J]. 电子学报, 2013, 41(7): 1385-1388.LI Lifeng, LIU Sanyang, LUO Qingjun. Representing chordal bipartite graph using concept lattice theory[J].Chinese journal of electronics, 2013, 41(7): 1385-1388.
[19] 李立峰. 链图的概念格表示[J]. 计算机科学, 2014, 41(2): 264-266.LI Lifeng. Chain graph and their concept lattice representation[J]. Computer science, 2014, 41(2): 264-266.
[20] MAO Hua. A graph-theoretic method to representing a concept lattice[J]. Applied mathematics and information sciences, 2014, 8(2): 553-561.
[21] MAO Hua. Characterizing trees in property-oriented concept lattices[J]. Armenian journal of mathematics, 2016, 8(2): 86-95.
[22] 王海英, 黄强, 李传涛, 等. 图论算法及其MATLAB实现[M]. 北京: 北京航空航天大学出版社, 2010: 1-38.
[23] 李娜. 形式概念分析中若干算法的改进与实现[D]. 北京:中央民族大学, 2007: 1-15.LI Na. Improvement and implementation of several algorithms about formal concept analysis[D]. Beijing: Minzu University of China, 2007: 1-15.

备注/Memo

备注/Memo:
收稿日期:2017-04-19。
基金项目:国家自然科学基金项目(61572011).
作者简介:毛华,女,1963年生,教授,博士后,美国《数学评论》评论员,河北省工业与应用数学学会理事,主要研究方向为计算机数学及其应用、拟阵理论、离散数学。已发表学术论文90余篇,其中被SCI、EI检索20余篇;史明,女,1989年生,硕士研究生,主要研究方向为网络优化、图论、拟阵理论、概念格。已发表学术论文2篇。
通讯作者:史明.E-mail:ming1254610676@163.com.
更新日期/Last Update: 2017-06-25