主题
Search

测地线图


Ore (1962) 指出,不仅在任意两个顶点之间具有唯一的最短路径,而且还存在其他具有相同性质的连通图。他将所有这些图称为“测地线图”,并要求对这类图进行表征。

GeodeticGraphs

节点数为 n=1、2、... 的测地线图的数量为 1, 1, 2, 4, 10, 23, 66, 185, 586, 1880, 6360, ... (OEIS A337179)。

测地线图的例子包括哑铃图块图、缺少偶圈的仙人掌图 (Gorovoy 和 Zmiaikou 2021)、完全图 K_n (Gorovoy 和 Zmiaikou 2021)、奇圈图 C_(2n+1) (Gorovoy 和 Zmiaikou 2021)、棒棒糖图 (Gorovoy 和 Zmiaikou 2021)、三角形蛇图风车图


另请参阅

对跖图, 图距离矩阵

使用 Wolfram|Alpha 探索

参考文献

Frasser, C. E. "k-测地线图及其在计算机网络拓扑设计中的应用。" 在 Proc. Argentinian Workshop on Theoretical Computer Science, 28 JAIIO-WAIT'99. 页. 187-203, 1999.Gorovoy, D. 和 Zmiaikou, D. "关于具有唯一测地线和对跖点的图。" 2021年11月19日。 https://arxiv.org/abs/2111.09987.Ore, O. 图论。 普罗维登斯,罗德岛州:美国数学会,1962.Parthasarathy, K. R. 和 Srinivasan, N. "测地线块的一些通用构造。" 组合论杂志 33, 121-136, 1982.Sloane, N. J. A. 序列 A337179 在 "整数序列在线百科全书" 中。Stemple, J. G.; 和 Watkins, M. E. "关于平面测地线图。" 组合论杂志 4, 101-117, 1968.

请引用为

Weisstein, Eric W. “测地线图。” 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/GeodeticGraph.html

学科分类