查询结果:   江青宇.无标度Sierpiński网络上的匹配与最大匹配数目[J].计算机应用与软件,2018,35(12):49 - 53.
中文标题
无标度Sierpiński网络上的匹配与最大匹配数目
发表栏目
应用技术与研究
摘要点击数
210
英文标题
MATCHING AND MAXIMUM MATCHING NUMBER IN SCALE-FREE SIERPINSKI NETWORKS
作 者
江青宇 Jiang Qingyu
作者单位
复旦大学计算机科学技术学院 上海 200433     
英文单位
School of Computer Science, Fudan University, Shanghai 200433, China     
关键词
复杂网络 无标度Sierpiński网络 匹配 边覆盖 最大匹配数目
Keywords
Complex network Scale-free Sierpiński networks Matching Edge coverage Maximum matching number
基金项目
国家自然科学基金项目(11275049)
作者资料
江青宇,硕士生,主研领域:算法与计算复杂性。 。
文章摘要
计数问题是复杂网络上一类很重要的问题,其中比较典型的是网络的匹配问题。然而,在一般图中求解最大匹配数是很困难的,甚至在二分图上都是一个NP完全问题。在复杂网络的研究中,Sierpiński网络是一类有着重要研究意义的网络。无标度Sierpiński网络是从经典的Sierpiński分形垫映射而来。算法利用无标度Sierpiński网络的结构特点,总结其匹配的规律,求解其匹配数目的解析表达式。利用匹配与边覆盖之间的关系给出无标度Sierpinski网络边覆盖数以及最大匹配数目的递推表达式。
Abstract
Counting problem is one of the most important problems in complex networks. The matching problem is a typical representative. It is very difficult to find the maximum matching number in a general graph, even in a bipartite graph it is a NP-complete problem. In the studies of complex networks, Sierpiński networks are a kind of networks with important research significance. The scale-free Sierpiński networks are derived from the classical Sierpiński gasket. According to the structural characteristics of scale-free Sierpiński networks, we summarized its matching rules and solved an analytical expression for its matching number. On the basis of the relationship between matching and edge coverage, the number of edge coverage was given. And recursive expression of maximum matching number was obtained.
下载PDF全文