...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Statistical Physics >Tutte Polynomial of Pseudofractal Scale-Free Web
【24h】

Tutte Polynomial of Pseudofractal Scale-Free Web

机译：伪分形无标度Web的Tutte多项式

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The Tutte polynomial of a graph is a 2-variable polynomial which is quite important in both Combinatorics and Statistical physics. It contains various numerical invariants and polynomial invariants, such as the number of spanning trees, the number of spanning forests, the number of acyclic orientations, the reliability polynomial, chromatic polynomial and flow polynomial. In this paper, we study and obtain a recursive formula for the Tutte polynomial of pseudofractal scale-free web (PSFW), and thus logarithmic complexity algorithm to calculate the Tutte polynomial of the PSFW is obtained, although it is NP-hard for general graph. By solving the recurrence relations derived from the Tutte polynomial, the rigorous solution for the number of spanning trees of the PSFW is obtained. Therefore, an alternative approach to determine explicitly the number of spanning trees of the PSFW is given. Furthermore, we analyze the all-terminal reliability of the PSFW and compare the results with those of the Sierpinski gasket which has the same number of nodes and edges as the PSFW. In contrast with the well-known conclusion that inhomogeneous networks (e.g., scale-free networks) are more robust than homogeneous networks (i.e., networks in which each node has approximately the same number of links) with respect to random deletion of nodes, the Sierpinski gasket (which is a homogeneous network), as our results show, is more robust than the PSFW (which is an inhomogeneous network) with respect to random edge failures.
机译：图的Tutte多项式是2变量多项式，在组合物理学和统计物理学中都非常重要。它包含各种数值不变量和多项式不变量，例如生成树的数量，生成林的数量，非循环定向的数量，可靠性多项式，色多项式和流多项式。本文研究并获得了伪分形无标度网（PSFW）的Tutte多项式的递推公式，从而获得了对数复杂度算法来计算PSFW的Tutte多项式，尽管它对于一般图来说是NP-hard 。通过求解从Tutte多项式导出的递归关系，可以获得PSFW生成树数的严格解。因此，给出了另一种明确确定PSFW的生成树数量的方法。此外，我们分析了PSFW的所有端子可靠性，并将结果与​​Sierpinski垫圈的结点和边数与PSFW相同的结果进行了比较。与众所周知的结论相反，就节点的随机删除而言，非均质网络（例如，无标度网络）比同质网络（即，每个节点具有大约相同数量的链接的网络）更健壮，正如我们的结果所示，就随机边缘故障而言，Sierpinski垫片（这是同构网络）比PSFW（这是不均匀网络）更坚固。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号