主题
Search

绕道指数

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

图 G 的绕道指数 omega(G) 被定义为图 G 的绕道矩阵的所有非对角矩阵元素之和的一半。

除非另有说明，否则在计算此类指标时通常会忽略氢原子，就像有机化学家在将苯环写成六边形时通常所做的那样 (Devillers and Balaban 1999, p. 25)。

许多命名图的预计算绕道指数在 Wolfram 语言中可用，如GraphData[graph,"DetourIndex"].

由于具有顶点计数 n 的Hamilton-连通图的所有非对角矩阵元素都等于 n-1，因此这种图的绕道指数由 n(n-1)^2/2 给出。

DetourIndex

绕道指数在区分图方面不是特别有效。 上图说明了许多共享相同绕道指数 omega 的小型非同构图 (Amić 和 Trinajstić 1995; Nikolić et al. 2000, p. 292, 已更正)，其中 n 是图顶点的数量。

下表给出了各种常见图类的数值。

图OEIS序列
Andrásfai 图A0000001, 35, 196, 550, 1183, 2176, 3610, 5566, 8125, ...
反棱柱图A139757X, X, 75, 196, 405, 726, 1183, 1800, 2601, 3610, ...
阿波罗尼安网络A29702718, 126, 1575, ...
哑铃图A226450X, X, 45, 124, 265, 486, 805, 1240, 1809, ...
黑主教图 BB_(n,n)A000000X, X, X, 194, 936, 2601, 7200, 15376, 32800, ...
书图 S_(n+1) square P_2A00000016, 67, 150, 251, 378, 531, 710, 915, ...
鸡尾酒会图 K_(n×2)A139757X, 16, 75, 196, 405, 726, 1183, 1800, 2601, ...
完全二部图 K_(n,n)A0000001, 16, 69, 184, 385, 696, 1141, 1744, 2529, 3520, ...
完全图 K_nA0024110, 1, 6, 18, 40, 75, 126, 196, 288, 405, 550, ...
完全三部图 K_(n,n,n)A0000006, 75, 288, 726, 1470, 2601, ...
2n-交叉棱柱图A000000X, X, X, 184, 696, 1744, 3520, 6216, 10024, ...
冠图A000000X, X, 63, 184, 385, 696, 1141, 1744, 2529, 3520, ...
立方体连接环图A296777X, X, 6348, 126016, 2022480, ...
环图 C_nA000000X, X, 6, 16, 35, 63, 105, 160, 234, 325, 440, 576, ...
斐波那契立方体图A2919181, 4, 28, 174, 864, 4000, 18241, ...
折叠立方体图A296778X, 1, 18, 184, 1800, 15136, ...
齿轮图A033430X, X, 108, 256, 500, 864, 1372, 2048, 2916, 4000, ...
网格图 P_n×P_nA2967790, 16, 256, 1744, 6912, 21744, ...
网格图 P_n×P_n×P_nA2967800, 184, 8788, ...
半立方体图A0000001, 18, 196, 1800, 15376, ...
河内图A0000006, 252, 8439, ...
舵图A181617X, X, 72, 160, 300, 504, 784, 1152, 1620, 2200, ...
超立方体图 Q_nA2887201, 16, 184, 1744, 15136, ...
Keller 图 G_nA000000X, 1800, 127008, 8323200, ...
国王图 Ki_(n,n)A288959X, 18, 288, 1800, 7200, 22050, ...
骑士图 Kn_(n,n)A296781X, X, 1532, 6840, 21744, ...
梯子图 P_2 square P_nA0000001, 16, 67, 176, 369, 668, 1099, 1684, 2449, 3416, ...
门格海绵图A0000002864, ...
莫比乌斯梯子 M_nA000000X, X, 69, 196, 385, 726, 1141, 1800, 2529, 3610, ...
Mycielski 图 M_nA0000000, 1, 35, 550, 5566, 49726, 419710, 3447550, ...
奇图 O_nA0000000, 6, 390, 20230, 984375, 49092351, 2523571050, ...
平底锅图A000000X, X, 13, 28, 54, 90, 142, 208, 295, 400, 531, 684, ...
路径图 P_nA0002920, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, ...
排列星图 Q_(n,n)A2967820, 1, 63, 6216, ...
棱柱图 Y_nA000000X, X, 75, 184, 405, 696, 1183, 1744, 2601, 3520, 4851, ...
皇后图A288959X, 18, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
车补图 K_n square K_n^_A2889590, X, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
车图 K_n square K_nA2889590, 16, 288, 1800, 7200, 22050, 56448, 127008, 259200, ...
谢尔宾斯基地毯图A000000160, 123080, ...
谢尔宾斯基垫片图A2967836, 69, 1404, 34485, ...
谢尔宾斯基四面体图A000000...
星图 S_nA000290X, X, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, ...
太阳图A000000X, X, 69, 180, 375, 678, 1113, 1704, 2475, 3450, ...
日瓣图 C_n circledot K_1A000000X, X, 39, 92, 185, 318, 511, 760, 1089, 1490, 1991, ...
四面体约翰逊图A000000X, X, X, X, X, 18, 405, 3610, 20230, 84700, 289338, ...
环面网格图 C_n square C_nA296784X, X, 288, 1744, 7200, 21744, 56448, ...
换位图 G_nA2967850, 1, 69, 6216, ...
三角形图A000000X, X, 6, 75, 405, 1470, 4200, 10206, 22050, ...
三角形网格图 T_nA2887196, 69, 399, 1467, 4197, 10203, 22047, ...
网络图A000000X, X, 189, 452, 970, 1653, 2779, 4080, 6048, 8165, ...
轮图 W_nA002411X, X, X, 18, 40, 75, 126, 196, 288, 405, 550, 726, ...
白主教图 WB_(n,n)A000000X, X, X, 194, 726, 2601, 6348, 15376, 30420, ...

下表总结了其中一些图类的闭合形式。

图绕道指数
Andrásfai 图{35 for n=2; 1/2(3n-1)(3n-2)^2 otherwise
反棱柱图n(2n-1)^2
哑铃图n(3n^2-5n+3)
黑主教图 BB_(n,n){28 for n=3; 194 for n=4; 1/(128)[2n^2-3-(-1)^n]^2[2n^2+1-(-1)^n] otherwise
书图{16 for n=1; 67 for n=2; 13n^2+10n+3 otherwise
鸡尾酒会图 K_(n×2){16 for n=2; n(2n-1)^2 otherwise
完全二部图 K_(n,n)n(4n^2-5n+2)
完全图 K_n1/2(n-1)^2n
完全三部图 K_(n,n,n)3/2n(3n-1)^2
2n-交叉棱柱图n(4n^2-5n+2)
冠图{63 for n=3; n(4n^2-5n+2) otherwise
环图 C_n1/(16)n[(-1)^(n+1)+6n^2-8n+1]
齿轮图4n^3
网格图 P_n square P_n{1/4n^2(2n^4-5n^2+4) for n even; 1/2(n-1)^3(n+1)^3 for n odd
网格图 P_n square P_n square P_n{1/2n^3(n^6-5/2n^3+2) for n even; 1/2(n-1)^3(n^2+n+1)^3 for n odd
半立方体图2^(n-4)(2^n-2)^2
舵图2(n^3+7n^2+16n+11)
超立方体图 Q_n2^(n-2)(2^(2n+1)-5·2^n+4)
Keller 图 G_n2^(2n-1)(4^n-1)^2
国王图 Ki_(n,n)1/2(n-1)^2n^2(n+1)^2
梯子图 P_2 square P_n1/4[16n^3-26n^2+28n-15-(-1)^n]
莫比乌斯梯子 M_n1/2n[(-1)^n(n-1)+(8n^2-9n+3)]
Mycielski 图{0 for n=1; 35 for n=3; 1/2(3·2^(n-2)-2)^2(3·2^(n-2)-1) otherwise
奇图{390 for n=3; 1/2[(2n-1; n-1)-1]^2(2n-1; n-1) otherwise
平底锅图1/(16)[6n^3+4n^2+n+(-1)^(n+1)(n+2)+2]
路径图 P_n1/6(n-1)n(n+1)
棱柱图 Y_n1/2n[(-1)^(n+1)(n-1)+(8n^2-9n+3)]
皇后图 Q_(n,n)1/2(n-1)^2n^2(n+1)^2
车补图 K_n square K_n^_{undefined for n=2; 1/2(n-1)^2n^2(n+1)^2 otherwise
车图 K_n square K_n{16 for n=2; 1/2(n-1)^2n^2(n+1)^2 otherwise
谢尔宾斯基四面体图(2^(2n-1)+1)^2(4^(n-1)+1)
星图 S_n(n-1)^2
太阳图n(4n^2-6n+5)
日瓣图 C_n circledot K_11/4n[(-1)^(n-1)+3(2n^2-1)]
四面体约翰逊图1/2(n; 3)[(n; 3)-1]^2
环面网格图 C_n square C_n{1/4n^2(2n^4-5n^2+4) for n even; 1/2n^2(n^2-1)^2 for n odd
换位图{1 for n=1; 1/4n![n!(2n!-5)+5] otherwise
三角形图1/(16)(n-1)(n^2-n-2)^2
三角形网格图{0 for n=0; 6 for n=1; 69 for n=2; 399 for n=3; 1/(16)n^2(n+1)(n+2)(n+3)^2-3 otherwise
网络图1/8n[72n^2-61n+22+(-1)^n(10-9n)]
轮图 W_n1/2(n-1)^2n
白主教图 WB_(n,n){16 for n=3; 194 for n=4; 1/(128)[2n^2+(-1)^n-5]^2[2n^2+(-1)^n-1] otherwise

另请参阅

绕道矩阵, 绕道多项式

使用 Wolfram|Alpha 探索

参考文献

Amić, D. and Trinajstić, N. "论绕道矩阵。" Croat. Chem. Acta 68, 53-62, 1995.Devillers, J. and Balaban, A. T. (编). 拓扑指数和 QSAR 与 QSPR 中的相关描述符。 阿姆斯特丹，荷兰：Gordon and Breach, pp. 82-83, 2000.Nikolić, S.; Trinajstić, N.; 和 Mihalić, A. "绕道矩阵和绕道指数。" 第 6 章，拓扑指数和 QSAR 与 QSPR 中的相关描述符 (J. Devillers A. T. 和 Balaban 编). 阿姆斯特丹，荷兰：Gordon and Breach, pp. 279-306, 2000.Randić, M.; DeAlba, L. M.; Harris, F. E. "具有相同绕道矩阵的图。" Croat. Chem. Acta 71, 53-68, 1998.Sloane, N. J. A. 序列 A000290/M3556, A000292/M3382, A002411/M4116, 和 A139757 在 "整数序列在线百科全书" 中。

在 Wolfram|Alpha 中引用

绕道指数

请这样引用

Weisstein, Eric W. "绕道指数。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/DetourIndex.html

主题分类