主題
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

另請參閱

繞道矩陣, 繞道多項式

使用 探索

參考文獻

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 在 "整數序列線上百科全書" 中。

在 中引用

繞道指數

請這樣引用

Weisstein, Eric W. "繞道指數。" 來自 --一個 資源。 https://mathworld.tw/DetourIndex.html

主題分類