“Wiener index”的意思、由来-开放百科全书

In chemical graph theory, the Wiener index (also Wiener number) introduced by Harry Wiener, is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule.^[1]

History

The Wiener index is named after Harry Wiener, who introduced it in 1947; at the time, Wiener called it the "path number".^[2] It is the oldest topological index related to molecular branching.^[3] Based on its success, many other topological indexes of chemical graphs, based on information in the distance matrix of the graph, have been developed subsequently to Wiener's work.^[4]

The same quantity has also been studied in pure mathematics, under various names including the gross status,^[5] the distance of a graph,^[6] and the transmission.^[7] The Wiener index is also closely related to the closeness centrality of a vertex in a graph, a quantity inversely proportional to the sum of all distances between the given vertex and all other vertices that has been frequently used in sociometry and the theory of social networks.^[6]

Example

Butane (C₄H₁₀) has two different structural isomers: n-butane, with a linear structure of four carbon atoms, and isobutane, with a branched structure. The chemical graph for n-butane is a four-vertex path graph, and the chemical graph for isobutane is a tree with one central vertex connected to three leaves.

The n-butane molecule has three pairs of vertices at distance one from each other, two pairs at distance two, and one pair at distance three, so its Wiener index is

The isobutane molecule has three pairs of vertices at distances one from each other (the three leaf-center pairs), and three pairs at distance two (the leaf-leaf pairs). Therefore, its Wiener index is

These numbers are instances of formulas for special cases of the Wiener index: it is

for any

-vertex path graph such as the graph of n-butane,^[8] and

for any

-vertex star such as the graph of isobutane.^[9]

Thus, even though these two molecules have the same chemical formula, and the same numbers of carbon-carbon and carbon-hydrogen bonds, their different structures give rise to different Wiener indices.

Relation to chemical properties

Wiener showed that the Wiener index number is closely correlated with the boiling points of alkane molecules.^[2] Later work on quantitative structure–activity relationships showed that it is also correlated with other quantities including the parameters of its critical point,^[10] the density, surface tension, and viscosity of its liquid phase,^[11] and the van der Waals surface area of the molecule.^[12]

Calculation in arbitrary graphs

The Wiener index may be calculated directly using an algorithm for computing all pairwise distances in the graph. When the graph is unweighted (so the length of a path is just its number of edges), these distances may be calculated by repeating a breadth-first search algorithm, once for each starting vertex.^[15] The total time for this approach is O(nm), where n is the number of vertices in the graph and m is its number of edges.

For weighted graphs, one may instead use the Floyd–Warshall algorithm^[15]^[13]^[14] or Johnson's algorithm,^[15] with running time O(n³) or O(nm + n² log n) respectively. Alternative but less efficient algorithms based on repeated matrix multiplication have also been developed within the chemical informatics literature.^[16]^[17]

Calculation in special types of graph

When the underlying graph is a tree (as is true for instance for the alkanes originally studied by Wiener), the Wiener index may be calculated more efficiently. If the graph is partitioned into two subtrees by removing a single edge e, then its Wiener index is the sum of the Wiener indices of the two subtrees, together with a third term representing the paths that pass through e. This third term may be calculated in linear time by computing the sum of distances of all vertices from e within each subtree and multiplying the two sums.^[18] This divide and conquer algorithm can be generalized from trees to graphs of bounded treewidth, and leads to near-linear-time algorithms for such graphs.^[19]

An alternative method for calculating the Wiener index of a tree, by Bojan Mohar and Tomaž Pisanski, works by generalizing the problem to graphs with weighted vertices, where the weight of a path is the product of its length with the weights of its two endpoints. If v is a leaf vertex of the tree then the Wiener index of the tree may be calculated by merging v with its parent (adding their weights together), computing the index of the resulting smaller tree, and adding a simple correction term for the paths that pass through the edge from v to its parent. By repeatedly removing leaves in this way, the Wiener index may be calculated in linear time.^[20]

For graphs that are constructed as products of simpler graphs, the Wiener index of the product graph can often be computed by a simple formula that combines the indices of its factors.^[21] Benzenoids (graphs formed by gluing regular hexagons edge-to-edge) can be embedded isometrically into the Cartesian product of three trees, allowing their Wiener indices to be computed in linear time by using the product formula together with the linear time tree algorithm.^[22]

Inverse problem

Gutman and Yeh conjectured, but were unable to prove, a similar description of the numbers that can be represented as Wiener indices of trees, with a set of 49 exceptional values:

References

1. ^{{citation | last = Rouvray | first = Dennis H. | editor1-last = Rouvray | editor1-first = Dennis H. | editor2-last = King | editor2-first = Robert Bruce | contribution = The rich legacy of half a century of the Wiener index | pages = 16–37 | publisher = Horwood Publishing | title = Topology in Chemistry: Discrete Mathematics of Molecules | url = https://books.google.com/books?id=a-ZkUeVLdO8C&pg=PA16 | year = 2002}}.
2. ^¹{{citation | last = Wiener | first = H. | doi = 10.1021/ja01193a005 | issue = 69 | journal = Journal of the American Chemical Society | pages = 17–20 | title = Structural determination of paraffin boiling points | volume = 1 | year = 1947}}.
3. ^{{citation | last1 = Todeschini | first1 = Roberto | last2 = Consonni | first2 = Viviana | isbn = 3-527-29913-0 | publisher = Wiley | title = Handbook of Molecular Descriptors | year = 2000}}.
4. ^{{harvtxt|Rouvray|2002}}. See in particular Table 2 on p. 32.
5. ^{{citation | last = Harary | first = Frank | authorlink = Frank Harary | journal = Sociometry | mr = 0134798 | pages = 23–43 | title = Status and contrastatus | volume = 22 | year = 1959 | doi=10.2307/2785610}}
6. ^¹{{citation | last1 = Entringer | first1 = R. C. | last2 = Jackson | first2 = D. E. | last3 = Snyder | first3 = D. A. | journal = Czechoslovak Mathematical Journal | mr = 0543771 | pages = 283–296 | title = Distance in graphs | volume = 26 | issue = 101 | year = 1976}}.
7. ^{{citation | last = Šoltés | first = Ľubomír | issue = 1 | journal = Mathematica Slovaca | mr = 1094978 | pages = 11–16 | title = Transmission in graphs: a bound and vertex removing | volume = 41 | year = 1991}}.
8. ^As {{harvtxt|Rouvray|2002}} describes, this formula was already given by {{harvtxt|Wiener|1947}}.
9. ^{{citation | last1 = Bonchev | first1 = D. | last2 = Trinajstić | first2 = N. | doi = 10.1063/1.434593 | issue = 10 | journal = Journal of Chemical Physics | pages = 4517–4533 | title = Information theory, distance matrix, and molecular branching | volume = 67 | year = 1977| bibcode = 1977JChPh..67.4517B}}.
10. ^{{citation | last1 = Stiel | first1 = Leonard I. | last2 = Thodos | first2 = George | doi = 10.1002/aic.690080421 | issue = 4 | journal = AIChE Journal | pages = 527–529 | title = The normal boiling points and critical constants of saturated aliphatic hydrocarbons | volume = 8 | year = 1962}}.
11. ^{{citation | last1 = Rouvray | first1 = D. H. | last2 = Crafford | first2 = B. C. | journal = South African Journal of Science | page = 47 | title = The dependence of physical-chemical properties on topological factors | volume = 72 | year = 1976}}.
12. ^{{citation | last1 = Gutman | first1 = Ivan | last2 = Körtvélyesi | first2 = T. | journal = Zeitschrift für Naturforschung | pages = 669–671 | title = Wiener indices and molecular surfaces | volume = 50a | year = 1995}}.
13. ^{{citation | last = Floyd | first = Robert W. | author-link = Robert W. Floyd | date = June 1962 | doi = 10.1145/367766.368168 | issue = 6 | journal = Communications of the ACM | page = 345 | title = Algorithm 97: Shortest Path | volume = 5}}.
14. ^{{citation | last = Warshall | first = Stephen | date = January 1962 | doi = 10.1145/321105.321107 | issue = 1 | journal = Journal of the ACM | pages = 11–12 | title = A theorem on Boolean matrices | volume = 9}}.
15. ^{{citation | last = Johnson | first = Donald B. | author-link = Donald B. Johnson | doi = 10.1145/321992.321993 | issue = 1 | journal = Journal of the ACM | pages = 1–13 | title = Efficient algorithms for shortest paths in sparse networks | volume = 24 | year = 1977}}.
16. ^{{citation | last = Bersohn | first = Malcom | doi = 10.1002/jcc.540040115 | issue = 1 | journal = Journal of Computational Chemistry | pages = 110–113 | title = A fast algorithm for calculation of the distance matrix of a molecule | volume = 4 | year = 1983}}.
17. ^{{citation | last1 = Müller | first1 = W. R. | last2 = Szymanski | first2 = K. | last3 = Knop | first3 = J. V. | last4 = Trinajstić | first4 = N. | doi = 10.1002/jcc.540080209 | issue = 2 | journal = Journal of Computational Chemistry | pages = 170–173 | title = An algorithm for construction of the molecular distance matrix | volume = 8 | year = 1987}}.
18. ^{{citation | last1 = Canfield | first1 = E. R. | last2 = Robinson | first2 = R. W. | last3 = Rouvray | first3 = D. H. | doi = 10.1002/jcc.540060613 | issue = 6 | journal = Journal of Computational Chemistry | mr = 824918 | pages = 598–609 | title = Determination of the Wiener molecular branching index for the general tree | volume = 6 | year = 1985}}.
19. ^{{citation | last1 = Cabello | first1 = Sergio | last2 = Knauer | first2 = Christian | doi = 10.1016/j.comgeo.2009.02.001 | issue = 9 | journal = Computational Geometry | mr = 2543804 | pages = 815–824 | title = Algorithms for graphs of bounded treewidth via orthogonal range searching | volume = 42 | year = 2009}}.
20. ^¹²{{citation | last1 = Mohar | first1 = Bojan | author1-link = Bojan Mohar | last2 = Pisanski | first2 = Tomaž | author2-link = Tomaž Pisanski | doi = 10.1007/BF01167206 | issue = 3 | journal = Journal of Mathematical Chemistry | mr = 966088 | pages = 267–277 | title = How to compute the Wiener index of a graph | volume = 2 | year = 1988}}.
21. ^{{citation | last1 = Yeh | first1 = Yeong Nan | last2 = Gutman | first2 = Ivan | doi = 10.1016/0012-365X(93)E0092-I | issue = 1-3 | journal = Discrete Mathematics | mr = 1310892 | pages = 359–365 | title = On the sum of all distances in composite graphs | volume = 135 | year = 1994}}.
22. ^{{citation | last1 = Chepoi | first1 = Victor | last2 = Klavžar | first2 = Sandi | issue = 4 | journal = Journal of Chemical Information and Computer Sciences | pages = 752–755 | title = The Wiener index and the Szeged index of benzenoid systems in linear time | volume = 37 | year = 1997 | doi=10.1021/ci9700079}}. For earlier algorithms for benzenoids based on their partial cube structure, see {{citation | last1 = Klavžar | first1 = Sandi | last2 = Gutman | first2 = Ivan | last3 = Mohar | first3 = Bojan | author3-link = Bojan Mohar | issue = 3 | journal = Journal of Chemical Information and Computer Sciences | pages = 590–593 | title = Labeling of benzenoid systems which reflects the vertex-distance relations | url = http://www.fmf.uni-lj.si/~klavzar/preprints/labeling-benzi.pdf | volume = 35 | year = 1995 | doi=10.1021/ci00025a030}}.
23. ^{{citation | last1 = Gutman | first1 = Ivan | last2 = Yeh | first2 = Yeong-Nan | issue = 4 | journal = Mathematica Slovaca | mr = 1387048 | pages = 327–334 | title = The sum of all distances in bipartite graphs | volume = 45 | year = 1995}}.
24. ^{{citation | last = Wagner | first = Stephan G. | doi = 10.1007/s10440-006-9026-5 | issue = 2 | journal = Acta Applicandae Mathematicae | mr = 2249544 | pages = 119–132 | title = A class of trees and its Wiener index | volume = 91 | year = 2006}}.
25. ^{{citation | last1 = Wang | first1 = Hua | last2 = Yu | first2 = Guang | doi = 10.1007/s10440-006-9037-2 | issue = 1 | journal = Acta Applicandae Mathematicae | mr = 2263469 | pages = 15–20 | title = All but 49 numbers are Wiener indices of trees | volume = 92 | year = 2006}}.