主題
Search

維納指數

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

維納指數 W，記作 w (Wiener 1947)，也稱為“路徑數”或維納數 (Plavšić et al. 1993)，是為節點數為 n 的圖定義的圖指標，定義如下

W=1/2sum_(i=1)^nsum_(j=1)^n(d)_(ij),
(1)

其中 (d)_(ij) 是圖距離矩陣。

除非另有說明，否則在計算此類指標時通常會忽略氫原子，就像有機化學家通常將苯環寫成六邊形一樣（Devillers 和 Balaban 1999, p. 25）。

圖 W(G) 的維納指數 G，其頂點數為 |G|，與圖的平均無序數 A(G) 相關，關係如下

A(G)=(2W(G))/(|G|)
(2)

（Fried 2022）。

圖 G_1 和 G_2 的圖笛卡爾積的維納指數由下式給出

W(G_1 square G_2)=|G_1|^2W(G_2)+|G_2|^2W(G_1)
(3)

（Yeh 和 Gutman 1994，Fried 2022）。

維納指數的區分度不高。事實上，爪圖和四個節點的方圖已經無法用維納指數區分（兩者都為 8）。非維納唯一連通圖在 n=1、2、... 個節點上的數量由 0, 0, 0, 2, 16, 108, 847, 11110, 261072, ... 給出 (OEIS A193217)。

許多圖的預計算值在 Wolfram Language 中實現為GraphData[g,"WienerIndex"].

下表總結了各種特殊圖類的維納指數值。

圖類OEISW(G_1), W(G_2), ...
Andrásfai 圖A2920181, 15, 44, 88, 147, 221, 310, 414, ...
羚羊圖 n×nA2920390, infty, infty, infty, infty, infty, infty, 11548, 16660, ...
反稜柱圖A002411X, X, 18, 40, 75, 126, 196, 288, ...
阿波羅網路A2890226, 27, 204, 1941, 19572, 198567, ...
黑主教圖 n×nA2920510, 1, 14, 42, 124, 251, 506, 852, 1432, 2165, ...
雞尾酒會圖A001105infty, 8, 18, 32, 50, 72, 98, 128, 162, ...
完全二分圖 K_(n,n)A0005671, 1, 5, 73, 2069, 95401, 6487445, ...
完全三部圖 K_(n,n,n)A0941591, 11, 1243, 490043, 463370491, ...
完全圖 K_nA0002170, 1, 3, 6, 10, 15, 21, 28, 36, ...
2n-交叉稜柱圖A292022X, 48, 132, 288, 540, 912, 1428, ...
皇冠圖 K_2 square K_n^_A033428X, X, 27, 48, 75, 108, 147, 192, 243, ...
立方體連線迴圈圖A292028X, X, 888, 9472, 76336, 559584, 3594952, ...
圈圖 C_nA034828X, X, 3, 8, 15, 27, 42, 64, 90, ...
斐波那契立方體圖A2384191, 4, 16, 54, 176, 548, 1667, 4968, ...
五跳圖 n×nA2920400, infty, infty, infty, infty, infty, infty, 6364, 9888, 15216, ...
摺疊立方體圖A292029X, 1, 6, 40, 200, 1056, 4928, 23808, ...
齒輪圖A049598X, X, 36, 72, 120, 180, 252, 336, 432, ...
網格圖 P_n square P_nA1439450, 8, 72, 320, 1000, 2520, 5488, 10752, ...
網格圖 P_n square P_n square P_nA2920450, 48, 972, 7680, 37500, 136080, 403368, ...
半立方體圖A2920440, 1, 6, 32, 160, 768, 3584, 16384, ...
河內圖A2900043, 72, 1419, 26580, 487839, 8867088, ...
超立方體圖 Q_nA0026971, 8, 48, 256, 1280, 6144, 28672, ...
Keller 圖A292056infty, 200, 2944, 43392, 650240, 9889792, ...
國王圖 n×nA2920530, 6, 52, 228, 708, 1778, 3864, 7560, ...
騎士圖 n×nA2920540, infty, infty, 288, 708, 1580, 3144, 5804, 9996, ...
門格海綿圖A292036612, 794976, 954380016, ...
莫比烏斯梯子A180857X, X, 21, 44, 85, 138, 217, 312, 441, ...
Mycielski 圖A2920550, 1, 15, 90, 435, 1926, 8175, 33930, ...
奇圖 O_nA1363280, 3, 75, 1435, 25515, 436821, ...
平底鍋圖A1808618, 16, 26, 42, 61, 88, 119, 160, 206, 264, ...
路徑圖 P_nA0002920, 1, 4, 10, 20, 35, 56, 84, 120, ...
排列星圖 PS_nA2840390, 1, 27, 744, 26520, 1239840, ...
稜柱圖 Y_nA138179X, X, 21, 48, 85, 144, 217, 320, 441, ...
皇后圖 n×nA2920570, 6, 44, 164, 440, 970, 1876, 3304, 5424, ...
車圖 K_n square K_nA085537X, 8, 54, 192, 500, 1080, 2058, 3584, 5832, ...
車補圖 K_n square K_n^_A2920580, infty, 54, 168, 400, 810, 1470, 2464, ...
謝爾賓斯基地毯圖A29202564, 13224, 2535136, 485339728, ...
謝爾賓斯基墊片圖A2901293, 21, 246, 3765, 64032, 1130463, 20215254, ...
謝爾賓斯基四面體圖A2920266, 66, 1476, 42984, 1343568, 42744480, ...
星圖 S_nA0002900, 1, 4, 9, 16, 25, 36, 49, 64, ...
太陽圖A180863X, X, 21, 44, 75, 114, 161, 216, 279, 350, ...
日瓣圖 C_n circledot K_1A180574X, X, 27, 60, 105, 174, 259, 376, 513, 690, ...
四面體約翰遜圖A292061X, X, X, X, X, 300, 1050, 2940, 7056, 15120, ...
環面網格圖 C_n square C_nA12265754, 256, 750, 1944, 4116, 8192, 14580, 25000, ...
轉置圖A2920620, 1, 21, 552, 19560, 920160, 55974240, ...
三角形圖A0060110, 3, 18, 60, 150, 315, 588, 1008, 1620, ...
三角形網格圖A1128513, 21, 81, 231, 546, 1134, 2142, 3762, 6237, ...
網路圖A180576X, X, 69, 148, 255, 417, 616, 888, 1206, 1615, ...
輪圖 W_nA002378X, X, X, X, 12, 20, 30, 42, 56, 72, ...
白主教圖 n×nA292059X, 1, 8, 42, 104, 251, 464, 852, 1360, 2165, ...

下表總結了閉合形式。圈圖由 Plavšić 等人 (1993) 和 Babić 等人 (2002) 考慮，路徑圖由 Plavšić 等人 (1993) 考慮。

Andrásfai 圖1/2(3n-1)(5n-1)
反稜柱圖1/2(n+1)n^2
雞尾酒會圖 K_(n×2)2n^2
完全圖 K_n1/2n(n-1)
交叉稜柱圖4n(n^2+2)
皇冠圖 S_n^03n^2
圈圖 C_n, n>=3{1/8n^3 for n even; 1/8(n-1)n(n+1) for n odd
齒輪圖6n(n-1)
網格圖 P_n square P_n1/3n^3(n-1)(n+1)
網格圖 P_n square P_n square P_n1/2n^5(n-1)(n+1)
半立方體圖{0 for n=1; n·2^(2n-5) for n>=2
超立方體圖 Q_nn·4^(n-1)
莫比烏斯梯子1/4n[2n(n+2)-3-(-1)^n]
Mycielski 圖 M_n1/(144)(216-272^(3+n)-563^n+814^n)
路徑圖 P_n1/6n(n^2-1)
車圖 K_n square K_nn^3(n-1)
星圖 S_n(n-1)^2
太陽圖n(4n-5)
日瓣圖 C_n circledot K_11/4n[(-1)^n+2n(n+4)-5]
三角形圖1/4n(n-1)^2(n-2)
輪圖 W_n(n-2)(n-1)

另請參閱

平均無序數, 巴拉班指數, 圖距離矩陣, 基爾霍夫指數, 電阻距離, 拓撲指數, 維納和指數

使用 探索

參考文獻

Babić, D.; Klein, D. J.; Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, 2002.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 26 and 108-109, 1999.Entringer, R. C.; Jackson, D. E.; and Snyder, D. "Distance in Graphs." Czech. Math. J. 26, 283-296, 1976.Fried, S. "The Disorder Number of a Graph." 7 Aug 2022. https://arxiv.org/abs/2208.03788/.Hosoya, H. "Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons." Bull. Chem. Soc. Japan 44, 2322-2239, 1971.Plavšić, D.; Nikolić, S.; Trinajstić, N.; and Mihalić, Z. "On the Harary Index for the Characterization of Chemical Graphs." J. Math. Chem. 12, 235-250, 1993.Sloane, N. J. A. Sequence OEIS A193217 in "The On-Line Encyclopedia of Integer Sequences."Wiener, H. J. "Structural Determination of Paraffin Boiling Points." J. Amer. Chem. Soc. 69, 17-20, 1947.Wiener, H. "Influence of Interatomic Forces on Paraffin Properties." J. Chem. Phys. 15, 766, 1947.Wiener, H. "Vapor Pressure-Temperature Relationships Among the Branched Paraffin Hydrocarbons." J. Phys. Chem. 52, 425-430, 1948.Wiener, H. "Relation of the Physical Properties of the Isomeric Alkanes to Molecular Structure. Surface Tension, Specific Dispersion, and Critical Solution Temperature in Aniline." J. Phys. Chem. 52, 1082-1089, 1948.Yeh, Y.-N. and Gutman, I. "On the Sum of All Distances in Composite Graphs." Disc. Math. 135, 359-365, 1994.Zerovnik, J. "Szeged Index of Symmetric Graphs." J. Chem. Inf. Comput. Sci. 39, 77-80, 1999.

在 中被引用

維納指數

引用為

Weisstein, Eric W. "維納指數。" 來自 -- 資源。 https://mathworld.tw/WienerIndex.html

主題分類