无标度Sierpi(n)ski网络上的匹配与最大匹配数目

摘要

计数问题是复杂网络上一类很重要的问题,其中比较典型的是网络的匹配问题.然而,在一般图中求解最大匹配数是很困难的,甚至在二分图上都是一个NP完全问题.在复杂网络的研究中,Sierpi(n)ski网络是一类有着重要研究意义的网络.无标度Sierpi(n)ski网络是从经典的Sierpi(n)ski分形垫映射而来.算法利用无标度Sierpi(n)ski网络的结构特点,总结其匹配的规律,求解其匹配数目的解析表达式.利用匹配与边覆盖之间的关系给出无标度Sierpinski网络边覆盖数以及最大匹配数目的递推表达式.