主题
Search

多重图


Multigraph

术语多重图指的是一种图,其中节点之间允许多条边(Harary 1994, p. 10; Gross and Yellen 1999, p. 4)或要求有多条边(Skiena 1990, p. 89, Pemmaraju and Skiena 2003, p. 198; Zwillinger 2003, p. 220)。West (2000, p. xiv) 建议完全避免使用该术语,理由是其含义模糊不清。

一些参考文献要求多重图不包含图环(Harary 1994, p. 10; Gross and Yellen 1999, p. 4; Zwillinger 2003, p. 220),一些参考文献明确允许包含图环(Hartsfield and Ringel 1994, p. 7; Cormen et al. 2001, p. 89),还有一些参考文献既没有明确允许也没有明确禁止包含图环(Skiena 1990, p. 89; Gross and Yellen 1999, p. 351; Pemmaraju and Skiena 2003, p. 198)。更糟糕的是,Tutte (1998, p. 2) 使用术语“多重图”来表示包含环或多条边的图。

由于存在诸多歧义,因此应弃用术语“多重图”,或者至少在使用时应极其谨慎。


另请参阅

边重数, 图环, 图重数, 超图, 柯尼斯堡桥问题, 混合图, 多重边, 伪图, 简单图

使用 Wolfram|Alpha 探索

参考文献

Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; and Stein, C. 算法导论,第 2 版 Cambridge, MA: MIT Press, 2001.Grimaldi, R. P. 离散与组合数学:应用导论,第 4 版 Longman, 1998.Gross, J. T. and Yellen, J. 图论及其应用 Boca Raton, FL: CRC Press, 1999.Harary, F. 图论 Reading, MA: Addison-Wesley, p. 10, 1994.Hartsfield, N. and Ringel, G. 图论中的明珠:综合导论,第 2 版 San Diego, CA: Academic Press, 1994.Pemmaraju, S. and Skiena, S. 计算离散数学:组合学与图论(使用 Mathematica) Cambridge, England: Cambridge University Press, 2003.Skiena, S. 离散数学实现:组合学与图论(使用 Mathematica) Reading, MA: Addison-Wesley, 1990.Tutte, W. T. 我所了解的图论 Oxford, England: Oxford University Press, 1998.West, D. B. 图论导论,第 2 版 Englewood Cliffs, NJ: Prentice-Hall, 2000.Zwillinger, D. (Ed.). CRC 标准数学表格和公式,第 31 版 Boca Raton, FL: CRC Press, 2003.

在 Wolfram|Alpha 中被引用

多重图

引用为

Weisstein, Eric W. "多重图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Multigraph.html

主题分类